对红黑树的认识总结

﹏ヽ暗。殇╰゛Y 2023-03-13 06:48 4阅读 0赞

**目录**

一、对红黑树的基本理解

（一）对红黑树的基本定义理解

（二）对红黑树是“近似平衡”的理解

1.将红色节点从红黑树中去掉，分析包含黑色节点的红黑树的高度

2.把红色节点加回去，分析高度变化

（三）红黑树与AVL树的比较：

二、实现红黑树的基本思想分析

（一）理解左旋（rotate left）、右旋（rotate right）操作

（二）插入操作的平衡调整

情况一：如果关注节点是 a，它的叔叔节点 d 是红色

情况二：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的右子节点

情况三：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的左子节点

以上具体代码如下：

（三）删除操作的平衡调整

1.针对删除节点初步调整

情况一：如果要删除的节点是 a，它只有一个子节点 b

情况二：如果要删除的节点 a 有两个非空子节点，并且它的后继节点就是节点 a 的右子节点 c

情况三：如果要删除的是节点 a，它有两个非空子节点，并且节点 a 的后继节点不是右子节点

2. 针对关注节点进行二次调整

情况一：如果关注节点是 a，它的兄弟节点 c 是红色的

情况二：如果关注节点是 a，它的兄弟节点 c 是黑色的，并且节点 c 的左右子节点 d、e 都是黑色的

情况三：如果关注节点是 a，它的兄弟节点 c 是黑色，c 的左子节点 d 是红色，c 的右子节点 e 是黑色

情况四：如果关注节点 a 的兄弟节点 c 是黑色的，并且 c 的右子节点是红色的

以上具体代码可见：

参考文献与链接：

--------------------

# 一、对红黑树的基本理解 #

## （一）对红黑树的基本定义理解 ##

红黑树的英文是“Red-Black Tree”，简称 R-B Tree，它是一种不严格的平衡二叉查找树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70][]

红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，**一棵红黑树还需要满足这样几个要求**：

*  **根节点是黑色的；**
 *  **每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据（图中将黑色的、空的叶子节点都省略掉了）；**
 *  **任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；**
 *  **每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；**

## （二）对红黑树是“近似平衡”的理解 ##

**平衡二叉查找树的初衷，是为了解决二叉查找树因为动态更新导致的性能退化问题**。所以，“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。

**一棵极其平衡的二叉树（满二叉树或完全二叉树）的高度大约是 log2n，所以如果要证明红黑树是近似平衡的，只需要分析，红黑树的高度是否比较稳定地趋近 log2n 就好了**。

### 1.将红色节点从红黑树中去掉，分析包含黑色节点的红黑树的高度 ###

红色节点删除之后，有些节点就没有父节点了，它们会直接拿这些节点的祖父节点（父节点的父节点）作为父节点。所以，之前的二叉树就变成了四叉树。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 1][]

从四叉树中取出某些节点，放到叶节点位置，四叉树就变成了完全二叉树。所以，仅包含黑色节点的四叉树的高度，比包含相同节点个数的完全二叉树的高度还要小。

完全二叉树的高度近似 log2n，这里的四叉“黑树”的高度要低于完全二叉树，所以去掉红色节点的“黑树”的高度也不会超过 log2n。

### 2.把红色节点加回去，分析高度变化 ###

在红黑树中，红色节点不能相邻，也就是说，有一个红色节点就要至少有一个黑色节点，将它跟其他红色节点隔开。

红黑树中包含最多黑色节点的路径不会超过 log2n，所以**加入红色节点之后，最长路径不会超过 2log2n，也就是说，红黑树的高度近似 2log2n。**

所以，红黑树的高度只比高度平衡的 AVL 树的高度（log2n）仅仅大了一倍，在性能上，下降得并不多。这样推导出来的结果不够精确，实际上红黑树的性能更好。

## （三）**红黑树与AVL树的比较：** ##

*  AVL树的时间复杂度虽然优于红黑树，但是对于现在的计算机，cpu太快，可以忽略性能差异
 *  红黑树的插入删除比AVL树更便于控制操作
 *  红黑树整体性能略优于AVL树（红黑树旋转情况少于AVL树）

# 二、实现红黑树的基本思想分析 #

**红黑树的平衡过程跟魔方复原非常神似，大致过程就是：遇到什么样的节点排布，我们就对应怎么去调整**。只要按照这些固定的调整规则来操作，就能将一个非平衡的红黑树调整成平衡的。

