高级数据结构（一）：红黑树、伸展树、Treap树、跳表

各位同学，今天我们来聊点硬核的。红黑树、伸展树、Treap树、跳表——这四个家伙，说白了就是「更聪明的查找结构」。你想想看，普通的二叉搜索树，运气不好就退化成链表了，查找变成O(n)，那还玩什么？

我刚开始做嵌入式开发时，就吃过这个亏。一个查找频繁的模块，我用普通BST，结果数据插入顺序刚好是递增的……嗯，性能直接崩了。从那以后，我对平衡数据结构就特别上心。

一、红黑树：工业级最常用的平衡树

红黑树，我个人认为是「性价比最高的平衡树」。它不像AVL树那样严格平衡，但性能足够好，而且插入删除的调整代价更小。

红黑树的规则其实就五条：

• 每个节点要么红，要么黑
• 根节点是黑色
• 叶子节点（NIL）是黑色
• 红色节点的子节点必须是黑色（不能有连续红节点）
• 从任一节点到其每个叶子的路径上，黑色节点数量相同

这五条规则保证了什么？保证了树的高度不超过 2log(n+1)。换句话说，查找最坏情况也是O(log n)。

我在项目中用过红黑树来实现定时器管理器。几百个定时器，频繁地插入、删除、查找最小超时时间。红黑树完美胜任。Linux内核的CFS调度器、C++的std::map，底层都是红黑树。

红黑树的插入和删除，核心操作就是「变色」和「旋转」。旋转分左旋和右旋，跟AVL树一样。但红黑树的调整逻辑更复杂一些，分好几种情况。我建议你记住一个口诀：「叔红就变色，叔黑就旋转」。

// 红黑树节点结构（简化版）
typedef enum { RED, BLACK } Color;

typedef struct RBNode {
    int key;
    Color color;
    struct RBNode *left, *right, *parent;
} RBNode;

// 左旋操作
void leftRotate(RBNode **root, RBNode *x) {
    RBNode *y = x->right;
    x->right = y->left;
    if (y->left != NULL)
        y->left->parent = x;
    y->parent = x->parent;
    if (x->parent == NULL)
        *root = y;
    else if (x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;
    y->left = x;
    x->parent = y;
}

二、伸展树：用过的节点往上提

伸展树（Splay Tree）的思路很有意思——它不追求每次都平衡，而是把刚访问过的节点「伸展」到根。你想想看，如果程序有局部性访问特征（刚用过的数据很可能再用），伸展树就特别高效。

伸展树的核心操作就是「伸展」：通过一系列旋转，把某个节点移到根。旋转分三种：

• Zig：父节点是根，单旋转
• Zig-Zig：节点、父节点、祖父节点在同一直线上，两次同向旋转
• Zig-Zag：节点、父节点、祖父节点不在同一直线上，两次反向旋转

伸展树的摊还时间复杂度是O(log n)。什么意思？单次操作可能很慢（O(n)），但连续m次操作的总时间是O(m log n)。

我记得有一次做缓存系统，需要频繁访问最近用过的数据。用伸展树就很合适——最近访问的节点自动跑到根，下次访问就是O(1)。

三、Treap树：树+堆的混血儿

Treap = Tree + Heap。每个节点除了key，还有一个随机优先级。从key角度看是二叉搜索树，从优先级角度看是堆（通常是大顶堆）。

为什么加随机优先级？因为随机性能保证平衡。插入时，如果新节点的优先级比父节点大，就旋转上去。删除时，把要删的节点旋转到叶子再删。

Treap的实现比红黑树简单得多，代码量大概只有红黑树的一半。而且期望时间复杂度也是O(log n)。

// Treap节点结构
typedef struct TreapNode {
    int key;
    int priority;  // 随机优先级
    struct TreapNode *left, *right;
} TreapNode;

// 插入操作
TreapNode* insert(TreapNode *root, int key) {
    if (root == NULL) {
        TreapNode *node = malloc(sizeof(TreapNode));
        node->key = key;
        node->priority = rand();  // 随机生成
        node->left = node->right = NULL;
        return node;
    }
    if (key < root->key) {
        root->left = insert(root->left, key);
        if (root->left->priority > root->priority)
            root = rightRotate(root);  // 右旋
    } else {
        root->right = insert(root->right, key);
        if (root->right->priority > root->priority)
            root = leftRotate(root);   // 左旋
    }
    return root;
}

四、跳表：链表的革命性升级

跳表（Skip List）跟前面三个完全不同——它不是树，而是多层链表。底层是完整的有序链表，上层是「快速通道」，每层节点数大约是下层的1/2。

查找时，从顶层开始，如果下一个节点比目标小，就向右走；否则向下走。这样平均查找长度是O(log n)。

跳表的实现比红黑树简单太多了。没有旋转，没有变色，只有简单的指针操作。而且支持高效的区间查询——这在树结构里比较麻烦。

// 跳表节点结构
#define MAX_LEVEL 16

typedef struct SkipNode {
    int key;
    struct SkipNode **forward;  // 每层的下一个节点
} SkipNode;

typedef struct SkipList {
    int level;
    SkipNode *header;  // 头节点，不存数据
} SkipList;

// 查找操作
SkipNode* search(SkipList *list, int key) {
    SkipNode *cur = list->header;
    for (int i = list->level - 1; i >= 0; i--) {
        while (cur->forward[i] != NULL && 
               cur->forward[i]->key < key) {
            cur = cur->forward[i];
        }
    }
    cur = cur->forward[0];
    if (cur != NULL && cur->key == key)
        return cur;
    return NULL;
}

我曾经用跳表实现过一个日志索引系统。日志按时间戳排序，需要支持按时间范围查询。跳表的区间查询能力让这个需求变得很简单——找到起始节点，然后沿着底层链表往后遍历就行。

五、四种结构的对比与选择

数据结构	平衡方式	实现难度	最坏情况	适用场景
红黑树	颜色约束+旋转	高	O(log n)	通用、工业级、实时系统
伸展树	伸展操作	中	O(n)	局部性访问、缓存
Treap树	随机优先级	低	O(n)概率极低	竞赛、快速原型
跳表	随机层数	低	O(n)概率极低	区间查询、并发场景

怎么选？我个人建议：

• 如果你在做工业级项目，要求稳定可靠，选红黑树
• 如果数据访问有强烈的局部性，选伸展树
• 如果你需要快速实现，或者写竞赛题，选Treap
• 如果你需要区间查询，或者做并发数据结构，选跳表

好了，这四种高级数据结构就讲到这里。每种都有它的脾气和适用场景。你想想看，没有一种数据结构是万能的，关键是要理解它们的本质，在合适的场景用合适的工具。

下一章我们会继续深入其他高级数据结构。今天的内容，建议你动手实现一下Treap和跳表——代码量不大，但能帮你真正理解它们的运作机制。