数据结构算法 - 红黑树

Dear 丶 2023-02-21 06:09 118阅读 0赞

红黑树是一棵自平衡的二叉搜索树，因此在学习红黑树之前，我们需要回顾一下之前所学的知识  
**二叉搜索树和平衡二叉树**。

## 1、二叉搜索树 ##

二叉搜索树又叫二叉查找树或者二叉排序树，它首先是一个二叉树，而且必须满足下面的条件：

1）若左子树不空，则左子树上所有结点的值均小于它的根节点的值；
    
    2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值
    
    3）左、右子树也分别为二叉搜索树

二叉搜索树示例  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg_size_16_color_FFFFFF_t_70]

## 2、平衡二叉树 ##

二叉搜索树解决了许多问题，比如可以快速的查找最大值和最小值，可以快速找到排名第几位的值，快速搜索和排序等等。但普通的二叉搜索树有可能出现极不平衡的情况（斜树），这样我们的时间复杂度就有可能退化成 O(N) 的情况。比如我们现在插入的数据是 \[1,2,3,4,5,6,7\] 转换为二叉树如下：

斜树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg_size_16_color_FFFFFF_t_70 1]  
由于普通的二叉搜索树会出现极不平衡的情况，那么我们就必须得想想办法了，这个时候平衡二叉树就能帮到我们了。什么是平衡二叉树？平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或**它的左右两个子树的高度差的绝对值不超过1**，并且左右两个子树都是一棵平衡二叉树。

平衡二叉树有一个很重要的性质：左右两个子树的高度差的绝对值不超过1。那么解决方案就是如果二叉树的左右高度超过 1 ，我们就把当前树调整为一棵平衡二叉树。这就涉及到**左旋、右旋、先右旋再左旋、先左旋再右旋**。

**2.1 右旋：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg_size_16_color_FFFFFF_t_70 2]

TreeNode<K, V> *R_Rotation(TreeNode<K, V> *pNode) { 
            TreeNode<K, V> *left = pNode->left;
            TreeNode<K, V> *right = left->right;
            left->right = pNode;
            pNode->left = right;
            // 重新调整高度
            pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) + 1;
            left->height = max(getHeight(left->left), getHeight(left->right)) + 1;
            return left;
        }

**2.2 左旋：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg_size_16_color_FFFFFF_t_70 3]

TreeNode<K, V> *L_Rotation(TreeNode<K, V> *pNode) { 
            TreeNode<K, V> *right = pNode->right;
            TreeNode<K, V> *left = right->left;
            right->left = pNode;
            pNode->right = left;
            // 重新调整高度
            pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) + 1;
            right->height = max(getHeight(right->left), getHeight(right->right)) + 1;
            return right;
        }

**2.3 先右旋再左旋：**  
![先右旋再左旋][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg_size_16_color_FFFFFF_t_70 4]

TreeNode<K, V> *R_L_Rotation(TreeNode<K, V> *pNode) { 
        pNode->right = R_Rotation(pNode->right);
        return L_Rotation(pNode);
      }

**2.4 先左旋再右旋：**  
![先左旋再右旋][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg_size_16_color_FFFFFF_t_70 5]

TreeNode<K, V> *L_R_Rotation(TreeNode<K, V> *pNode) { 
        pNode->left = L_Rotation(pNode->left);
        return R_Rotation(pNode);
      }

## 3、红黑树 ##

红黑树用法就比较广了，比如 JDK 1.8 的 HashMap，TreeMap，C++ 中的 map 和 multimap 等等。红黑树学习起来还是有一点难度的，这时如果我们心中有 B 树就有助于理解它，如果没有 B 树也没有关系。

红黑树的特性:  
（1）每个节点或者是黑色，或者是红色。  
（2）根节点是黑色。  
（3）每个叶子节点（NIL）是黑色。 \[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！\]  
（4）如果一个节点是红色的，则它的子节点必须是黑色的。  
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。  
![在这里插入图片描述][20200628213739196.png]

假设我们现在要插入一个新的节点，如过插入的这个新的节点为黑色，那么必然会违反性质(5)，所以我们把新插入的点定义为红色的。但是如果插入的新节点为红色，就可能会违反性质(4) ，因此我们需要对其进行调整，使得整棵树依然满足红黑树的性质，也就是双红修正。接下来我们只要分情况分析就可以了：

1、如果没有出现双红现象，父亲是黑色的不需要修正；
    2、叔叔是红色的 ，将叔叔和父亲染黑，然后爷爷染红；
    3、叔叔是黑色的，父亲是爷爷的左节点，且当前节点是其父节点的右孩子，将“父节点”作为“新的当前节点”，
    	以“新的当前节点”为支点进行左旋。然后将“父节点”设为“黑色”，将“祖父节点”设为“红色”，
    	以“祖父节点”为支点进行右旋；
    4、叔叔是黑色的，父亲是爷爷的左节点，且当前节点是其父节点的左孩子，将“父节点”设为“黑色”，
    	将“祖父节点”设为“红色”，以“祖父节点”为支点进行右旋；
    5、叔叔是黑色的，父亲是爷爷的右节点，且当前节点是其父节点的左孩子，将“父节点”作为“新的当前节点”，
    	以“新的当前节点”为支点进行右旋。然后将“父节点”设为“黑色”，将“祖父节点”设为“红色”，
    	以“祖父节点”为支点进行左旋；
    6、叔叔是黑色的，父亲是爷爷的右节点，且当前节点是其父节点的右孩子，将“父节点”设为“黑色”，
    	将“祖父节点”设为“红色”，以“祖父节点”为支点进行左旋；