如上，一棵合格的红黑树需要满足的四个基本要求中，在插入、删除节点的过程中，第三、第四点要求可能会被破坏，而“平衡调整”实际上就是要把被破坏的第三、第四点恢复过来。具体分析如下：

## （一）理解左旋（rotate left）、右旋（rotate right）操作 ##

左旋就是围绕某个节点的左旋，图中的 a，b，r 表示子树，可以为空。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 2][]

具体代码实现：

/**
         * 功能描述：左旋右侧需要平衡
         *
         * @author yanfengzhang
         * @date 2020-05-27 14:57
         */
        private void rotateLeft(Entry<K, V> p) {
            if (p != null) {
                /*拿到根节点的右子节点 */
                Entry<K, V> r = p.right;
                /*把根节点的右子节点的左节点，赋值*/
                p.right = r.left;
                if (r.left != null)
                    /*将根节点这个值赋值到当前断开的跟节点上*/ {
                    r.left.parent = p;
                }
                /*r 将来要成为新的根节点 p.parent 为根 ，使得他为新的跟节点 */
                r.parent = p.parent;
                if (p.parent == null) {
                    root = r;
                }
                /*如果p 为左孩子，让他还是成为左孩子 同理*/
                else if (p.parent.left == p) {
                    p.parent.left = r;
                } else {
                    p.parent.right = r;
                }
                /*最后 将当前交换的跟换值*/
                r.left = p;
                p.parent = r;
            }
        }

右旋就是围绕某个节点的右旋，图中的 a，b，r 表示子树，可以为空。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 3][]

具体代码实现：

/**
         * 功能描述：右旋代码
         *
         * @author yanfengzhang
         * @date 2020-05-27 14:58
         */
        private void rotateRight(Entry<K, V> p) {
            if (p != null) {
                Entry<K, V> l = p.left;
                p.left = l.right;
                if (l.right != null) {
                    l.right.parent = p;
                }
                l.parent = p.parent;
                if (p.parent == null) {
                    root = l;
                } else if (p.parent.right == p) {
                    p.parent.right = l;
                } else {
                    p.parent.left = l;
                }
                l.right = p;
                p.parent = l;
            }
        }

## （二）插入操作的平衡调整 ##

**红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上。**

关于插入操作的平衡调整，有这样两种特殊情况：

*  如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义。
 *  如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了。

**除此之外，其他情况都会违背红黑树的定义，需要进行调整，调整的过程包含两种基础的操作：左右旋转和改变颜色**。

红黑树的平衡调整过程是一个迭代的过程。把正在处理的节点叫作关注节点。关注节点会随着不停地迭代处理，而不断发生变化。最开始的关注节点就是新插入的节点。新节点插入之后，如果红黑树的平衡被打破，那一般会有下面三种情况：

备注：我们只需要根据每种情况的特点，不停地调整，就可以让红黑树继续符合定义，也就是继续保持平衡。为了简化描述，把父节点的兄弟节点叫作叔叔节点，父节点的父节点叫作祖父节点。

### **情况一：如果关注节点是 a，它的叔叔节点 d 是红色** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 4][]

具体操作为：将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色；将关注节点 a 的祖父节点 c 的颜色设置成红色；关注节点变成 a 的祖父节点 c；跳到情况二或者情况三。

### **情况二：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的右子节点** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 5][]

具体操作为：关注节点变成节点 a 的父节点 b；围绕新的关注节点b 左旋；跳到情况三。

### **情况三：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的左子节点** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 6][]

具体操作为：围绕关注节点 a 的祖父节点 c 右旋；将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换，调整结束。

### 以上具体代码如下： ###

