MENU

红黑树

June 5, 2018 • 文章

一:背景

红黑树(英语:Red–Black Tree,简称 RB-Tree)是一种平衡的二叉查找树,用途广泛。例如:

  • Java 中的:java.util.TreeMap,java.util.TreeSet;
  • C++ STL 中的:map,multimap,multiset。

它是在 1972 年由 Rudolf Bayer 发明的,他称之为 “对称二叉 B 树”,它现代的名字(即 ”红黑树“)是 Leo J. Guibas 和 Robert Sedgewick 于 1978 年写的一篇论文中获得的。

红黑树的实现比较复杂,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的,它可以在 $O(logn)$ 时间内做查找,插入和删除操作。

红黑树有四个性质(也有书籍和博客上说是五个性质,其实四个性质足矣):

  1. 每个结点要么是红的,要么是黑的;
  2. 根结点是黑色的;
  3. 如果一个结点是红色的,则它的两个孩子都是黑色的;
  4. 对于任意一个结点,其到叶子结点的每条路径上都包含相同数目的黑色结点。

红黑树的实现和理解还是很复杂的,所以建议读者在阅读本文前,最好已经理解和掌握了 二叉查找树AVL 树

二:具体实现与代码分析

和 AVL 树通过约束左右子树高度不同,红黑树是通过它的四条性质来实现 “平衡状态”,在插入结点或者删除结点时,可能会造成某个结点违反了上述的某条性质,那么红黑树的做法就是通过 “重新着色” 和 “旋转” 两种方式使之重新符合性质。

“重新着色” 这很简单,现在来看下 “旋转” 是怎么旋转的。一共有两种旋转方式:左旋和右旋。

左旋

