红黑树

Apr 7, 2019

红黑树是一种自平衡的二叉搜索树，与AVL树类似，在其上进行的插入、删除、查找操作的平均时间复杂度均为$O(log\,n)$。

但与AVL树不同的是，红黑树的平衡不是非常严格的平衡（即左右子树高度差不超过1），它牺牲了部分平衡性来换取了插入、删除时的少量旋转操作（最多3次）。

与普通二叉搜索树的区别

节点

  • 颜色：相比于普通的二叉搜索树，红黑树的节点增加了一个颜色属性：黑色或红色，这也是红黑树名字的由来。

  • 叶子节点：红黑树特别区分了中间节点与叶子节点。在二叉搜索树中，叶子节点与中间节点一般不做区分，两者的区别仅在于有没有子节点（叶节点子节点为NULL，视为没有子节点）。虽然在红黑树中也可以这样，但是为了方便解释与实现，一般对叶子节点进行了区分：叶子节点不存储数据，只是充当树在此结束的标志。

  • 父指针：因为红黑树的特殊性，在进行平衡调整时，一般都会涉及到父节点与兄弟节点（具体请参见后文），所以在每个节点中都存储了指向其父节点的指针（叶子节点可能例外，参见后文）。

所以红黑树的节点定义如下：

// 枚举节点颜色：只有黑色与红色
enum COLOR { BLACK, RED };

class Node {
  public:
    Node* parent; // 父节点
    Node* left;   // 左子节点
    Node* right;  // 右子节点
    COLOR color;  // 节点颜色
    int val;      // 节点的值
};

5条性质

在普通二叉搜索树的基础上，红黑树的定义增加了以下5条性质：

  1. 节点是黑色或者红色。（即树中任意节点非黑即红，没有其它颜色）
  2. 根节点是黑色。
  3. 所有的叶子节点是黑色。
  4. 每个红色节点一定有两个黑色的节点。（即有父子关系的两个节点不能均为红色）
  5. 从任一节点出发，到其每个叶子节点的所有简单路径上有相同数量的黑节点。（这个黑节点数量也被称为黑高）

基于这5个性质，红黑树能够保证从根节点到叶子节点最长深度不会超过最短深度的2倍，从而保证了红黑树的平衡。

因为最长路径即为红黑交替出现，而最短路径即为全部为黑节点。又由于性质5，所以这两条路径上的黑色节点数目一定相同，根节点与叶节点均为黑色，最长路径上多出的红色节点数目一定不会多于黑色节点的数目。

也正因为红黑树平衡性是通过黑高来进行维护的，所以在其节点上不用存储树的高度。

树的结构

一般情况下，红黑树有以下三种结构（参考《算法导论》）：

  • 所有叶子节点为NULL，在其它节点上存储节点的黑高。如图：
    NULL.png

  • 叶子节点由一个节点实例来代表，并且根节点的父节点也指向此节点，如图：
    Tril.png

  • 每个分支都有一个单独的叶节点实例，如图：
    leaf.png

本文选取第二种结构。

操作

对于二叉搜索树的操作基本上也就是三种：增加、删除、查找。

红黑树上也是一样，其中查找操作与普通的二叉搜索树上相同，此处便不再赘述。下文主要以最麻烦的插入与删除来进行说明。

在此之前，先说明一下文中代码所用的红黑树结构（这里只说明了类中的数据，函数声明与定义请参见文末源码）：

class RedBlackTree {
  private:
    // 枚举节点颜色：只有黑色与红色
    enum COLOR { BLACK, RED };

    class Node {
      public:
        Node* parent; // 父节点
        Node* left;   // 左子节点
        Node* right;  // 右子节点
        COLOR color;  // 节点颜色
        int val;      // 节点的值
    };

    // 叶节点，只有一个实例，其中的值没有意义（默认为0）、其父、左子、右子节点均为nullptr
    Node* leaf;
    // 树的根节点，通过此指针可以得到整颗树
    Node* root;
    // 双黑节点的父节点，只有在删除操作后进行双黑修正时值才有意义，其余情况下均为nullptr
    Node* dBlackParent;
}