上面的双红修正现象看似比较复杂，但实际上只有三种情况，一种是没有双红现象，另一种是父亲和叔叔都是红色的，最后一种是叔叔是黑色的。我们来画个实例看下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg_size_16_color_FFFFFF_t_70 6]

void solveDoubleRed(TreeNode *pNode) { 
            while (pNode->parent && pNode->parent->color == red) { // 情况 1
                TreeNode *uncle = brother(parent(pNode));
    
                if (getColor(uncle) == red) { // 情况2
                    // 设置双亲和叔叔为黑色
                    setColor(parent(pNode), black);
                    setColor(uncle, black);
                    // 指针回溯至爷爷
                    pNode = parent(parent(pNode));
                } else { 
                    // 父亲是爷爷的左儿子
                    if (parent(parent(pNode))->left = parent(pNode)) {  // 情况 3 和 4
                        // 自己是父亲的右儿子
                        if (parent(pNode)->right == pNode) { 
                            pNode = parent(pNode);
                            L_Rotation(pNode);
                        }
                        // 把我自己这边的红色节点挪到隔壁树上，但仍然不能违反性质 4 和 5
                        setColor(parent(pNode), black);
                        setColor(parent(parent(pNode)), red);
                        R_Rotation(parent(parent(pNode)));
                    } else {  // 情况 5 和 6
                        // 自己是父亲的左儿子
                        if (parent(pNode)->left == pNode) { 
                            pNode = parent(pNode);
                            R_Rotation(pNode);
                        }
                        // 把我自己这边的红色节点挪到隔壁树上，但仍然不能违反性质 4 和 5
                        setColor(parent(pNode), black);
                        setColor(parent(parent(pNode)), red);
                        L_Rotation(parent(parent(pNode)));
                    }
                }
            }
    
            // 根结点为黑色
            root->color = black;
        }

哎～好复杂这怎么记得住。如果要记住肯定不太可能而且费劲，接下来我们来分析下为什么要这么操作，还有没有更好的调整方法。我们所有的调整都是为了不违反性质4和性质5，假设我在左边的这个支树上新增了一个红色的节点，违反了性质4 。想法就是我把左支树上的一个红色节点，挪动右支树上去，这样就解决了我有两个连续红色节点的问题。但挪给右支树的过程中不能违反性质4和性质5，所以必须得考虑叔叔节点的颜色。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg_size_16_color_FFFFFF_t_70 7]

最后我们来看下红黑树的删除操作，红黑树的删除操作要比新增操作要复杂些，但总体来说都是出现问题就去解决问题。当我们移除的是一个红色节点，那么根本就不会影响我们的性质4和性质5，我们不需要调整，但倘若我们移除的是一个黑色的节点，这时肯定会违反我们的性质5，所以我们只需要调整移除黑色节点的情况。分情况讨论下：

1、如果兄弟节点是红色的，把兄弟节点染黑，父节点染红，左/右旋父节点；
    2、如果兄弟节点是黑色的，并且两个侄子节点都是黑色的，将兄弟节点染红，指针回溯至父亲节点；
    3、如果兄弟节点是黑色，的并且远侄子是黑色的，近侄子是红色的，将进侄子染黑，兄弟染红，
    	左/右旋兄弟节点，进入下面情况 4 ；
    4、如果兄弟节点是黑色的，并且远侄子是红色的，近侄子随意，将兄弟节点染成父亲节点的颜色，
    	父亲节点染黑，远侄子染黑，左/右旋父亲节点。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg_size_16_color_FFFFFF_t_70 8]

void solveLostBlack(TreeNode *pNode) { 
            while (pNode != root && getColor(pNode) == black) { 
                if (left(parent(pNode)) == pNode) { 
                    TreeNode *sib = brother(pNode);
                    if (getColor(sib) == red) { 
                        setColor(sib, black);
                        setColor(parent(pNode), red);
                        L_Rotation(parent(pNode));
                        sib = brother(pNode);
                    }
    
                    if (getColor(left(sib)) == black && getColor(right(sib)) == black) { 
                        setColor(sib, red);
                        pNode = parent(pNode);
                    } else { 
                        if (getColor(right(sib)) == black) { 
                            setColor(left(sib), black);
                            setColor(sib, red);
                            R_Rotation(sib);
                            sib = brother(pNode);
                        }
    
                        setColor(sib, getColor(parent(pNode)));
                        setColor(parent(pNode), black);
                        setColor(right(sib), black);
                        L_Rotation(parent(pNode));
                        pNode = root;
                    }
                } else { 
                    TreeNode *sib = brother(pNode);
                    if (getColor(sib) == red) { 
                        setColor(sib, black);
                        setColor(parent(pNode), red);
                        R_Rotation(parent(pNode));
                        sib = brother(pNode);
                    }
    
                    if (getColor(left(sib)) == black && getColor(right(sib)) == black) { 
                        setColor(sib, red);
                        pNode = parent(pNode);
                    } else { 
                        if (getColor(left(sib)) == black) { 
                            setColor(right(sib), black);
                            setColor(sib, red);
                            L_Rotation(sib);
                            sib = brother(pNode);
                        }
    
                        setColor(sib, getColor(parent(pNode)));
                        setColor(parent(pNode), black);
                        setColor(left(sib), black);
                        R_Rotation(parent(pNode));
                        pNode = root;
                    }
                }
            }
            pNode->color = black;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200628213238838.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200628213309837.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200628213512563.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200628213554440.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200628213619798.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200628213644548.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg==,size_16,color_FFFFFF,t_70
[20200628213739196.png]: https://img-blog.csdnimg.cn/20200628213739196.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200628213933380.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200628214003443.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200628214049906.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDYyMzczNg==,size_16,color_FFFFFF,t_70