0%

红黑树学习记录

Posted on Edited on
Symbols count in article: 11k Reading time ≈ 10 mins.

本文记录学习红黑树过程的一些思考

红黑树

前言

在对二叉查找树做插入的过程中，在树的底部插入一个新节点后，由于不知道其余节点的情况，重新平衡实现起来比较复杂。由于树向下生长的过程中很容易造成不平衡，我们可以反过来思考一下，让树向根节点发展，由于根节点每向上生长一级，对应的从根节点到所有叶子节点的距离都同时发生变化，不会产生不一致的情况。所以可以从树的底部插入，然后通过移动节点向根部生长，从而保持树的平衡性，由此引入了2-3查找树。

2-3查找树

一棵平衡的2-3查找树，意味着所有的节点的空链接到根节点的距离是一样的。

2-3 树既有普通二叉树的2-节点（该节点下有两个子节点）也存在3-节点（该结点下有三个子节点），往一个2-节点插入数据后，2-节点变成3-节点，此时树还是平衡的，往一个3-节点插入数据后，3-节点变成了临时的4-节点，可以分解成两个2-节点。

插入一个节点后


这里将一个4-节点分解成为了两个2-节点后，由于会将一个值向父节点传递，所以此时整个树的平衡并没有被打破，但造成的影响是，等价于父节点插入了一个新数据。此时的场景和从底部插入一个数据的情形是一样的。

当节点从树底部插入后，不断向根节点变换，如果最后根节点是一个4-节点，就会被分解成为两个2-节点，从而使整棵树的高度加1.

让我们先从图示出发，看看往一个 2-3 树插入一个节点后，树是如果通过变换来保持基本性质不变的

当我们往图中的2-节点（A、F、M、U）插入一个节点后，对应的节点从 2- 节点变成了一个3- 节点，2-3 树的整体平衡性没有发生改变，树的所有空节点到根节点的距离还是一致的。比如，当我们插入了一个 B后，变成如下

当我们往图中的3-节点(PR)插入一个Q后，3- 节点变成了临时的4- 节点，注意此时所有的空链接到根节点的距离还是一样，由于我们的2-3 树，最多只允许存在3-节点，所以我们需要在保证2-3树平衡性的情况下，将这个4-节点分解成为两个2-节点

我们将这个临时的4-节点进行分解，将其中一个值向他的父节点移动，由于他的父节点是一个2-节点，所以该节点接收一个节点变成一个3-节点后，整棵树重新恢复了平衡。

假如该场景下，父节点也是一个3-节点，在接收子节点传过来的值后，也会变成一个临时4-节点，此时我们需要继续之前的流程，直到找到一个2-节点的父节点为止。如果最终到了根节点都是3-节点，此时只需要对根节点进行一次分解，整棵树的高度+1， 树也就重新恢复了平衡。

综上，我们只需要在树底部插入一个节点后，沿着父路径进行相同的变换，而无需关注其余部分的变化，我们就能够在插入中动态的维持树的平衡。

红黑树

此处如果直接实现上面的操作，我们需要一个结构表示2，3，4节点，或者用不同的数据结构表示不同的节点，而且中间涉及很多的转换过程，实现起来较为复杂，所幸的是，我们只需要在以前实现过的二叉查找树中，将连接父子节点的边加上颜色的属性，（两个节点之间是黑色的链接，就是2-3树中的2-节点，两个节点之间是红色链接，就是2-3树中的3-节点）就可以复用以前的查找逻辑，通过这种方法实现的2-3树就是红黑树。

当我们把红色的链接和节点拉平后，就能达到用二叉树表示的红黑树，如图所示：

为了方便大家理解，对比生产上的红黑树，多加了一些限制，但是原理都是相通的。后续也会对生产中用到的红黑树做一个介绍。

本文所介绍的红黑树的约束如下：

  1. 红链接均为左链接
  2. 空连接视为黑色
  3. 没有任何一个节点同时和两条红链接相连（不存在4-节点）
  4. 该树是完美黑色平衡的，既任意空链接到根节点的路径上的经过的黑链接数量相同

