红黑树RBT的原理分析及实现

野性酷女 2023-09-28 14:19 25阅读 0赞

## **RBT定义** ##

上一篇文章讲了 [AVL][] 树是自平衡的二叉搜索树；在 add 和 remove 之后是通过节点的左右子节点高度差来判断调节节点的平衡；红黑树RBT，也是自平衡的二叉搜索树；RBT是通过下列条件来约束节点实现的平衡：

*  根节点是黑色；
 *  叶子节点是黑色；
 *  RBT树的节点颜色只有红，黑色；
 *  一条路径上不能出现连续红色；
 *  任意节点到叶子节点的所有路径上黑色节点数相同；

**RBT的叶子节点**

![3e5e917c37ab47a6aa3c9a6574755f62.png_pic_center][]

**连续红色节点**

![在这里插入图片描述][596e79d940044ab3b82a543996e3f8f0.png_pic_center]

**任意节点到叶子节点的所有路径上黑色节点数相同**

![在这里插入图片描述][01c826073fb948ed82fe137d0910dca5.png_pic_center]  
  
  
  这是一颗红黑树，可以观察到任意一个节点到叶子节点的路径上黑色的节点数都是相等的；比如 根节点500到叶子节点的路径一共10条；这10条路径上每一条路径的黑色节点数都是都是3个；再比如 200节点到叶子节点的路径有4条，这4条路径从叶子到200节点的黑色节点都是 2个；RBT的所有节点都遵守这个规则；

## **RBT在add时遇到颜色冲突及解决办法** ##

![60081757e7c8428599885045e8643c03.png_pic_center][]  
   这是target节点与其他节点关系的代称，下面描述会用到；

*  parent 父节点
 *  brother 兄弟节点
 *  grandpa 祖父节点
 *  uncle 叔父节点或者 parent的兄弟节点

当有新节点加入RBT时，新节点的颜色应该是黑色还是红色呢？如果新节点的颜色是黑色，那么从新节点 -> root 路径上的所有节点都会增加一个黑色节点，而其他路径黑色节点数不变，这必然导致要重新调节红黑树；新节点是红色，红色可能会导致颜色冲突也可能不冲突；因此新节点颜色是红色；

![在这里插入图片描述][e36ce24fa5364f839bae0dd8e5df3439.png_pic_center]

上面提到新加入RBT的节点颜色是红色，这样可能造成与其parent节点颜色冲突：连续红色。在这种情况就违反了红黑树的定义，需要调整。那问题是如何调整节点颜色呢？在调整颜色的同时必须要兼顾最后一条性质；那直接将parent节点或者自身的颜色改为黑色来解决冲突就不行了；  
  
  
![在这里插入图片描述][d51d44d48ef245fb916d1a8324b4da43.png_pic_center]

上图可以看到，这样直接修改节点颜色虽然是可以解决颜色冲突的问题。但是这样改，又引入了新的问题；我们可以直接看 200 节点，200节点有5条路径到叶子节点，经过200节点左分支的2条路径黑色节点是2个，经过200右分支的3条路径黑色节点是3个；不符合定义的最后一条；

直接修改是不行的，那如何修改呢？这需要一些技巧与AVL树一样，需要通过旋转节点，然后再对节点染色；不过与AVL树不一样的是，RBT在旋转之后重新染色还需要考虑uncle节点的颜色；

*  **uncle节点是黑色的处理;  
      
      
    ![在这里插入图片描述][4b4871b1ab0e4f3d9427f2ad6311ab44.png_pic_center]**  
      
    
 *  **uncle是红色的处理**

![在这里插入图片描述][fac755b2e7f144b5b8c9c493da6c6216.png_pic_center]

## **RBT在delete时的颜色调整** ##

在delete时，删除的是红色节点就不会破坏红黑树的定义；如果删除黑色节点，就会破坏最后一条规则了；那如何解决黑色节点被删除的问题呢？经过被删除黑色节点的分支，比不经过该节点的分支少了一个黑色节点。这种情况有2种解决办法：

*  **1.通过旋转向兄弟节点或兄弟的子节点借一个红色节点到被删除节点所在分支将其染黑；这样可以使兄弟分支的黑色节点数不变又让被删除分支补充了一个黑色节点，保持黑色节点的平衡；**
 *  **2.如果兄弟节点或者兄弟节点的子节点没有红色节点，就让兄弟节点也减少一个黑色节点（把兄弟节点染红）；这样可以保持被删除节点的parent节点左右分支的黑色节点数相等；** 
    
     *  **2.1如果parent是红色，直接将parent染黑，增加一个黑色节点即可达到平衡；**
     *  **2.2如果parent是黑色，grandpa节点就左右失衡了，因此还要继续向上向uncle分支借红色节点；在这个过程中借不到节点就把兄弟变红，直到借到红色节点或者到root节点为止；**