插入

先从较为简单的插入操作说起。

总的来说，分为三步：

  • 找到应该插入到树中的哪个位置。
  • 创建新的红色节点并将其插入到树中。
  • 对树进行调整（包括染色与旋转），使其满足红黑树的定义（5条性质）。

红黑树本质上也是一颗二叉搜索树，所以它的插入操作与二叉搜索树一样：先找到应该插入的位置，然后插入。这一部分不必多说。

不同的是，因为红黑树增加了5条性质，在插入后有可能会违反其中一条或几条性质，所以在红黑树上的插入操作多了一步调整。

首先，如果一颗红黑树不为空时，那么性质1、2、3则会自然满足，不用去多加考虑。所以我们只需要保证性质4与性质5便可。

为什么要默认插入红色节点呢？

因为性质5更为复杂（因为只要有某一节点不满足，那么其父节点也不满足，从此节点向上到根节点，路径上的所有节点都会不满足），如果破坏了性质5，再进行恢复所付出的代价也会更大，所以我们在插入时尽量先保证性质5不会被破坏。因此，在进行插入时，我们将新的节点默认为红色。这样，不论此节点被插入到何处，都不会破坏性质5（性质5只与黑色节点有关）。

5种情况

默认为红色的新节点插入到树中后，会出现下面5种情况（为方便讨论，在此假设当前讨论节点为N（在插入后第一次讨论时，N代表新插入的节点）、N的父节点为P、P的兄弟节点为U、N的祖父节点为G（即P的父节点））：

情形1：N就是根节点。

这时我们只需要将此节点重绘为黑色即可。这样，树上的所有节点的黑高都增加了1，性质5得到满足。

void RedBlackTree::InsertCase1(Node* root) {
    // 树为空，直接返回
    if (!root) return;
    // 当前节点为根节点，染黑当前节点并返回
    if (root->parent == leaf) {
        root->color = BLACK;
        return;
    }
    // 否则进入情形2判断
    InsertCase2(root);
}

情形2：P为黑色。

此时性质4没有被破坏，性质5因为插入的是红色节点，也未被破坏。所以此种情况不用调整。

void RedBlackTree::InsertCase2(Node* root) {
    if (root->parent->color == BLACK) return;
    // 否则进入情形3判断
    else
        InsertCase3(root);
}

一个说明：图中三角表示子树，k表示此子树的黑高为k。

情形3：P为红色，B为红色。

我们假设N为P的左子节点，右子节点对称，不进行展开说明，只需要将左右对换即可。

此时我们可以简单地将G重绘为红色，将P与B重绘为黑色。如图：

情形3

此操作只是将G节点的黑色属性下放到了P与B节点，所以此操作不会破坏性质5。并且，此时在以G为根的子树中，性质4也得到了满足。但是此时，有可能G为根节点（违反性质2）或者G的父节点为红色（违反性质4），所以我们需要从情形1开始，对G进行调整讨论。

void RedBlackTree::InsertCase3(Node* root) {
    // 父节点
    Node* p = root->parent;
    // 祖父节点
    Node* g = p->parent;
    // 叔父节点
    // 如果父节点为祖父节点的左子节点，那么叔父节点就应为祖父节点的右子节点，反之亦然
    Node* u = g->left == p ? g->right : g->left;

    // 如果叔父节点为红色（如果叔父节点为叶节点，则不可能为红色）
    if (u->color == RED) {
        // 重绘祖父节点为红色
        g->color = RED;
        // 重绘父节点、叔父节点为黑色
        p->color = BLACK;
        u->color = BLACK;

        // 进行祖父节点的调整
        InsertCase1(g);
    }
    // 进入情形4判断
    else
        InsertCase4(root);
}

又一个说明：在情形4和情形5中，我们假设P为G的左子节点。如果不是，那么进行左右对调即可。