接下来，我们看看如何在红黑树上做操作，来达到和2-3树里面插入的效果

从图中的展示，我们可以这样理解，用红色链接链接起来的两个节点，可以看作是一个2-3节点，即把父子节点当成一个整体来看待，基于这样的理解，我们来完成以下几种操作，其中查找操作和普通的二叉树是一致的。

新节点插入

往上述的红黑树中插入一个新节点分为以下几种情况

2- 节点插入一个新节点。

从上述对2-3树的插入中，我们可以看到，对2-节点的插入，会使得将一个2- 节点变成 3- 节点。这种场景对应红黑树而言，就是红色链接连接的两个节点，组成一个3-节点。所以我们只需要将新节点通过红色链接连接到对应的父节点即可。

2- 节点插入左节点
如图所示，当插入一个新的 H 节点时, 此时刚好是一个左链接，插入后，整个红黑树的性质没有发生变化，此时插入完成。

2- 节点插入右节点
如图所示，当插入一个新的 N 节点.


此时是一个左链接，插入后，违背了我们约定的红链接均为左链接的约束，此时需要做一个变换，进行一”左旋” 操作

由图可知，”左旋”操作是局部变换，不会影响其余部分的平衡性。而且”左旋”操作本身，也不会破坏局部的平衡。经过操作后，可以发现，整棵树重新达到了平衡。

3- 节点顶部插入新节点

如图所示，当插入一个新的 U 节点

此时是一个右连接，插入后，RTU形成了临时的4- 节点，此时需要对该节点进行分解，变化为两个2- 节点，需要执行一个”变色”操作


可以看到，变色本身也是一个局部操作，不会对整体的平衡性造成破坏


此时TVW又变成了一个4-节点，此时场景类似于下面的第4种情况

3- 节点底部插入新节点

如果所示，当插入一个新的 Q 节点

此时是一个左连接，插入后，QRT形成了临时的4- 节点，此时需要对该节点进行分解，由于我们需要把处在中间的值向父节点传递，那首先需要转换局部的父连接指向。先执行一个”右旋”操作

操作完成后，回到了第3种场景，此时再进行一次”变色”操作就可以局部恢复树的平衡
“右旋操作也是一个局部操作” 不会破换整体的平衡性

3- 节点中间插入新节点

如果所示，当插入一个新的 Q 节点

此时是一个右连接，插入后，SRT形成了临时的4- 节点，此时我们先把右红色的右连接换到左边，参照场景2，需要对该节点进行一次”左旋”操作。

此时场景变换成了情景4，再进行一次 “右旋”操作和”变色”操作后，树局部重新恢复平衡

为方便大家理解，这里把整颗树的完整变换流程加以说明
先是进行”变色”操作

通过该操作完成了将4-节点分解为两个 2- 节点，同时向父节点插入了一个节点，SVW形成了临时的 4- 节点，此时相当于在底部插入了一个节点，属于情形4，需要进行一次右旋操作

进行”变色”操作

再进行一次”左旋”操作

综上我们讨论完了红黑树插入的所有场景

插入节点代码实现

通过上面的分析可以知道，无论是在底部插入还是在向上传递的过程中，只要经过有限次操作，就能将树重新归为局部的平衡，而且上述的5种情况存在一定的关联

由此可以组织起我们的插入代码，以下代码片段采用递归的方式实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
template <class T>
class Node
{
public:
    Node(const T &t);
    virtual ~Node();

    T data_;
    Node *left_;
    Node *right_;
    bool color; // 节点颜色为红色表示该节点的父节点指向自身的连接为红连接
};

