左偏红黑树稽古 II 红黑树的节点与神乎其技的旋边

Author: sandyzikun

之前讲解了红黑树通过维持“黑高平衡”以实现倍数平衡的原理，但是

维护红黑树的性质是比较复杂的。如果我们要插入一个节点：首先，它一定会被染色成红色，否则会破坏黑高平衡。纵使这样，还有可能会出现连续的两个红色节点。因此需要进行调整。而删除节点就更加麻烦，与插入类似，我们不能删除黑色节点，否则会破坏黑高的平衡。

Intro

为了解决这样的问题，我们引入一个Robert Sedgewick所提出的容易实现的方案：左偏红黑树1（Left-Leaning Red-Black Tree，简称LLRBT，又称左倾红黑树或左斜红黑树）。

在左偏红黑树中有一点与红黑树不同，那便是左偏红黑树中是边具有颜色而非节点具有颜色，但我们为了表示方便，用一条边中的孩子来表示该边的颜色。

左偏红黑树对红黑树进行了进一步限制，一个黑色节点的左右孩子满足以下特征：

  1. 要么全为黑色（即从一个黑色节点延展出两条黑边）；
  2. 要么左孩子为红色而右孩子为黑色。

这两点保证了所有的红边都是左偏的，即红边只会连接某个节点与其左孩子，而不是右孩子。
由此可以看出，这是一种特殊的红黑树，这些新加入的特征对其进行限制，使其增删操作可以与2-3-4树3构成一一对应。
可以通过一下一正一反两个例子来理解这两条特征：

  • 符合条件的情形
  • 不符合条件的情形

Structure

左偏红黑树中，在二叉查找树的结构基础之上，我们将加入一个成员colored以记录某个节点的染色情况。
党colored为真时，我们视这个节点为红色节点，亦即连接其与其母亲节点的边为红边，否则视为黑边。
如此这般便有了左偏红黑树中节点的基本结构：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct Node {
    int val;
    struct Node *parent, *lchild, *rchild;
    bool colored;
} *root;
struct Node * new_node(int _value) {
    // 类比高级语言中的对象构造函数并加以简单封装。
    struct Node * q = (struct Node *)malloc(sizeof(struct Node));
    q->val = _value;
    q->lchild = nullptr;
    q->rchild = nullptr;
    q->parent = nullptr;
    // 在创建节点时预先染红，关于这一点将在后面进行解释。
    q->colored = true;
    return q;
}

Rotation

对于左偏红黑树的节点，旋边时其他的与普通的二叉查找树的旋边操作无异，但需要注意两个节点染色情况的改变。
以左旋为例，原本的孩子会取代母亲的位置，继承其母亲与祖母相连的边的颜色，在表示上便是该点被更新为其母亲的染色情况；而原本的母亲将会被旋转至其孩子的位置，表示该边染色情况的节点从原本的孩子变为旋转成为孩子的母亲，效果上也是继承其孩子的染色情况…右旋也是类似的过程。
如若能够理解以上过程，那么我们可以发现红黑树（不仅是左偏红黑树）的旋边中染色情况的变化可以简单概括为：被旋边两端节点染色情况交换。

  • 左旋 Left Rotate
    • 代码
      C++
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      struct Node * rotate(struct Node *rt) {
          /**
          * Left Rotate an Edge...
          *        [1]               [2]
          *        / \               / \
          *       *  [2]    ==>    [1]  *
          *          / \           / \
          *         O   *         *   O
          */
          Node * newroot = rt->rchild;
          if (newroot != nullptr) {
              // 先进行常规的旋边过程。
              rt->rchild = newroot->lchild;
              newroot->lchild = rt;
              newroot->parent = rt->parent;
              rt->parent = newroot;
              if (rt->rchild != nullptr)
                  rt->rchild->parent = rt;
              // 而后交换两节点染色情况。
              swap(rt->colored, newroot->colored);
              return newroot;
          }
      }
    • 例
      C++
      1
      node = rotate(node);
  • 右旋 Right Rotate
    • 代码
      C++
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      struct Node * rotrev(struct Node *rt) {
          Node * newroot = rt->lchild;
          if (newroot != nullptr) {
              rt->lchild = newroot->rchild;
              newroot->rchild = rt;
              newroot->parent = rt->parent;
              rt->parent = newroot;
              if (rt->lchild != nullptr)
                  rt->lchild->parent = rt;
              swap(rt->colored, newroot->colored);
              return newroot;
          }
      }
    • 例
      C++
      1
      node = rotrev(node);

Flip

红黑树中还有一个重要操作，便是颜色的翻转，其可以使某节点及其左右孩子的染色变为与当前相反的情况。

C++
1
2
3
4
5
inline void flip(struct Node *rt) {
    rt->colored = !(rt->colored);
    rt->lchild->colored = !(rt->lchild->colored);
    rt->rchild->colored = !(rt->rchild->colored);
}

Extra

事实上，红黑树本身就是与2-3-4树等价的，我们可以从nullzx的这篇文章4里这两张图中理解这一点：

由于左偏红黑树不存在右偏的红边，所以可以认为对应的2-3-4树中不存在4-节点，因此可以认为左偏红黑树等价于2-3树：

References

1. OI-Wiki章节 左偏红黑树 ↩
2. Left-Leaning Red-Black Trees, Robert Sedgewick, Princeton University ↩
3. Algorithms - Balanced Search Trees, Robert Sedgewick, Kevin Wayne ↩
4. nullzx的博客园文章 从2-3-4树到红黑树（中） ↩