MENU

红黑树

一:背景

红黑树(英语: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"为"当前结点"。那么我们的处理策略就是:

    • 将"父亲结点"改为黑色;

    • 将"祖父结点"改为红色;

    • 以"祖父结点"为支点进行右旋。

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

2.2 删除操作

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

  1. "被删结点"没有孩子,那么直接删除即可;

  2. "被删结点"只有一个孩子,那么直接删除该结点,并用该结点的唯一孩子替换它;

  3. "被删结点"有两个孩子,那么先找出它的"后继结点",然后删除"被删结点",再用"后继结点"去替换"被删结点"。

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

首先,我们来看看删除一个结点会遇到哪几种情况,分析发现,一共有四种:

  1. "原先结点"为黑色,"当前结点"为红色,那么我们把"原先结点"删掉后,拿"当前结点"去替换它并修改颜色为黑色即可;

  2. "原先结点"为黑色,"当前结点"为黑色,这种情况比较复杂,待会再说;

  3. "原先结点"为红色,"当前结点"为红色,那么我们把"原先结点"删掉后,直接拿"当前结点"去替换它即可;

  4. "原先结点"为红色,"当前结点"为黑色,那么我们把"原先结点"删掉后,再拿"当前结点"去替换它并修改颜色为红色。我们发现,此时"原先结点"位置是满足红黑树性质的,但是由于"当前结点"被拿走,"当前结点"位置可能就会违背红黑树性质。分析发现,此时的"当前结点"不就是上面"情况1"和"情况2"中所讲的"原先结点"!那么当前的这种情况直接就变成了"情况1"或"情况2"。

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

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

    图中,"结点1"为"当前结点"。观察上图,因"原先结点"已被删除,故原来每条路径上应该是3个黑色结点(右侧路径未画完全),此时左侧少了一个,那么我们的处理策略就是:

    • 将"兄弟结点"改为黑色;

    • 将"父亲结点"改为红色;

    • 以"父亲结点"为支点进行左旋;

    • 左旋后,重新设置"兄弟结点"。

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

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

    图中,"结点1"为"当前结点"。观察上图,因"原先结点"已被删除,故原来每条路径上应该是2个黑色结点,此时左侧少了一个,那么我们的处理策略就是:

    • 将"兄弟结点"改为红色;

    • 将"父亲结点"设置为新的"当前结点",继续进行操作。

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

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

    图中,"结点1"为"当前结点"。观察上图,因"原先结点"已被删除,故原来每条路径上应该是2个黑色结点,此时左侧少了一个,那么我们的处理策略就是:

    • 将"兄弟结点"的左孩子改为黑色;

    • 将"兄弟结点"改为红色;

    • 以"兄弟结点"为支点进行右旋;

    • 右旋后,重新设置"当前结点"的"兄弟结点"。

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

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

    图中,"结点1"为"当前结点"。观察上图,因"原先结点"已被删除,故原来每条路径上应该是2个黑色结点,此时左侧少了一个,那么我们的处理策略就是:

    • 将"父亲结点"的颜色赋给"兄弟结点";

    • 将"父亲结点"改为黑色;

    • 将"兄弟结点"的右孩子改为黑色;

    • 以"父亲结点"为支点进行左旋;

处理完后,一切OK。

三:完整代码

/**
 *
 * author : 刘毅(Limer)
 * date   : 2017-08-20
 * mode   : C++
 */

#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 * header;
private:
    void rotate_left(Node * x);
    void rotate_right(Node * x);
    void destroy(Node * node);
    Node *& root();
    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();
};

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;
}

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

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

Node *& RBTree::root()
{
    return header->left;
}

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);
            }
        }
        else  // same as above, just 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);
            }
        }
    }

    root()->color = black;  // Do not forget!
}

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
    {
        y = y->right;
        while (y->left)
            y = y->left;
        x = y->right;
    }  

    if (y != z)  // if y is z's successor
    {
        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;
    }
    // now, y is pointing to what you will erase!
    //      x is the child of y, and note that x might be nullptr.
    


    // Now, the actual reblance is coming!
    // .....
    if (y->color == black)
    {
        while (x != root() && (x == nullptr || x->color == black))
        {
            if (x == x_parent->left)
            {
                Node * w = x_parent->right;  // w can not possibly be nullptr!

                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);
                    break;
                }
            }
            else  // same as above, just 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);
                    break;
                }
            }
        }  // while (x != root() && (x == nullptr || x->color == black))

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

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

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