/**
         * 功能描述：插入一个节点
         *
         * @author yanfengzhang
         * @date 2020-05-27 15:07
         */
        private void insert(RBTreeNode<T> node) {
            int cmp;
            RBTreeNode<T> root = this.rootNode;
            RBTreeNode<T> parent = null;
    
            /*定位节点添加到哪个父节点下*/
            while (null != root) {
                parent = root;
                cmp = node.key.compareTo(root.key);
                if (cmp < 0) {
                    root = root.left;
                } else {
                    root = root.right;
                }
            }
    
            node.parent = parent;
            /*表示当前没一个节点，那么就当新增的节点为根节点*/
            if (null == parent) {
                this.rootNode = node;
            } else {
                //找出在当前父节点下新增节点的位置
                cmp = node.key.compareTo(parent.key);
                if (cmp < 0) {
                    parent.left = node;
                } else {
                    parent.right = node;
                }
            }
    
            /*设置插入节点的颜色为红色*/
            node.color = COLOR_RED;
    
            /*修正为红黑树*/
            insertFixUp(node);
        }
    
        /**
         * 功能描述：红黑树插入修正
         *
         * @author yanfengzhang
         * @date 2020-05-27 15:07
         */
        private void insertFixUp(RBTreeNode<T> node) {
            RBTreeNode<T> parent, gparent;
            /*节点的父节点存在并且为红色*/
            while (((parent = getParent(node)) != null) && isRed(parent)) {
                gparent = getParent(parent);
    
                /*如果其祖父节点是空怎么处理, 若父节点是祖父节点的左孩子*/
                if (parent == gparent.left) {
                    RBTreeNode<T> uncle = gparent.right;
                    if ((null != uncle) && isRed(uncle)) {
                        setColorBlack(uncle);
                        setColorBlack(parent);
                        setColorRed(gparent);
                        node = gparent;
                        continue;
                    }
    
                    if (parent.right == node) {
                        RBTreeNode<T> tmp;
                        leftRotate(parent);
                        tmp = parent;
                        parent = node;
                        node = tmp;
                    }
    
                    setColorBlack(parent);
                    setColorRed(gparent);
                    rightRotate(gparent);
                } else {
                    RBTreeNode<T> uncle = gparent.left;
                    if ((null != uncle) && isRed(uncle)) {
                        setColorBlack(uncle);
                        setColorBlack(parent);
                        setColorRed(gparent);
                        node = gparent;
                        continue;
                    }
    
                    if (parent.left == node) {
                        RBTreeNode<T> tmp;
                        rightRotate(parent);
                        tmp = parent;
                        parent = node;
                        node = tmp;
                    }
    
                    setColorBlack(parent);
                    setColorRed(gparent);
                    leftRotate(gparent);
                }
            }
            setColorBlack(this.rootNode);
        }

## （三）删除操作的平衡调整 ##

删除操作的平衡调整分为两步：

**第一步是针对删除节点初步调整**。初步调整只是保证整棵红黑树在一个节点删除之后，仍然满足最后一条定义的要求，也就是说，每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

**第二步是针对关注节点进行二次调整，让它满足红黑树的第三条定义**，即不存在相邻的两个红色节点。

### 1.针对删除节点初步调整 ###

红黑树的定义中“只包含红色节点和黑色节点”，经过初步调整之后，为了保证满足红黑树定义的最后一条要求，有些节点会被标记成两种颜色，“红 - 黑”或者“黑 - 黑”。如果一个节点被标记为了“黑 - 黑”，那在计算黑色节点个数的时候，要算成两个黑色节点。

备注：如果一个节点既可以是红色，也可以是黑色，图中用一半红色一半黑色来表示。如果一个节点是“红 - 黑”或者“黑 - 黑”，图中用左上角的一个小黑点来表示额外的黑色。

### **情况一：如果要删除的节点是 a，它只有一个子节点 b** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 7][]

具体操作为：删除节点 a，并且把节点 b 替换到节点 a 的位置，这一部分操作跟普通的二叉查找树的删除操作一样；节点 a 只能是黑色，节点 b 也只能是红色，其他情况均不符合红黑树的定义。这种情况下，我们把节点 b 改为黑色；调整结束，不需要进行二次调整。

### **情况二：如果要删除的节点 a 有两个非空子节点，并且它的后继节点就是节点 a 的右子节点 c** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 8][]

具体操作为：如果节点 a 的后继节点就是右子节点 c，那右子节点 c 肯定没有左子树。我们把节点 a 删除，并且将节点 c 替换到节点 a 的位置。这一部分操作跟普通的二叉查找树的删除操作无异；然后把节点 c 的颜色设置为跟节点 a 相同的颜色；如果节点 c 是黑色，为了不违反红黑树的最后一条定义，我们给节点 c 的右子节点 d 多加一个黑色，这个时候节点 d 就成了“红 - 黑”或者“黑 - 黑”；这个时候，关注节点变成了节点 d，第二步的调整操作就会针对关注节点来做。

### **情况三：如果要删除的是节点 a，它有两个非空子节点，并且节点 a 的后继节点不是右子节点** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 9][]