情形4：P为红色，B为黑色（或者缺少，即为叶子节点，合并讨论）且N是P的右子节点。

祖父 - 父 - 当前三者呈“拆线”型。

这种情况下，我们通过对P进行一次左旋转，转化为情形5进行处理。如图：

情形4

经过旋转之后，G的左子树（即原来以P为根的子树，现在以N为根的子树）没有增加新的黑色节点，也就是说，性质5仍然是满足的，只是现在的N和P仍不满足性质4。

void RedBlackTree::InsertCase4(Node* root) {
    // 父节点
    Node* p = root->parent;
    // 祖父节点
    Node* g = p->parent;
    // 叔父节点
    // 如果父节点为祖父节点的左子节点，那么叔父节点就应为祖父节点的右子节点，反之亦然
    Node* u = g->left == p ? g->right : g->left;

    if (p->right == root && g->left == p) {
        RotateL(p);
        InsertCase5(root->left);
    } else if (p->left == root && g->right == p) {
        RotateR(p);
        InsertCase5(root->right);
    } else
        InsertCase5(root);
}

情形5：P为红色，B为黑色（同情形4），且N是P的左子节点。

祖父 - 父 - 当前三者呈“直线”型。

此时我们对G进行右旋转，并交换P与G的颜色（将G染红、P染黑）。如图：
情形5

此时，对于经过G的所有路径，现在仍通过一个黑色的节点：P，黑高不变；经过B的所有路径，虽然多经过了G节点，但是G现在为红色，所以黑高也没有发生变化。所以在这个子树上，所有节点的黑高都没有发生变化，都满足性质5，同时调整之后，也满足性质4。调整完成。

void RedBlackTree::InsertCase5(Node* root) {
    // 父节点
    Node* p = root->parent;
    // 祖父节点
    Node* g = p->parent;
    // 叔父节点
    // 如果父节点为祖父节点的左子节点，那么叔父节点就应为祖父节点的右子节点，反之亦然
    Node* u = g->left == p ? g->right : g->left;

    if (p->left == root && g->left == p)
        RotateR(g);
    else
        RotateL(g);
    g->color = RED;
    p->color = BLACK;
}

删除

删除操作也分为四步：

  • 在树中找到待删除元素。
  • 如果待删除元素有两个子节点，找到其前驱节点，并交换两个节点的值，将前驱节点标记为真正要删除的节点。
  • 删除节点。
  • “双黑”修正。

前面三步与普通的二叉搜索树相同，将删除问题转化成了删除最多只有一个子节点的情况。所以下面的讨论也基于被删除的节点最多只有一个子节点。

所不同的在于最后一步：“双黑”修正。这也是删除操作（甚至是红黑树中）最为复杂的一步。

注：在下面的讨论中，节点没有子节点意为节点的左、右子节点均指向唯一的叶节点。

删除节点的三种情况

为方便讨论，我们假设被删除的节点为T、当前讨论的节点为N（第一次讨论时，N为被删除节点的子节点）、X的父节点为P、X的兄弟节点为B、B的左子节点为$\mathrm{B_L}$、B的右子节点为$\mathrm{B_R}$。

  • T为红色。此时，T一定没有子节点。根据性质4，如果T有一个子节点N，那么N一定是黑色，则此时经过N的黑高一定大于1，不经过此子节点的黑高为1，违反性质5。

    这种情况下，直接删除即可，用叶节点做为P的子节点。

  • T为黑色，但有一个红色子节点N。此时，N一定没有子节点。如上一种情况，要保证经过N的黑高为1，那么它就不能有子节点。

    这种情况下，直接删除，用N做为P的子节点，并将N染成黑色。这样，原来经过P的路径的黑高为2，现在删除了一个黑色节点（X），又增加了一个黑色节点（染色后的N），经过现在N的路径的黑高仍为2，黑高没有变化。

  • T为黑色，且其没有红色子节点。那么此时，T一定没有子节点，因为如果N为黑色，那么经过N的路径与不经过N的路径（黑高为1）黑高不等，违反性质5。

    这种情况下，如果将T直接删除，那么则会原来经过T的路径的黑高也就会减少1，破坏性质5，需要进行调整。这就是所谓的“双黑”修正。