template <class T>
Node<T> *RedBlackTree<T>::Insert(Node<T> *node, const T &t)
{
    if (node == nullptr)
    {
        node = new Node<T>(t);
        return node;
    }

    if (node->data_ > t)
    {
        node->left_ = Insert(node->left_, t);
    }
    else if (node->data_ < t)
    {
        node->right_ = Insert(node->right_, t);
    }
    else
    {
        return node;
    }
    
    if (Color(node->left_) == BLACK && Color(node->right_) == RED)
    {
        // 进行左旋
        Node<T> *right = node->right_;
        node->right_ = right->left_;
        right->left_ = node;
        right->color = node->color;
        node->color = RED;
        node = right;
    }
    
    if (Color(node->left_) == RED && node->left_->left_ != nullptr && Color(node->left_->left_) == RED)
    {
        // 进行右旋
        Node<T> *left = node->left_;
        node->left_ = left->right_;
        left->right_ = node;
        left->color = node->color;
        node->color = RED;
        node = left;
    }

    if (Color(node->left_) == RED && Color(node->right_) == RED)
    {
        // 变色
        node->left_->color = BLACK;
        node->right_->color = BLACK;
        node->color = RED;
    }

    return node;
}

删除节点

删除一个节点时，我们先来分析一下删除2-节点和3-节点分别会造成什么影响

被删除节点在最底层

如图所示

如果被删除的是2-节点，会打破树的平衡，如果被删除的是3-节点，则不会破坏树的平衡

被删除节点不在最底层

当被删除的节点不在最底层时，参考二叉树的删除方法，我们会将该节点的后继节点替换该节点的值，同时删除该节点的后继节点，以达成删除的效果，在本文讨论的二叉树中，如果一个节点不处在最底层，则他必定有右子节点，否则无法平衡。则对非底层节点的删除，也转换删除被删除节点的右子节点做为根节点的最小值节点，该节点也必定属于底层节点，如图所示

如果对应的后继节点是2-节点，会打破树的平衡，如果被删除的是3-节点，则不会破坏树的平衡

节点变换

为了保证在删除节点后不破坏树的平衡性，我们需要保证节点被删除时，是一个3-节点（或临时4-节点）。
要做到这一点，一个办法是在查询要删除的节点的过程中，把所遇到的全部的2-节点转换为3-节点或者临时4-节点，等删除完节点后，再原路返回，将受影响的节点恢复