RBTree::RBTree()
{
    header = new Node(0);
}

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

Node * RBTree::insert(int key)
{
    Node * cur = root();
    Node * pre = header;
  
    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 (pre == header || key < pre->key)
        pre->left = cur;
    else
        pre->right = cur;

    insert_rebalance(cur);
  
    return cur;
}

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::erase(int key)
{
    Node * z = find(key);
  
    if (z)
    {
        erase_rebalance(z);
        delete z;
    }
}

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

int main()
{
    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;
}

数据测试如下图:

红黑树还是很复杂的,所以建议读者结合算法可视化工具来理解红黑树。注意,该平台的"删除操作"采用的是"前驱替换原则",这和本文的"后继替换原则"不同。

四:时间复杂度

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

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

最后,附三段红黑树插入操作的视频(资源来自http://algs4.cs.princeton.edu/33balanced/):

(1)以升序序列插入

(2)以降序序列插入

(3)以随机序列插入

五:参考文献

标签: 红黑树
返回文章列表 文章二维码 打赏
本页链接的二维码
打赏二维码
添加新评论

20 条评论
  1. 你是人间的四月天 你是人间的四月天

    博主,你好!我有几个地方没看懂:

    "原先结点" 为红色,"当前结点" 为黑色,那么我们把 "原先结点" 删掉后,再拿 "当前结点" 去替换它并修改颜色为红色。我们发现,此时 "原先结点" 位置是满足红黑树性质的,但是由于 "当前结点" 被拿走,"当前结点" 位置可能就会违背红黑树性质。分析发现,此时的 "当前结点" 不就是上面 "情况 1" 和 "情况 2" 中所讲的 "原先结点"!

    那么当前的这种情况直接就变成了 "情况 1" 或 "情况 2"。

          请问博主,这个第四个情况在哪里被处理的呢?
         2.  删除代码的重要部分从这开始  if (y->color == Black)
          请问博主,从这开始处理的只是情况二的那 case 1 case 2 case 3 case 4,
          也就是处理原先节点黑色,当前结点也是黑色的吗?原谅我菜鸟没看出来 原先节点红色,当前结点黑色在哪里被处理的.......
         3. 博主,在那个 case 介绍那里,可以把删除之前的图片也画出来吗?(笑哭)
          我很难知道被删除的节点原来在哪里,而且那个(右侧路径未画完全可以加上去吗?)笑哭
          原谅菜鸟看起来有点迷.......
    
    1. @你是人间的四月天你的第一个问题:第四种情况可以转化为第一或第二,请仔细阅读我文章的说明,它在代码的 if (y != z) // if y is z's successor这里处理了。

      第二个问题:你把你的这种情况放进代码自己脑补运行下就知道了。

      第三个问题:真的没有这个必要。恢复平衡阶段根本不用考虑原先结点的位置,因为前面代码已经考虑过了。

      -------------------------个人建议---------------------------------

      红黑树确实是很复杂的,建议你先把二叉查找树和AVL树看明白再来看红黑树,尤其是AVL树,一定要看明白。

    2. 你是人间的四月天 你是人间的四月天

      @刘毅博主,你好! 嗯嗯,是我能力不行,没看懂这个......
      刚才我在csdn 上看到了其他的红黑树讲解,感觉有一点不错,指出了为什么那四个case 是那样操作的
      博主只给出了四种case 结论,这四个 case 为什么是这样,我没看懂
      但其他博客写道了:删除 y 之后,想方设法地让经过 x 路径的黑色节点都 +1......
      我感觉这样就蛮清楚了!那四个 case 清楚了.......
      之前很迷,就是在博主您的删除操作(还向上没有调整颜色,if(y->color==black)之前),
      和我平时写的不一样,我花了好久才看懂(好像博主你的 AVL 树的删除操作和这次红黑树的也不一样)
      刚才我看的其他博客删除操作和我平时写的差不多.....没有替换节点,而是找了“替罪羊”代替删除......博主您的是指针操作完成的替换!厉害呀,我一时没反应过来
      这次学习了!多谢博主
      如有冒犯,请博主见谅(@(哈哈))

    3. 你是人间的四月天 你是人间的四月天

      @你是人间的四月天说错了,是“博主你的二叉树删除操作和这次红黑书的也不一样”,@(笑尿)

    4. @你是人间的四月天四个case为什么是这样?所以我们才要看懂AVL树再来看红黑树,两个都一样的,AVL存在四种情况,那是因为不管你怎么插入删除只会出现这四种,所以只考虑这四种。而红黑树也在综合考虑了所有所有所有的可能出现的情况后,然后剔除没必要的,就只剩下四种了,那为什么恢复“平衡”操作是那样设置的呢?个人觉得,它是在综合考虑了四种情况后,发现由case 1可以进入case2,3,4,而由case 3可以进入case 4,case 4本身又可以单独形成一种情况,所以才巧妙的只用了几个if else就解决了四种情况。你可以思考下如果将这四种情况单独考虑再找到它们的解决方法,那着实是异常困难的。

      “刚才我在csdn 上看到了其他的红黑树讲解,感觉有一点不错,指出了为什么那四个case 是那样操作的
      博主只给出了四种case 结论,这四个 case 为什么是这样,我没看懂。”

      嗯,这我也看到了,但我没这么去绘图,为什么呢?因为它那张图只是依次考虑了case 1,case 2,case 3,case 4,那case 1,case 3,case 4呢?是不是还要重新画张图?没必要。直接将这四种情况分开加以说明即可,剩下的疑问需要读者自己画画图慢慢思考就出来了。

    5. 你是人间的四月天 你是人间的四月天

      @刘毅嗯嗯,博主你说得对

  2. 你是人间的四月天 你是人间的四月天

    博主,你好,我感觉你的视频和代码的效果好像有点不一样.........我从1 2 3 4...... 10 递增建树,然后层次遍历出来的效果,我画了一下图,和视频的不一样.....
    代码还是博主你的代码,我就加了一个层次遍历代码, 效果和视频里的不一样,以下是我的层次遍历代码
    不知道是不是我的有问题

    void RBTree::Level_visit(Node * node)
    {
        printf("\n\n--------------------------------------- 层次遍历 ----------------------------------------\n\n") ;
        Node *ptr = node ;
        queue<Node*> a ;
        if(ptr){
            a.push(ptr) ;
        }
        while(!a.empty())
        {
            ptr = a.front() ;
            printf("%d\t",ptr->key) ;
            printf(ptr->color==red?"红\t":"黑\t") ; 
            a.pop() ;
            if(ptr->left){
                a.push(ptr->left) ;
                printf("左孩子  %d\t",ptr->left->key) ;
            }
            if(ptr->right){
                a.push(ptr->right) ;
                printf("右孩子  %d\t",ptr->right->key) ;
            }
            printf("\n\n") ;
        }
    }
    1. 你是人间的四月天 你是人间的四月天

      @你是人间的四月天请博主指点啦^ . ^

      数据结构小白不知道 1 2 3 4 5 6 7 8 9 10 建立的红黑树长什么样........
      也可能是我的层次遍历有问题,求指点^ . ^

    2. 你是人间的四月天 你是人间的四月天

      @你是人间的四月天我的代码原来该有 号的地方是有 的,传上去就没了

    3. @你是人间的四月天评论是支持markdown语法的,已经帮你修改好

    4. @你是人间的四月天http://www.cs.usfca.edu/~galles/visualization/RedBlack.html

      我已经在代码尾部提供一个算法可视化工具,你可以对照着看下

    5. @你是人间的四月天视频仅仅作为参考,其目的就是让我们感受下红黑树的过程。(视频并不是我做的)

    6. 你是人间的四月天 你是人间的四月天

      @刘毅好的!多谢博主

    7. 你是人间的四月天 你是人间的四月天

      @刘毅博主,你的代码没有错!我按照那个可视化工具演示了一遍!
      之前没注意这个算法可视化工具......这样更好理解了!

    8. 你是人间的四月天 你是人间的四月天

      @刘毅这个可视化工具好棒!

  3. Kevin Kevin

    真心赞!最下面的演示视频是用什么工具做的?

  4. 感谢博主的分享

  5. 你是人间的四月天 你是人间的四月天

    谢谢博主的一系列博客,真的很好!比一般的csdn 博客认真多了