“双黑”修正

什么是“双黑”呢，顾名思义，就是有两个黑色：一个节点被染上了两个黑色。

这样做的目的其实是为了简化讨论，如上面所说，T为黑色且没有子节点的时候，删除T会导致经过T的路径上的黑高减少1，那么我们就给P增加一个黑色子节点（因为P此时应该指向叶节点，这个子节点就是叶节点），但是又不能破坏原来的结构，所有可以假设在这个黑色子节点上有两个黑色，这样黑高就满足性质5了。这就是“双黑”。

而修正就比较好理解了，因为真实情况下一个节点不可能有两个黑色（那样就太非了(￣▽￣)”），所以我们要对树进行调整，去掉这个“双黑”节点。

具体去除方法有6种情况。

在此这前，先做一些说明：

  • 节点假设与上一节相同，只是现在X已经被删除，N代替了X现在的位置，相应的，B成了N的兄弟节点，P成了N的父节点，当前讨论的节点N就是要进行修正的“双黑”节点。
  • 另外，假设N为P的左子节点。如果不是，则在相应的情形（2、5、6）下进行左右对调。
  • 与插入类似，“双黑”修正时也会进行回溯，所以在讨论时会以一般情况进行讨论。
  • 关于N的子树，如果在第一次讨论时，N本身即为叶子节点，所以N的子树是不存在的，图片中所画为一般情况。同样的，对于B的子树也是类似的。
  • 因为在进行调整时，会去取N的父节点P，但如果N为叶子节点，那么其父节点是被设置为nullptr的，所以为了便于讨论，在树的结构中存储了N的父节点：dBlackParent，并且在讨论时进行更新维护。

“双黑”修正的思路

怎么去除“双黑”节点呢？

最容易想到的办法就是把B给染红。这样，对于P而言，左子树上去除了一个黑色节点，右子树上也去掉了一个黑色节点，这样“双黑”就在以P为根的子树上去除了，然后向上传递，再讨论P…

但问题就在于，B不是说染红就染的。万一它就是红的呢？万一P是红的呢？万一B的子节点有红的呢？

我们的目标就是要将B转化为可以染红。

情形1：N为树的根

如果是第一次讨论时，N为叶子节点，则代表删除的节点X是原来树的根，删除之后树为空。

如果是回溯的讨论，那么“双黑”性质传递到了根节点，则无需更改就可以消除“双黑”。此时相当于所有路径都去除了一个黑色节点，所有节点的黑高都减少1，满足性质5。

// 删除节点为根节点
if (t == root) {
    // 删除根节点
    delete root;
    // 根节点置空，便于再进行插入
    root = nullptr;
    return 1;
}

void RedBlackTree::RemoveCase1(Node* root) {
    // 双黑节点为新的根节点，直接返回
    if (dBlackParent == leaf) return;
    // 否则进入情形2的判断
    RemoveCase2(root);
}

情形2：B为红色

此时，P为黑色，$\mathrm{B_L}$、$\mathrm{B_R}$均为黑色。

我们对P进行左旋转，然后交换P和B的颜色。如图：
双黑情形2

虽然我们现在没有直接解决“双黑”的问题，但是通过此次旋转与染色，现在N有了一个红色的父节点与一个黑色的兄弟节点，此时“双黑”节点仍为N，进行情形4的判断。

void RedBlackTree::RemoveCase2(Node* root) {
    // 兄弟节点
    Node* b =
        dBlackParent->left == root ? dBlackParent->right : dBlackParent->left;

    // 情形2处理的情况
    if (b->color == RED) {
        b->color = BLACK;
        // 将父节点重绘为红色
        dBlackParent->color = RED;
        // 以父节点为根旋转
        if (dBlackParent->left == root)
            RotateL(dBlackParent);
        else
            RotateR(dBlackParent);
        // 进入情形4的判断
        RemoveCase4(root);
    }
    // 不是情形2进入情形3的判断
    else
        RemoveCase3(root);
}