我们先来查看查找过程中会存在哪些2-节点的场景，以及需要怎样来做变换

  1. 当前节点的值大于被查找的值，此时下一个被访问的节点是该节点的左子节点，可能情况如下图所示

    由图可知，图中1、2情况遇到的是3-节点，可以无需处理，直接进入下一个访问节点
    如果是图中3、4的场景，遇到的是2-节点，由于该2-节点有可能是要被删除的节点,且假设3、4中的R、T节点是空节点，即此时被删除的节点位于最底层，此时删除会导致树的平衡会被破坏，所以我们要把场景3、4化为3-或4-节点

    对于场景3

    我们可以使用”变色”操作的逆变化，让子节点成为临时的4-节点（注意该变换也不会破换树的整体平衡），此时如果该节点的左子节点不是要删除的节点，则删除后回溯到 V 节点时，重新变换一次 “变色” 操作，则能恢复树的特性。如果该左节点被删除了，4-节点会转变成3-节点，此时也可以通过在回溯V时进行旋转操作恢复。
    此处操作能顺利进行的前提是，V节点本身是红色节点，这点是可以保证的，因为在查找的过程中，我们始终保证当前节点要是一个3-节点（或4-节点）; 如果当前节点是根节点，我们可以忽略他的颜色，或者直接设置为红色

    对于场景4

    如果只是和场景三一样只进行”变色”操作，则会产生由SVXSW组合而成的5-节点，这种节点在后续的回溯过程中，会存在无法通过基本的旋转操作处理还原的问题，所以我们还需要把5-节点做进一步的处理
    为了方便分析当前的场景，我们将他化为2-3查找树来看，方便得到思路

    此时我们需要把5-节点分解，由于需要保证S节点是3-节点，所以需要把W节点向上递交

    所以对应的红黑树的操作，完成”变色”操作后，先进行一次”右旋”,再进行一次”左旋”,最后再次”变色”

    涉及移动相关代码如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    template<class T>
     Node<T>* RedBlackTree<T>::MoveToLeft(Node<T>* node) {
     node->color = BLACK;
     node->left_->color = RED;
     if (node->right_ != nullptr) {
         node->right_->color = RED;
         if (Color(node->right_->left_) == RED) {
             // 先进行一次右旋
             Node<T>* tmp = node->right_->left_;
             node->right_->left_ = tmp->right_;
             tmp->right_ = node->right_;
             tmp->color = node->right_->color;
             node->right_->color = RED;
             node->right_ = tmp;

             // 再进行一次左旋
             Node<T>* l_tmp = node->right_;
             node->right_ = l_tmp->left_;
             l_tmp->left_ = node;
             l_tmp->color = node->color;
             node->color = RED;
             node = l_tmp;

             // 变换颜色
             node->right_->color = BLACK;
             node->left_->color = BLACK;
             node->color = RED;
         }
     }
     return node;
     }

  2. 当前节点的值大于被查找的值，此时下一个被访问的节点是该节点的右子节点，可能情况如下图所示

    由图可知，1 中遇到的是3-节点，可以不用处理，直接进入下一个访问节点

    对于场景2
    我们可以使用”变色”操作的逆变化，让右子节点成为临时的4-节点

    此处操作能狗顺利进行的前提是当前节点必须是红色节点，这点是可以保证的，因为在查找的过程中，我们始终保证当前节点要是一个3-节点（或4-节点），如果当前节点不是红色节点，则不属于场景2

    对于场景3
    通过一次”右旋”操作，变换为场景2或则场景4

    对于场景4
    进行一次”变色”操作后，如图所示，会产生RSVX组成的5-节点

    和左查找类似，我们需要将5-节点分解为3-节点和2-节点，由于要保证VX为3-节点，所以需要进行以下操作
    进行一次”右旋”,然后进行”变色”操作

    由于场景4 产生了红色的右连接，则在向右查找变换的过程中，需要增加右节点为红色节点则继续向下的判断

    涉及移动相关代码如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    template <class T>
    Node<T> *RedBlackTree<T>::MoveToRight(Node<T>* node) {
    // 颜色变化
    node->color = !node->color;
    node->left_->color = !node->left_->color;
    node->right_->color = !node->right_->color;
    if (node->left_ != nullptr && Color(node->left_->left_) == RED) {
        // 进行右旋操作
        Node<T>* tmp = node->left_;
        node->left_ = tmp->right_;
        tmp->right_ = node;
        tmp->color = node->color;
        node->color = RED;
        node = tmp;
        // 将颜色变化恢复过来
        node->color = !node->color;
        node->left_->color = !node->left_->color;
        node->right_->color = !node->right_->color;
    }
    return node;
    }

  3. 当前节点的值等于要被查找的值，此时可以保证当前节点必定是属于3-节点或4-节点的
    场景1
    右子节点为空, 此时正好位于底层

    此时无论被删除的是V还是S，可以直接返回左子节点

    场景2
    右子节点非空, 此时转化为删除以右子节点为根节点的树的最小值问题
    此时如果右子节点为黑色节点，则若被删除的恰好是右子节点，会破坏树的平衡性，同时删除最小值的查找过程中涉及的移动节点的变化也无法满足父节点需要是红色节点的要求。所以我们需要保证执行删除最小值操作前，右子节点也需要是3-节点；此时涉及的情况如下
    被删除的节点是3-或者4-节点的黑色节点

    则通过一次右旋变化后，统一化为被删除节点为3-或4-节点的红色节点
    则将其右节点变化为 3- 节点的操作和当前节点的值大于被查找的值，将右节点化为3-和4-节点一致。

综合以上分析，当前节点的值等于要被查找的值和当前节点的值大于要被查找的值这两种情况，存在相当统一的一致性

删除最小值节点