void RBTree::rotate_left(Node* x)
{
    Node* y = x->right;

    x->right = y->left;
    if (y->left)
        y->left->parent = x;
    y->parent = x->parent;

    if (x == root)
        root = y;
    else if (x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;

    y->left = x;
    x->parent = y;
}

右旋

void RBTree::rotate_right(Node* x)
{
    Node* y = x->left;

    x->left = y->right;
    if (y->right)
        y->right->parent = x;
    y->parent = x->parent;

    if (x == root)
        root = y;
    else if (x == x->parent->right)
        x->parent->right = y;
    else
        x->parent->left = y;

    y->right = x;
    x->parent = y;
}

很容易看出,左旋和右旋其实就是两个镜像操作而已。

好了,真是千呼万唤始出来,重点终于来了!

2.1 插入操作

将红黑树当作一颗二叉查找树,将结点插入,插入后,该树仍然是一棵二叉查找树,但是它可能已经不是红黑树了,所以接下来就要通过 “旋转” 和 “重新着色” 来使它重新成为红黑树。

首先,我们把新插入的结点着色为红色。为什么偏偏是红色呢?先回顾下红黑树的四条性质:

  1. 每个结点要么是红的,要么是黑的;
  2. 根结点是黑色的;
  3. 如果一个结点是红色的,则它的两个孩子都是黑色的;
  4. 对于任意一个结点,其到叶子结点的每条路径上都包含相同数目的黑色结点。

将插入的结点着色为红色,不会违背 “性质4”。而少违背一条性质,就意味着我们需要处理的情况越少。

接着,我们再来看看插入结点会遇到哪几种情况,分析发现,一共有三种:

  1. 被插入结点是根结点,那我们把此结点涂为黑色就行了;
  2. 被插入结点的父亲结点是黑色的,那么什么也不需要做,结点被插入后,仍然是红黑树。
  3. 被插入结点的父亲结点是红色的,那么此时是违背 “性质 3” 的,需要调整。

那么,如何调整呢?分析一下,此种情况,被插入结点是一定存在祖父(即父亲的父亲)结点的,且可以进一步再划分为 6 种情况,因为涉及到镜像操作,所以我们只需理解其中一边镜像的 3 种情况即可。

为方便叙述,我们把 “新插入结点” 称为 “当前结点”,那么 “当前结点” 的父亲的父亲就叫做 “祖父结点”,而 “祖父结点” 如果还有一个儿子的话,我们就称其为 “叔叔结点”。

  • Case 1 :当前结点的父亲是红色,叔叔存在且也是红色

    图中,“结点 1” 为 “当前结点”。那么我们的处理策略就是:

    • 将 “父亲结点” 改为黑色;
    • 将 “叔叔结点” 改为黑色;
    • 将 “祖父结点” 改为红色;
    • 将 “祖父结点” 设为 “当前结点”,继续进行操作。

处理完后,图中显示的两条路径上,黑色结点数相同且和原图数目一致。

  • Case 2:当前结点的父亲是红色,叔叔不存在或是黑色,且当前结点是其父亲的右孩子

    图中,“结点 2” 为 “当前结点”。那么我们的处理策略就是:

    • 将 “父亲结点” 设为 “当前结点”;
    • 以新的 “当前结点” 为支点进行左旋。

处理完后,我们发现依旧不满足红黑树的性质,别急,这就是 “Case 3”。

  • Case 3:当前结点的父亲是红色,叔叔不存在或是黑色,且当前结点是其父亲的左孩子

    图中,“结点 1” 为 “当前结点”。那么我们的处理策略就是:

    • 将 “父亲结点” 改为黑色;
    • 将 “祖父结点” 改为红色;
    • 以 “祖父结点” 为支点进行右旋。

处理完后,图中显示的两条路径上,黑色结点数相同且和原图数目一致。

代码如下:

void RBTree::insert_rebalance(Node* x)
{
    x->color = red;

    while (x != root && x->parent->color == red)
    {
        if (x->parent == x->parent->parent->left)
        {
            Node* y = x->parent->parent->right;

            if (y && y->color == red)           /* Case 1 */
            {
                x->parent->color = black;
                y->color = black;
                x->parent->parent->color = red;
                x = x->parent->parent;
            }
            else
            {
                if (x == x->parent->right)      /* Case 2 */
                {
                    x = x->parent;
                    rotate_left(x);
                }

                x->parent->color = black;       /* Case 3 */
                x->parent->parent->color = red;
                rotate_right(x->parent->parent);
                break;
            }
        }
        else  /* left <-> right */
        {
            Node* y = x->parent->parent->left;

            if (y && y->color == red)
            {
                x->parent->color = black;
                y->color = black;
                x->parent->parent->color = red;
                x = x->parent->parent;
            }
            else
            {
                if (x == x->parent->left)
                {
                    x = x->parent;
                    rotate_right(x);
                }

                x->parent->color = black;
                x->parent->parent->color = red;
                rotate_left(x->parent->parent);
                break;
            }
        }
    }

    root->color = black;
}

Node* RBTree::insert(int key)
{
    if (root == nullptr)
    {
        root = new Node(key);
        root->color = black;
        return root;
    }

    Node* cur = root;
    Node* pre = nullptr;

    while (cur)
    {
        pre = cur;
        if (key < cur->key)
            cur = cur->left;
        else if (key > cur->key)
            cur = cur->right;
        else
            return nullptr; /* 不可重复插入 */
    }

    cur = new Node(key);
    cur->parent = pre;

    if (key < pre->key)
        pre->left = cur;
    else
        pre->right = cur;

    insert_rebalance(cur);

    return cur;
}

2.2 删除操作

首先,和删除一棵普通二叉查找树的结点相同,我们会遇到三种情况:

  1. “被删结点” 没有孩子,如果它是红色的,那么可以直接删除;如果是黑色的,这点比较特殊,读者直接跟读代码就可以理解,很简单;
  2. “被删结点” 只有一个孩子,那么删除该结点后,用这个孩子去替换它即可;
  3. “被删结点” 有两个孩子,那么先找出它的 “后继结点”,然后用 “后继结点” 去替换 “被删结点”,把问题转化为删除 “后继结点” ,也就是说, “后继结点” 才是真正的 “被删结点”。

为方便接下来的叙述,我们把 “被删结点” 称为 “原先结点”,而用来替换 “被删结点” 的结点称为 “当前结点”。

接着,我们来看看 “原先结点” 被删掉后,会遇到哪几种情况,分析发现,一共有四种:

  1. “原先结点” 为黑色,“当前结点” 为红色,那么我们把 “原先结点” 删掉后,拿 “当前结点” 去替换它,并修改颜色为黑色即可;
  2. “原先结点” 为黑色,“当前结点” 为黑色,这种情况比较复杂,待会再说;
  3. “原先结点” 为红色,“当前结点” 为红色,那么我们把 “原先结点” 删掉后,直接拿“当前结点” 去替换它即可;
  4. “原先结点” 为红色,“当前结点” 为黑色,这和 “情况 3” 一样,直接拿“当前结点” 去替换它即可。

最后,我们只需看下上述的 “情况 2”。这种情况可以进一步再划分为 8 种情况,因为涉及到镜像操作,所以我们只需理解其中一边镜像的 4 种情况即可(注意,下面的图片上,“原先结点” 已被删除,故未画出,我们只画出了 “当前结点” ):

  • Case 1:当前结点是黑色,兄弟结点是红色

    “结点 1” 为 “当前结点”。观察上图,因 “原先结点” 已被删除,故路径2->1上少了一个黑色结点(右侧路径的黑色结点未画完全),那么我们的处理策略就是:

    • 将 "兄弟结点" 改为黑色;
    • 将 "父亲结点" 改为红色;
    • 以 "父亲结点" 为支点进行左旋;
    • 左旋后,重新设置 "兄弟结点"。

处理完后,我们发现路径2->1上依旧是 2 个黑色结点,说明当前状态并不满足红黑树性质。其实,这是进入了下面的 Case 2,Case 3,和 Case 4 阶段了,请继续往下看。

  • Case 2:当前结点是黑色,兄弟结点是黑色,两个孩子为空或是黑色

    "结点 1" 为 “当前节点”。观察上图,因 “原先结点” 已被删除,故路径2->1上少了一个黑色结点,那么我们的处理策略就是:

    • 将 “兄弟结点” 改为红色;
    • 将 “父亲结点” 设置为新的 “当前结点”,继续进行操作。

处理完后,我们发现路径2->1上还是只有 1 个黑色结点,且有两个红色结点相连,说明当前状态不满足红黑树性质,但是我们发现只要把 “结点 2” 着色为黑色不就行了么,这也就是erase_rebalance()代码最后出现if(x) x->color = black;的缘由之一(x指向的是 “当前结点”)。

  • Case 3:当前结点是黑色,兄弟结点是黑色,兄弟结点的左孩子是红色,右孩子为空或是黑色

    “结点 1” 为 “当前结点”。观察上图,因 “原先结点” 已被删除,故路径2->1上少了一个黑色结点,那么我们的处理策略就是:

    • 将 “兄弟结点” 的左孩子改为黑色;
    • 将 “兄弟结点” 改为红色;
    • 以 “兄弟结点” 为支点进行右旋;
    • 右旋后,重新设置 “当前结点” 的 “兄弟结点”。

处理完后,我们发现图中2->1上还是只有 1 个黑色结点,说明当前状态不满足红黑树性质。其实这是进入了Case 4。

  • Case 4:当前结点是黑色,兄弟结点是黑色,兄弟结点的右孩子是红色,左孩子为空或红黑皆可

    “结点 1” 为 “当前结点”。观察上图,因 “原先结点” 已被删除,故路径2->1上少了一个黑色结点,那么我们的处理策略就是:

    • 将 “父亲结点” 的颜色赋给 “兄弟结点”;
    • 将 “父亲结点” 改为黑色;
    • 将 “兄弟结点” 的右孩子改为黑色;
    • 以 “父亲结点” 为支点进行左旋;

处理完后,一切 OK。

代码如下:

void RBTree::erase_rebalance(Node* z)
{
    Node* y = z;
    Node* x = nullptr;
    Node* x_parent = nullptr;

    if (y->left == nullptr)
        x = y->right;
    else if (y->right == nullptr)
        x = y->left;
    else /* 结点 z 的孩子都存在 */
    {
        y = y->right;
        while (y->left)
            y = y->left; /* 找到后继结点 */

        x = y->right;
    }

    /* y != z 说明结点 z 的孩子都存在 */
    if (y != z)
    {
        z->left->parent = y;
        y->left = z->left;

        if (y != z->right)
        {
            x_parent = y->parent;
            if (x)
                x->parent = y->parent;
            y->parent->left = x;
            y->right = z->right;
            z->right->parent = y;
        }
        else
            x_parent = y;

        if (root == z)
            root = y;
        else if (z->parent->left == z)
            z->parent->left = y;
        else
            z->parent->right = y;

        y->parent = z->parent;
        swap(y->color, z->color);
        y = z;
    }
    else
    {
        x_parent = y->parent;
        if (x)
            x->parent = y->parent;

        if (root == z)
            root = x;
        else if (z->parent->left == z)
            z->parent->left = x;
        else
            z->parent->right = x;
    }
    
    /* 
    经过上边的处理,y 指向真正要删除的结点(即文中所定义的 “原先结点”);x 为 y 的左孩子
    或右孩子(也可能为空),作为结点 y 被删除后的替补结点(即文中所定义的 “当前结点”)。
    */

    if (y->color == black)
    {
        if (x != root && (x == nullptr || x->color == black))
        {
            if (x == x_parent->left)
            {
                Node* w = x_parent->right;

                if (w->color == red)                                     /* Case 1 */
                {
                    w->color = black;
                    x_parent->color = red;
                    rotate_left(x_parent);
                    w = x_parent->right;
                }

                if ((w->left == nullptr || w->left->color == black) &&   /* Case 2 */
                    (w->right == nullptr || w->right->color == black))
                {
                    w->color = red;
                    x = x_parent;
                    x_parent = x_parent->parent;
                }
                else
                {
                    if (w->right == nullptr || w->right->color == black) /* Case 3 */
                    {
                        if (w->left)
                            w->left->color = black;
                        w->color = red;
                        rotate_right(w);
                        w = x_parent->right;
                    }

                    w->color = x_parent->color;                          /* Case 4 */
                    x_parent->color = black;
                    if (w->right)
                        w->right->color = black;
                    rotate_left(x_parent);
                }
            }
            else  /* left <-> right */
            {
                Node* w = x_parent->left;

                if (w->color == red)
                {
                    w->color = black;
                    x_parent->color = red;
                    rotate_right(x_parent);
                    w = x_parent->left;
                }

                if ((w->right == nullptr || w->right->color == black) &&
                    (w->left == nullptr || w->left->color == black))
                {
                    w->color = red;
                    x = x_parent;
                    x_parent = x_parent->parent;
                }
                else
                {
                    if (w->left == nullptr || w->left->color == black)
                    {
                        if (w->right)
                            w->right->color = black;
                        w->color = red;
                        rotate_left(w);
                        w = x_parent->left;
                    }

                    w->color = x_parent->color;
                    x_parent->color = black;
                    if (w->left)
                        w->left->color = black;
                    rotate_right(x_parent);
                }
            }
        }

        if (x)
            x->color = black;
    }
}

void RBTree::erase(int key)
{
    Node* z = find(key);

    if (z)
    {
        erase_rebalance(z);
        delete z;
    }
}

三:完整代码

#include <iostream>
#include <algorithm>

using namespace std;

enum { red = 0, black = 1 };

struct Node
{
    int key;
    bool color;
    Node* parent;
    Node* left;
    Node* right;
    Node(int key = 0)
    {
        this->key = key;
        this->color = red;
        this->parent = this->left = this->right = nullptr;
    }
};

class RBTree
{
private:
    Node* root;

private:
    void rotate_left(Node* x);
    void rotate_right(Node* x);
    void destroy(Node* node);
    void insert_rebalance(Node* x);
    void erase_rebalance(Node* z);
    void in_order(Node* node);

public:
    RBTree();
    ~RBTree();
    Node* insert(int key);
    Node* find(int key);
    void erase(int key);
    void print();
};

RBTree::RBTree()
{
    root = nullptr;
}

void RBTree::destroy(Node* node)
{
    if (node == nullptr)
        return;

    destroy(node->left);
    destroy(node->right);
    delete node;
}

RBTree::~RBTree()
{
    destroy(root);
    root = nullptr;
}

void RBTree::rotate_left(Node* x)
{
    Node* y = x->right;

    x->right = y->left;
    if (y->left)
        y->left->parent = x;
    y->parent = x->parent;

    if (x == root)
        root = y;
    else if (x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;

    y->left = x;
    x->parent = y;
}

void RBTree::rotate_right(Node* x)
{
    Node* y = x->left;

    x->left = y->right;
    if (y->right)
        y->right->parent = x;
    y->parent = x->parent;

    if (x == root)
        root = y;
    else if (x == x->parent->right)
        x->parent->right = y;
    else
        x->parent->left = y;

    y->right = x;
    x->parent = y;
}

Node* RBTree::find(int key)
{
    Node* z = root;

    while (z)
    {
        if (key < z->key)
            z = z->left;
        else if (key > z->key)
            z = z->right;
        else
            return z;
    }

    return z;
}

void RBTree::insert_rebalance(Node* x)
{
    x->color = red;

    while (x != root && x->parent->color == red)
    {
        if (x->parent == x->parent->parent->left)
        {
            Node* y = x->parent->parent->right;

            if (y && y->color == red)           /* Case 1 */
            {
                x->parent->color = black;
                y->color = black;
                x->parent->parent->color = red;
                x = x->parent->parent;
            }
            else
            {
                if (x == x->parent->right)      /* Case 2 */
                {
                    x = x->parent;
                    rotate_left(x);
                }

                x->parent->color = black;       /* Case 3 */
                x->parent->parent->color = red;
                rotate_right(x->parent->parent);
                break;
            }
        }
        else  /* left <-> right */
        {
            Node* y = x->parent->parent->left;

            if (y && y->color == red)
            {
                x->parent->color = black;
                y->color = black;
                x->parent->parent->color = red;
                x = x->parent->parent;
            }
            else
            {
                if (x == x->parent->left)
                {
                    x = x->parent;
                    rotate_right(x);
                }

                x->parent->color = black;
                x->parent->parent->color = red;
                rotate_left(x->parent->parent);
                break;
            }
        }
    }

    root->color = black;
}

Node* RBTree::insert(int key)
{
    if (root == nullptr)
    {
        root = new Node(key);
        root->color = black;
        return root;
    }

    Node* cur = root;
    Node* pre = nullptr;

    while (cur)
    {
        pre = cur;
        if (key < cur->key)
            cur = cur->left;
        else if (key > cur->key)
            cur = cur->right;
        else
            return nullptr; /* 不可重复插入 */
    }

    cur = new Node(key);
    cur->parent = pre;

    if (key < pre->key)
        pre->left = cur;
    else
        pre->right = cur;

    insert_rebalance(cur);

    return cur;
}

void RBTree::erase_rebalance(Node* z)
{
    Node* y = z;
    Node* x = nullptr;
    Node* x_parent = nullptr;

    if (y->left == nullptr)
        x = y->right;
    else if (y->right == nullptr)
        x = y->left;
    else /* 结点 z 的孩子都存在 */
    {
        y = y->right;
        while (y->left)
            y = y->left; /* 找到后继结点 */

        x = y->right;
    }

    /* y != z 说明结点 z 的孩子都存在 */
    if (y != z)
    {
        z->left->parent = y;
        y->left = z->left;

        if (y != z->right)
        {
            x_parent = y->parent;
            if (x)
                x->parent = y->parent;
            y->parent->left = x;
            y->right = z->right;
            z->right->parent = y;
        }
        else
            x_parent = y;

        if (root == z)
            root = y;
        else if (z->parent->left == z)
            z->parent->left = y;
        else
            z->parent->right = y;

        y->parent = z->parent;
        swap(y->color, z->color);
        y = z;
    }
    else
    {
        x_parent = y->parent;
        if (x)
            x->parent = y->parent;

        if (root == z)
            root = x;
        else if (z->parent->left == z)
            z->parent->left = x;
        else
            z->parent->right = x;
    }
    
    /* 
    经过上边的处理,y 指向真正要删除的结点(即文中所定义的 “原先结点”);x 为 y 的左孩子
    或右孩子(也可能为空),作为结点 y 被删除后的替补结点(即文中所定义的 “当前结点”)。
    */

    if (y->color == black)
    {
        if (x != root && (x == nullptr || x->color == black))
        {
            if (x == x_parent->left)
            {
                Node* w = x_parent->right;

                if (w->color == red)                                     /* Case 1 */
                {
                    w->color = black;
                    x_parent->color = red;
                    rotate_left(x_parent);
                    w = x_parent->right;
                }

                if ((w->left == nullptr || w->left->color == black) &&   /* Case 2 */
                    (w->right == nullptr || w->right->color == black))
                {
                    w->color = red;
                    x = x_parent;
                    x_parent = x_parent->parent;
                }
                else
                {
                    if (w->right == nullptr || w->right->color == black) /* Case 3 */
                    {
                        if (w->left)
                            w->left->color = black;
                        w->color = red;
                        rotate_right(w);
                        w = x_parent->right;
                    }

                    w->color = x_parent->color;                          /* Case 4 */
                    x_parent->color = black;
                    if (w->right)
                        w->right->color = black;
                    rotate_left(x_parent);
                }
            }
            else  /* left <-> right */
            {
                Node* w = x_parent->left;

                if (w->color == red)
                {
                    w->color = black;
                    x_parent->color = red;
                    rotate_right(x_parent);
                    w = x_parent->left;
                }

                if ((w->right == nullptr || w->right->color == black) &&
                    (w->left == nullptr || w->left->color == black))
                {
                    w->color = red;
                    x = x_parent;
                    x_parent = x_parent->parent;
                }
                else
                {
                    if (w->left == nullptr || w->left->color == black)
                    {
                        if (w->right)
                            w->right->color = black;
                        w->color = red;
                        rotate_left(w);
                        w = x_parent->left;
                    }

                    w->color = x_parent->color;
                    x_parent->color = black;
                    if (w->left)
                        w->left->color = black;
                    rotate_right(x_parent);
                }
            }
        }

        if (x)
            x->color = black;
    }
}

void RBTree::erase(int key)
{
    Node* z = find(key);

    if (z)
    {
        erase_rebalance(z);
        delete z;
    }
}

void RBTree::in_order(Node* node)
{
    if (node == nullptr)
        return;

    in_order(node->left);
    cout << "( " << node->key << ", " << node->color << " )" << endl;
    in_order(node->right);
}

void RBTree::print()
{
    in_order(root);
    cout << endl;
}

int main()
{
    cout << "red: " << red << ", black: " << black << endl << endl;

    RBTree rb_tree;

    /* test "insert" */
    rb_tree.insert(7);
    rb_tree.insert(2);
    rb_tree.insert(1); rb_tree.insert(1);
    rb_tree.insert(5);
    rb_tree.insert(3);
    rb_tree.insert(6);
    rb_tree.insert(4);
    rb_tree.insert(9);
    rb_tree.insert(8);
    rb_tree.insert(11); rb_tree.insert(11);
    rb_tree.insert(10);
    rb_tree.insert(12);
    rb_tree.print();

    /* test "find" */
    Node* p = nullptr;
    cout << ((p = rb_tree.find(2)) ? p->key : -1) << endl;
    cout << ((p = rb_tree.find(100)) ? p->key : -1) << endl << endl;

    /* test "erase" */
    rb_tree.erase(1);
    rb_tree.print();
    rb_tree.erase(9);
    rb_tree.print();
    rb_tree.erase(11);
    rb_tree.print();

    return 0;
}

数据测试如下:

( 1, 1 )
( 2, 1 )
( 3, 1 )
( 4, 0 )
( 5, 1 )
( 6, 1 )
( 7, 1 )
( 8, 1 )
( 9, 0 )
( 10, 0 )
( 11, 1 )
( 12, 0 )

2
-1

( 2, 1 )
( 3, 1 )
( 4, 1 )
( 5, 1 )
( 6, 1 )
( 7, 1 )
( 8, 1 )
( 9, 0 )
( 10, 0 )
( 11, 1 )
( 12, 0 )

( 2, 1 )
( 3, 1 )
( 4, 1 )
( 5, 1 )
( 6, 1 )
( 7, 1 )
( 8, 1 )
( 10, 0 )
( 11, 1 )
( 12, 0 )

( 2, 1 )
( 3, 1 )
( 4, 1 )
( 5, 1 )
( 6, 1 )
( 7, 1 )
( 8, 1 )
( 10, 0 )
( 12, 1 )

四:时间复杂度

最坏情况,输入的序列为升序或降序,此时红黑相间的路径长度是全黑路径长度的2倍,时间复杂度为$O_{worst}(2logn)$。

平均情况,时间复杂度为$O_{avg}(logn)$。

五:需注意的地方

有三个需要注意的地方。

5.1 insert_rebalance

insert_rebalance操作可能会有$O(logn)$量级的回溯(第一个注意点)。

当程序进入insert_rebalancewhile (x != root() && x->parent->color == red)后,它只会有如下 6 种运行方式:

  1. Case 1;
  2. Case 1 ----> Case 1 ----> Case 1 ......;
  3. Case 1 ----> ...... ----> Case 2 ----> Case 3;
  4. Case 1 ----> ...... ----> Case 3;
  5. Case 2 ----> Case 3;
  6. Case 3;

而这回溯就发生在第 2,3,4 种,我们就以第 2 种的为例,如下图,

“结点 1” 为新插入结点,此时属于 “Case 1:当前结点的父亲是红色,叔叔存在且也是红色”。那么我们的处理策略就是:

  • 将 “父亲结点” 改为黑色;
  • 将 “叔叔结点” 改为黑色;
  • 将 “祖父结点” 改为红色;
  • 将 “祖父结点” 设为 “当前结点”,继续进行操作。

但处理完后,根据代码while (x != root() && x->parent->color == red),我们发现 “当前结点” 又进入了 Case 1。假设每次处理完后都会进入 Case 1,那么这样的处理操作会直到根结点才会结束。

另外,根据运行方式第 3,4,5,6 种,我们发现,一旦 Case 3 处理完后,整个insert_rebalance随之结束,这就是为什么在 Case 3 的处理代码下方加入一行break;的原因(第二个注意点)。

5.2 erase_rebalance

可能会有人好奇erase_rebalance为何使用if (x != root() && (x == nullptr || x->color == black)),而不是while (x != root() && (x == nullptr || x->color == black))

那是因为erase_rebalance不存在回溯问题(第三个注意点)。

当程序进入if (x != root() && (x == nullptr || x->color == black))后,它只会有如下 6 种运行方式:

  1. Case 1 ----> Case 2;
  2. Case 1 ----> Case 3 ----> Case 4;
  3. Case 1 ----> Case 4;
  4. Case 2;
  5. Case 3 ----> Case 4;
  6. Case 4;

六:参考文献

Archives QR Code Tip
QR Code for this page
Tipping QR Code
Leave a Comment

已有 9 条评论
  1. 111 111

    网站使用什么框架做的

  2. zhan zhan

    图画得很漂亮,请问是用什么工具画的

    1. @zhan
      pickpick

  3. "将插入的结点着色为红色,不会违背 "性质 4"。而少违背一条性质,就意味着我们需要处理的情况越少。",如果新插入的也是黑色,那就不是红黑树了呀,全都是黑色了,所有这么描述有问题趴。^_^

    1. @boom
      根节点黑色,新插入的节点为红色,这就是一个约定而已,个人愚见。@(哈哈)

    2. @boom
      https://www.quora.com/In-insertion-of-a-red-black-tree-why-set-the-color-to-red-initially
      https://stackoverflow.com/questions/35965640/why-are-newly-inserted-nodes-are-always-colored-red-in-red-black-tree-insert-ope
      这是有依据的。

  4. 111 111

    case2的左旋感觉有问题

    1. @111
      什么问题,能说的具体点么?

    2. 111 111

      @刘毅
      看错了,不好意思