【数据结构】红黑树（R-B Tree）_rbortree

定义

红黑树（Red-Black Tree）是一棵含有红黑结点、能够自平衡的的二叉排序树。它满足如下定义：

1）每个结点或为黑色，或为红色

2）根结点是黑色

3）每个叶子结点是黑色，注意这里的叶子结点是指NIL结点

4）一个红结点的两个子结点必为黑色，即不存在连续的红结点

5）任一结点到每个叶子结点的路径都包含相同数量的黑结点，即对于黑结点平衡

 
 

红黑树的查找

红黑树是一棵不严格的平衡树，但它是一棵严格的排序树/搜索树。

因此，查找操作的时间复杂度自然是O(logn)。

 
 

红黑树的插入

首先明确两点，插入的结点必然是红色（除非是向空树插入根结点），自平衡的调整是向上转化的。

我将红黑树的插入归纳为 3 种情形，这已经比书上的8种情形简单许多！请耐心看图理解一下吧 >_<！

情形1：父为黑——直接插入

红黑树的平衡性针于黑色，所以在一个黑结点下插入一个红结点，并不会对平衡性造成任何影响！直接插入即可！

情形2：父为红，叔叔存在且叔叔为红——直接变色

父亲有个并排的叔叔，且他们俩都是红色，那么就将他们统一变黑，并将问题抛给祖先吧！

这也是唯一一种会增加黑结点层数的情形。

情形3：父为红，叔叔不存在或叔叔为黑——先变色再左/右旋，形状不对就先左/右旋一次

如果你熟悉AVL树，那么你对结点的左/右旋应该有非常直观的感受和理解，这里不再赘述。

 
 

红黑树的删除

第一步，按照二叉搜索树的替代删除思路，分为3种情形：

1）如果被删除结点是叶子结点，则直接删除

2）如果被删除结点只有左/右子树，则让左/右子树直接替代被删除结点，即子承父业

3）如果被删除结点有左右两棵子树，则被删除结点的值被其直接后继(直接前驱)结点的值取代，并转换为对直接后继(直接前驱)结点的删除

第二步，进行自平衡：

情形1：x为红色

这里(以及下面的x)表示的是即将被替换到被删除位置的替代结点，它在原位置进行平衡。

由于被替代的是红结点，不管它被拿到何处，对原处的平衡性也是没有影响的；它的颜色，直接设置为被删除的那个结点的颜色即可。

情形2：x为黑色，兄弟是红色，此时兄弟的两个孩子必然都是黑色

兄弟变黑色，父亲变红色；对父亲左旋。

情形3：x为黑色，兄弟是黑色，兄弟的两个孩子都是黑色

兄弟直接变红色。

情形4：x为黑色，兄弟是黑色，兄弟的左孩子是红色，右孩子是黑色

兄弟左孩子变黑色，兄弟变红色；对兄弟右旋。

情形5：x为黑色，兄弟是黑色，兄弟的左孩子是任意颜色，右孩子是红色

父亲颜色赋给兄弟，父亲变黑色，兄弟右结点变黑色；对父亲左旋。

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

☘️