具体操作为：找到后继节点 d，并将它删除，删除后继节点 d 的过程参照 CASE 1；将节点 a 替换成后继节点 d；把节点 d 的颜色设置为跟节点 a 相同的颜色；如果节点 d 是黑色，为了不违反红黑树的最后一条定义，我们给节点 d 的右子节点 c 多加一个黑色，这个时候节点 c 就成了“红 - 黑”或者“黑 - 黑”；这个时候，关注节点变成了节点 c，第二步的调整操作就会针对关注节点来做。

### 2. 针对关注节点进行二次调整 ###

初步调整之后，关注节点变成了“红 - 黑”或者“黑 - 黑”节点。针对这个关注节点，再分四种情况来进行二次调整。

备注：二次调整是为了让红黑树中不存在相邻的红色节点。

### **情况一：如果关注节点是 a，它的兄弟节点 c 是红色的** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 10][]

具体操作：围绕关注节点 a 的父节点 b 左旋；关注节点 a 的父节点 b 和祖父节点 c 交换颜色；关注节点不变；继续从四种情况中选择适合的规则来调整。

### **情况二：如果关注节点是 a，它的兄弟节点 c 是黑色的，并且节点 c 的左右子节点 d、e 都是黑色的** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 11][]

具体操作：将关注节点 a 的兄弟节点 c 的颜色变成红色；从关注节点 a 中去掉一个黑色，这个时候节点 a 就是单纯的红色或者黑色；给关注节点 a 的父节点 b 添加一个黑色，这个时候节点 b 就变成了“红 - 黑”或者“黑 - 黑”；关注节点从 a 变成其父节点 b；继续从四种情况中选择符合的规则来调整。

### **情况三：如果关注节点是 a，它的兄弟节点 c 是黑色，c 的左子节点 d 是红色，c 的右子节点 e 是黑色** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 12][]

具体操作：围绕关注节点 a 的兄弟节点 c 右旋；节点 c 和节点 d 交换颜色；关注节点不变；跳转到 CASE 4，继续调整。

### **情况四：如果关注节点 a 的兄弟节点 c 是黑色的，并且 c 的右子节点是红色的** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 13][]

具体操作：围绕关注节点 a 的父节点 b 左旋；将关注节点 a 的兄弟节点 c 的颜色，跟关注节点 a 的父节点 b 设置成相同的颜色；将关注节点 a 的父节点 b 的颜色设置为黑色；从关注节点 a 中去掉一个黑色，节点 a 就变成了单纯的红色或者黑色；将关注节点 a 的叔叔节点 e 设置为黑色；调整结束。

### 以上具体代码可见： ###