删除最小值的操作就是不断的向左节点做遍历，同时在过程中保持左节点始终是3-或者临时4- 节点便可，相关情况和上述节点变换保持一致; 相关操作代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
template <class T>
Node<T>* RedBlackTree<T>::DeleteMinInternal(Node<T>* node) {
    if (node->left_ == nullptr) {
        delete node;
        return nullptr;
    }

    if (Color(node->left_) != RED && Color(node->left_->left_) != RED) {
        node = MoveToLeft(node);
    }

    node->left_ = DeleteMinInternal(node->left_);
    if (Color(node->left_) == BLACK && Color(node->right_) == RED) {
        // 进行一次左旋
        Node<T> * tmp = node->right_;
        node->right_ = tmp->left_;
        tmp->left_ = node;
        tmp->color = node->color;
        node->color = RED;
        node = tmp;
    }

    // 正常的插入rebalance 流程
    if (Color(node->left_) == RED && Color(node->left_->left_) == RED) {
        // 右旋
        Node<T> * tmp = node->left_;
        node->left_ = tmp->right_;
        tmp->right_ = node;
        tmp->color = node->color;
        node->color = RED;
        node = tmp;
    }

    if (Color(node->left_) == RED && Color(node->right_) == RED) {
        node->left_->color = BLACK;
        node->right_->color = BLACK;
        node->color = RED;
    }
    return node;
}

回溯恢复节点属性

在删除最小值的时候，有一段在回溯中不断恢复由于节点转移和变换导致的临时 4- 节点和右红色连接，这些操作和插入过程中向上传递恢复过程是一致的。由于不可能同时存在相邻的两个4-节点，也就不会在恢复的过程中产生5-节点，所以通过旋转和变色的操作，我们总能将树恢复平衡

删除节点代码实现

综上讨论，删除的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
template< class T>
Node<T> *RedBlackTree<T>::DeleteInternal(Node<T>* node, const T &t) {
    // 避免找不到
    if (node == nullptr) {
        return node;
    }
 
    if (node->data_ > t) {
        if (Color(node->left_) == BLACK && (node->left_ != nullptr && Color(node->left_->left_) == BLACK)) {
            node = MoveToLeft(node);
        }
        node->left_ = DeleteInternal(node->left_, t);
    } else {
        if (Color(node->left_) == RED) {
            Node<T>* tmp = node->left_;
            node->left_ = tmp->right_;
            tmp->right_ = node;
            tmp->color = node->color;
            node->color = RED;
            node = tmp;
        }

        if (node->data_ == t && node->right_ == nullptr) {
            Node<T>* left = node->left_;
            delete node;
            return left;
        }

        if (Color(node->right_) == BLACK && (node->right_ != nullptr && Color(node->right_->left_) == BLACK)) {
            node = MoveToRight(node);
        }

        if (node->data_ == t) {
            Node<T>* after = node->right_;
            while (after->left_ != nullptr) {
                after = after->left_;
            }
            node->data_ = after->data_;
            node->right_ = DeleteMinInternal(node->right_);
        } else {
            node->right_ = DeleteInternal(node->right_, t);
        }
    }

    // 重新恢复平衡
    if (Color(node->left_) == BLACK && Color(node->right_) == RED) {
        // 左旋
        Node<T>* tmp = node->right_;
        node->right_ = tmp->left_;
        tmp->left_ = node;
        tmp->color = node->color;
        node->color = RED;
        node = tmp;
    }

    if (Color(node->left_) == RED && Color(node->left_->left_) == RED) {
        // 右旋
        Node<T>* tmp = node->left_;
        node->left_ = tmp->right_;
        tmp->right_ = node;
        tmp->color = node->color;
        node->color = RED;
        node = tmp;
    }

    if (Color(node->left_) == RED && Color(node->right_) == RED) {
        node->color = !node->color;
        node->left_->color = !node->left_->color;
        node->right_->color = !node->right_->color;
    }

    return node;
}

生产上使用的红黑树

mysql

用来实现 Innodb 事务ID到事务对象的映射

golang

TreeSet and TreeMap

对应的约束条件为

  1. Every node is either red or black.
  2. All NIL nodes are considered black.
  3. A red node does not have a red child.
  4. Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes.

和我们以上介绍的红黑树区别在于，允许存在右连接为红色，允许黑色节点下挂两个红色节点的这种4-节点存在。整体插入和删除的逻辑会复杂一些，但是核心思想是相通的。
代码实现上，通过一个指向父节点的指针实现了向上回溯，没有使用递归的方式

参考文档

  1. https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Properties
  2. https://algs4.cs.princeton.edu/33balanced/
  3. Robert Sedgewick: Left-leaning Red-Black Trees