情形3：P、S、$\mathrm{B_L}$、$\mathrm{B_R}$均为黑色

此时，就可以直接将B染红。

在以P为根的子树内，“双黑”成功去除。但是这样操作后，通过P的路径上的节点比不通过P的路径上的节点的黑高都少1，也就是说，现在“双黑”性质转移到了P，我们再对P从情形1开始讨论。如图：
删除情形3

void RedBlackTree::RemoveCase3(Node* root) {
    // 兄弟节点
    Node* b =
        dBlackParent->left == root ? dBlackParent->right : dBlackParent->left;

    // 情形3处理的情况
    if (dBlackParent->color == BLACK && b->color == BLACK &&
        b->left->color == BLACK && b->right->color == BLACK) {
        // 重绘兄弟节点为红色
        b->color = RED;
        // 双黑向上传递
        root = dBlackParent;
        dBlackParent = dBlackParent->parent;
        // 从情形1开始判断父节点
        RemoveCase1(root);
    }
    // 不是情形3进入情形4的判断
    else
        RemoveCase4(root);
}

情形4：P为红色，S、$\mathrm{B_L}$、$\mathrm{B_R}$均为黑色

此时，先染黑P，再染红B。

这样，我们就将N上两份黑色分了一份给P，所以经过N的路径的节点的黑高保持了不变。

并且，我们达到了目标，可以直接将B染红。染红B后，经过B的路径的节点的黑高都减少了1（因为P染黑又增加了1，所以与原来相同）。如图：
删除情形4

void RedBlackTree::RemoveCase4(Node* root) {
    // 兄弟节点
    Node* b =
        dBlackParent->left == root ? dBlackParent->right : dBlackParent->left;

    if (dBlackParent->color == RED && b->color == BLACK &&
        b->left->color == BLACK && b->right->color == BLACK) {
        // 交换兄弟节点和父节点的颜色
        b->color = RED;
        dBlackParent->color = BLACK;
    }
    // 不是情形4进入情形5的判断
    else
        RemoveCase5(root);
}

情形5：B为黑色，$\mathrm{B_L}$为红色、$\mathrm{B_R}$为黑色

此时，我们对B进行右旋转，再交换$\mathrm{B_L}$与B的颜色。转化为情形6。

此操作不会对N与P产生影响，但是现在N的兄弟节点为黑色，并且它有一个红色的右子节点。

并且此次操作对于原来经过B的路径的节点的黑高没有变化。如图：

删除情形5

void RedBlackTree::RemoveCase5(Node* root) {
    // 兄弟节点
    Node* b =
        dBlackParent->left == root ? dBlackParent->right : dBlackParent->left;

    // 当前节点为父节点的左子节点、兄弟节点为黑色、兄弟节点的左子节点为红色、兄弟节点的右子节点为黑色
    if (dBlackParent->left == root && b->left->color == RED &&
        b->right->color == BLACK) {
        RotateR(b);
    }
    // 与上类似，只是左右对调
    else if (dBlackParent->right == root && b->right->color == RED &&
             b->left->color == BLACK) {
        RotateL(b);
    }

    // 进入情形6的处理
    RemoveCase6(root);
}

情形6：S为黑色、$\mathrm{B_R}$为黑色

此时，对P进行左旋转，然后交换P和B的颜色并染黑$\mathrm{B_R}$。

如图：
删除情形6

此时会有两种情况：

  • P为黑色时：操作后的B应为红色，那么从P到叶子节点的黑高为k + 2，操作之后仍为k + 2。
  • P为红色时：操作后的B应为黑色，那么从P到叶子节点的黑高为k + 2，操作之后仍为k + 2。

并且从图中可以看出，并没有违反性质4，所以“双黑”节点消失。修正完成。

附注

  • 文中完整源代码请参见我的Github：RedBlackTree。

参考：