红黑树

1. 引言

首先, 明确一个问题, 什么是红黑树? 红黑树的历史可以追溯至1972年, 一个姓 Bayer 的人发明了一种特殊的 B-tree 数据结构(可见 B-tree 先于红黑树). 这种树的特点是具有极好的平衡特性, 并且任一从根节点到叶子节点的路径所包含的节点数都一致——计算机界的强迫症尤为严重. 但是, 这种树并不是一种二叉搜索树. Bayer 称这种树为 "对称二叉B-tree". 当然, 后来就发展成为 2-3-4树(什么是2-3-4树本文暂且按下不表). 继而1978年, L.J. Guibas 和 R. Sedgewick 在论文A Dichromatic Framework for Balanced Trees中, 基于前面说的对称二叉B-tree推演出了红黑树. 至于为什么叫红黑树, 一说红黑是作者工作时彩色激光打印机能够打印的最好看的色彩, 一说是红颜色和黑颜色的笔方便绘制红黑树. 不论如何事物的发展总是基于所处的历史条件下的, 上世纪七八十年代规模化的集成电路已经发展起来了, 可以说硬件正在以摩尔定律所预测的那样指数式更新迭代, 与此同时科学家们也必须找到高效管理数据的方法, 以充分利用硬件资源, 从操作系统到应用软件, 从电路设计到指令系统, 计算机系统的大厦根基不是一天建成的.

本文仅从数据结构角度介绍红黑树, 并不涉及其具体应用.

2. 定义

要知道, 红黑树是一种特殊的2-3-4树, 所有的自平衡二叉树都可以从2-3-4树那里寻得身影, 可以说后者是一种平衡树的范式了. 笔者先介绍红黑树所具有的性质, 再说明其结构体定义.

红黑树是一中二叉搜索树, 那肯定具有一般搜索树的性质, 除此之外还应具有的性质有:

1. 每一个节点都需着色, 红或黑;
2. 根节点始终着黑色;
3. 每一个空叶子节点都着黑色;
4. 如果一个节点着红色, 则其两个孩子节点着黑色, 也即相邻的两个节点不能同时着红色;
5. 任意节点到其后代空叶子的简单路径上的黑色节点数目都一致.

下面给出红黑树的结构体定义:

struct node{
    int key;
    node* parent;
    char color; 
    node* left;
    node* right;
};

注意: 法无常法, 在于道可.

3. 操作

一个含有 \(n\) 个节点的红黑树, 树高不超过 \(2*log(n+1)\).证明略, 有兴趣的读者可以查阅资料. 这也就是为什么红黑树是一种搜索性能较好的平衡树: 任何情况下, 搜索都可以在 \(O(log\ n)\) 时间内结束.

3.1 旋转

搜索是不会破环第 2 节中关于红黑树定义所描述的性质的, 插入和删除则不然. 同平常的平衡树一样, 在对红黑树上的节点进行操作之后原有性质被破环, 需要进行树的旋转(rotation). 这里还有一个言外之意, 旋转前后的树或者子树保有的性质一致. 下面举个小例子.

图1. 旋转示意

如图1所示, 不论将树结构向左旋还是右旋, 其中序遍历的结果都为: \(a\mbox{-}b\mbox{-}c\mbox{-}d\mbox{-}e\). 结合红黑树的定义, 我们可以给出左旋的代码.

void leftrotate(node *p){
    if (p->right == nullptr)        // 左旋判断右子树是否为空
        return;
    else{
        node *y = p->right;         // 记录右子树的根节点y
        if(y->left != nullptr){     // 判断右子树y的左孩子是否为空, 不为空则,
            p->right = y->left;     // 将右子树y的左孩子挂在节点p的右子树上
            y->left->parent = p;
        }
        else                        // 如果为空, 则
            p->right = nullptr;     // 直接挂空节点

        if(p->parent != nullptr)    // 判断节点p是否为顶层的根节点, 否, 则
            y->parent = p->parent;
        if(p->parent == nullptr)    // 如果节点p是根节点, 则
            root = y;               // p的右子树y就为左旋后的树根

        else{                       // 节点p远离树根
            if(p == p->parent->left)
                p->parent->left = y;
            else
                p->parent->right = y;
        }

        y->left = p;                // 父子节点角色互换
        p->parent = y;
    }
}

右旋的代码不再复制粘贴了:).

3.2 插入&删除

前文已经说明, 红黑树属于搜索树, 所以其插入操作与二叉排序树的搜索插入类似, 关键点在于变色以及根据着色特点进行再平衡即旋转的操作. 根据第二节中所述的红黑树所具有的性质, 可以总结出在插入或者删除之后调整红黑树的策略.

插入

简便起见, 笔者使用流程图与伪代码相结合的方式描述插入(删除)操作的着色和旋转. 插入操作的伪代码如下:

step0: node *t = node_to_insert;
step1: bst_insert(t);
step2: if t==root  then set t->color RED;
        set node *p = t->parent; set node *g = t->parent->parent;
step3: if p->color == RED && t != root then:
        step3.1: if t->uncle->color = RED then:
                p->color = BLACK; t->uncle->color = BLACK; g->color = RED;
                set t = g;
                goto step2;
        step3.2: if t->uncle->color = BLACK then:
                case 1: LL- g->left = p && p->left = t ===> p->color = BLACK; 
                        g->color = RED; rightrotate(g);
                case 2: LR- g->left = p && p->right = t ===> t = p; leftrotate(t); case 1;
                case 3: RR- g->right = p && p->right = t ===> p->color = BLACK; 
                        g->color = RED; leftrotate(g);
                case 4: RL- g->right = p && p->left = t ===> t = p; rightrotate(t); case 3;

图2. 红黑树插入操作流程图

删除

删除操作的伪代码如下:

step0: node *p = node_to_delete;
step1: bst_delete(p);
step2: if p->parent->left == p then s = p->parent->right;
        step2.1: if s->color == red then:
                    s->color = black; p->parent->color = red;
                    leftrotate(p->parent);
                    s = p->parent->right;
        step2.2: if s->right->color == black && s->left->color == black then:
                    s->color = red;
                    p = p->parent;
        step2.3: else 
            step2.3.a: if s->right->color == black then:
                        s->left->color = black;
                        s->color = red;
                        rightrotate(s);
                        s = p->parent->right;
            step2.3.b: s->color = p->parent->color;
                        p->parent->color = black;
                        s->right->color = black;
                        leftrotate(p->parent);
                        p = root;
        step2.4: p->color = black; root->color = black;
                    if p!=root && p->color == black goto step2;
step3: else s = p->parent->left;
        step3.1: if s->color == red then:
                    s->color = black; p->parent->color = red;
                    rightrotate(p->parent);
                    s = p->parent->left;
        step3.2: if s->left->color == black && s->right->color == black then:
                    s->color = red;
                    p = p->parent;
        step3.3: else 
            step3.3.a: if s->left->color == black then:
                        s->right->color = black;
                        s->color = red;
                        leftrotate(s);
                        s = p->parent->right;
            step3.3.b: s->color = p->parent->color;
                        p->parent->color = black;
                        s->left->color = black;
                        rightrotate(p->parent);
                        p = root;
        step3.4: p->color = black; root->color = black;
                    if p!=root && p->color == black goto step2;

图3. 红黑树删除操作流程图

本文仅以流程图和伪代码形式介绍红黑树的插入删除再平衡，未以实际着色图示辅助说明，请读者谅解，未解处请自行查阅资料。

请常读常新。