/**
         * 功能描述：删除节点
         *
         * @author yanfengzhang
         * @date 2020-05-27 15:11
         */
        private void remove(RBTreeNode<T> node) {
            RBTreeNode<T> child, parent;
            boolean color;
            /*被删除节点左右孩子都不为空的情况*/
            if ((null != node.left) && (null != node.right)) {
    
                /*获取到被删除节点的后继节点*/
                RBTreeNode<T> replace = node;
    
                replace = replace.right;
                while (null != replace.left) {
                    replace = replace.left;
                }
    
                /*node节点不是根节点*/
                if (null != getParent(node)) {
                    /*node是左节点*/
                    if (getParent(node).left == node) {
                        getParent(node).left = replace;
                    } else {
                        getParent(node).right = replace;
                    }
                } else {
                    this.rootNode = replace;
                }
    
                child = replace.right;
                parent = getParent(replace);
                color = getColor(replace);
    
                if (parent == node) {
                    parent = replace;
                } else {
                    if (null != child) {
                        setParent(child, parent);
                    }
                    parent.left = child;
    
                    replace.right = node.right;
                    setParent(node.right, replace);
                }
    
                replace.parent = node.parent;
                replace.color = node.color;
                replace.left = node.left;
                node.left.parent = replace;
                if (color == COLOR_BLACK) {
                    removeFixUp(child, parent);
                }
    
                node = null;
                return;
            }
    
            if (null != node.left) {
                child = node.left;
            } else {
                child = node.right;
            }
    
            parent = node.parent;
            color = node.color;
            if (null != child) {
                child.parent = parent;
            }
    
            if (null != parent) {
                if (parent.left == node) {
                    parent.left = child;
                } else {
                    parent.right = child;
                }
            } else {
                this.rootNode = child;
            }
    
            if (color == COLOR_BLACK) {
                removeFixUp(child, parent);
            }
            node = null;
        }
    
        /**
         * 功能描述：删除修复
         *
         * @author yanfengzhang
         * @date 2020-05-27 15:11
         */
        private void removeFixUp(RBTreeNode<T> node, RBTreeNode<T> parent) {
            RBTreeNode<T> other;
            /*node不为空且为黑色，并且不为根节点*/
            while ((null == node || isBlack(node)) && (node != this.rootNode)) {
                /*node是父节点的左孩子*/
                if (node == parent.left) {
                    /*获取到其右孩子*/
                    other = parent.right;
                    /*node节点的兄弟节点是红色*/
                    if (isRed(other)) {
                        setColorBlack(other);
                        setColorRed(parent);
                        leftRotate(parent);
                        other = parent.right;
                    }
    
                    /*node节点的兄弟节点是黑色，且兄弟节点的两个孩子节点也是黑色*/
                    if ((other.left == null || isBlack(other.left)) &&
                            (other.right == null || isBlack(other.right))) {
                        setColorRed(other);
                        node = parent;
                        parent = getParent(node);
                    } else {
                        /*node节点的兄弟节点是黑色，且兄弟节点的右孩子是红色*/
                        if (null == other.right || isBlack(other.right)) {
                            setColorBlack(other.left);
                            setColorRed(other);
                            rightRotate(other);
                            other = parent.right;
                        }
                        /*node节点的兄弟节点是黑色，且兄弟节点的右孩子是红色，左孩子是任意颜色*/
                        setColor(other, getColor(parent));
                        setColorBlack(parent);
                        setColorBlack(other.right);
                        leftRotate(parent);
                        node = this.rootNode;
                        break;
                    }
                } else {
                    other = parent.left;
                    if (isRed(other)) {
                        setColorBlack(other);
                        setColorRed(parent);
                        rightRotate(parent);
                        other = parent.left;
                    }
    
                    if ((null == other.left || isBlack(other.left)) &&
                            (null == other.right || isBlack(other.right))) {
                        setColorRed(other);
                        node = parent;
                        parent = getParent(node);
                    } else {
                        if (null == other.left || isBlack(other.left)) {
                            setColorBlack(other.right);
                            setColorRed(other);
                            leftRotate(other);
                            other = parent.left;
                        }
    
                        setColor(other, getColor(parent));
                        setColorBlack(parent);
                        setColorBlack(other.left);
                        rightRotate(parent);
                        node = this.rootNode;
                        break;
                    }
                }
            }
            if (node != null) {
                setColorBlack(node);
            }
        }

# 参考文献与链接： #

1.[https://tech.meituan.com/2016/12/02/redblack-tree.html][https_tech.meituan.com_2016_12_02_redblack-tree.html]

2.《数据结构与算法之美》，王争（前Google工程师），极客时间，2019

3.[https://blog.csdn.net/tanrui519521/article/details/80980135][https_blog.csdn.net_tanrui519521_article_details_80980135]

4.[https://blog.csdn.net/jjc120074203/article/details/78780221][https_blog.csdn.net_jjc120074203_article_details_78780221]

5.[https://blog.csdn.net/aa1215018028/article/details/92660140][https_blog.csdn.net_aa1215018028_article_details_92660140]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70]: /images/20230312/e97a85f6c6494889ba1379fc5e0e01c2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 1]: /images/20230312/5c48bc8e25064246bf756201d7bcf8c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200527115357818.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200527115419462.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2020052711592256.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200527115946139.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/2020052712000897.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200527143854463.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200527143927784.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200527144006994.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200527144734352.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20200527144824243.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20200527144857249.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/20200527144922149.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9mZW5nMTAzMzAxMTE=,size_16,color_FFFFFF,t_70
[https_tech.meituan.com_2016_12_02_redblack-tree.html]: https://tech.meituan.com/2016/12/02/redblack-tree.html
[https_blog.csdn.net_tanrui519521_article_details_80980135]: https://blog.csdn.net/tanrui519521/article/details/80980135
[https_blog.csdn.net_jjc120074203_article_details_78780221]: https://blog.csdn.net/jjc120074203/article/details/78780221
[https_blog.csdn.net_aa1215018028_article_details_92660140]: https://blog.csdn.net/aa1215018028/article/details/92660140