图解上面2大类情况，第一种情况分为：兄弟红色向兄弟节点借，兄弟节点的子节点有红色向子节点借；

*  1.1 **brother是红色向兄弟节点借一个 节点**

![e3f212b4e17147699b77af9164a2c65a.png_pic_center][]

*  1.2 **brother是黑色，并且有红色的子节点；向兄弟的子节点借一个节点；（PS:这里要注意红色子节点的位置,也是分为 RR,LL,RL ,LR四种类型，不同类型旋转次数不同，下面这个例子是RR 型；后面还会再讲RL）**

![d62b3646273f4e0c82fde381438e461c.png_pic_center][]

*  **2.1 兄弟及其子节点都是黑色且parent是红色，直接染黑 parent**

![936fc96767604d69b5d55fe4ab65848e.png_pic_center][]

*  **2.2 兄弟及其子节点都是黑色，parent是黑色；继续向上借直到root或者借到节点为止；其实这种情况又回到了前面的几种类型了；**

![c239482a77774c65b61fe030eae0bb54.png_pic_center][]

以上就是红黑树对于delete时，删除了黑色节点时的处理方法；总共就2种不同类型的方式：

*  通过旋转增加一个黑色节点；
 *  不能增加该分支的黑色节点就将另一个分支也减少一个黑色节点，以此来达到平衡；

上面讲到，在向兄弟子节点借红色节点时要注意红色节点的位置；这个其实跟add操作一样，分四种类型：LL ,LR ,RR ,RL ;其中LL ,RR只需一次旋转；RL ,LR 需要2次旋转；下面以RL为例：

![49e5ef8f73a647e499d95d78ddb402a1.png_pic_center][]

以上是对红黑树add和remove的分析，代码：[Gitee-RBT][]

测试：

@Test
        public void test(){
        
            for (int i = 0; i < 10; i++) {
        
                addVal(i);
            }
            System.out.println("++++++++++++++++add test+++++++++++++++");
            print();
            System.out.println("\n++++++++++++++++delete test+++++++++++++++");
            deleteVal(8);
            print();
        }

测试结果可以在网站：[test网站 ][test_]查看结果；

![Image 1][]

[AVL]: https://blog.csdn.net/m0_37550986/article/details/125629666?spm=1001.2014.3001.5501
[3e5e917c37ab47a6aa3c9a6574755f62.png_pic_center]: https://img-blog.csdnimg.cn/3e5e917c37ab47a6aa3c9a6574755f62.png#pic_center
[596e79d940044ab3b82a543996e3f8f0.png_pic_center]: https://img-blog.csdnimg.cn/596e79d940044ab3b82a543996e3f8f0.png#pic_center
[01c826073fb948ed82fe137d0910dca5.png_pic_center]: https://img-blog.csdnimg.cn/01c826073fb948ed82fe137d0910dca5.png#pic_center
[60081757e7c8428599885045e8643c03.png_pic_center]: https://img-blog.csdnimg.cn/60081757e7c8428599885045e8643c03.png#pic_center
[e36ce24fa5364f839bae0dd8e5df3439.png_pic_center]: https://img-blog.csdnimg.cn/e36ce24fa5364f839bae0dd8e5df3439.png#pic_center
[d51d44d48ef245fb916d1a8324b4da43.png_pic_center]: https://img-blog.csdnimg.cn/d51d44d48ef245fb916d1a8324b4da43.png#pic_center
[4b4871b1ab0e4f3d9427f2ad6311ab44.png_pic_center]: https://img-blog.csdnimg.cn/4b4871b1ab0e4f3d9427f2ad6311ab44.png#pic_center
[fac755b2e7f144b5b8c9c493da6c6216.png_pic_center]: https://img-blog.csdnimg.cn/fac755b2e7f144b5b8c9c493da6c6216.png#pic_center
[e3f212b4e17147699b77af9164a2c65a.png_pic_center]: https://img-blog.csdnimg.cn/e3f212b4e17147699b77af9164a2c65a.png#pic_center
[d62b3646273f4e0c82fde381438e461c.png_pic_center]: https://img-blog.csdnimg.cn/d62b3646273f4e0c82fde381438e461c.png#pic_center
[936fc96767604d69b5d55fe4ab65848e.png_pic_center]: https://img-blog.csdnimg.cn/936fc96767604d69b5d55fe4ab65848e.png#pic_center
[c239482a77774c65b61fe030eae0bb54.png_pic_center]: https://img-blog.csdnimg.cn/c239482a77774c65b61fe030eae0bb54.png#pic_center
[49e5ef8f73a647e499d95d78ddb402a1.png_pic_center]: https://img-blog.csdnimg.cn/49e5ef8f73a647e499d95d78ddb402a1.png#pic_center
[Gitee-RBT]: https://gitee.com/myd123/data-struct/blob/master/balanceTree/src/main/java/R20220707/RBT.java
[test_]: https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
[Image 1]: