\t\t红黑树原理详解（下）

编程入门行业动态更新时间:2024-10-06 20:36:25

$\t\t红黑树原理<a href=https://www.elefans.com/category/jswz/34/1770044.html style=$ 详解（下）"/>

\t\t红黑树原理详解（下）

b ：黑兄

遇到黑兄就又麻烦了，我们又必须引入要删除的节点的侄子了。所以我们这里再次细分为b1: 黑兄双黑侄 b2: 黑兄左黑侄右红侄 b3: 黑兄右黑侄左红侄。可能你会问b4呢，双红侄的情况呢？其实双红侄的情况同属于b2,b3的情况，所以可以默认用 b2,b3其中一种情况来处理就可以了。

现在我们开始了

b1黑兄双黑侄

注解：我们首先可以肯定的是父节点的左子树高度减一了，所以我们必须想方设法来弥补这个缺陷。如果我们把父节点的右子树高度也减一（兄变成红色）那么父节点这颗树就可以保持平衡了，但整颗树的高度减一，所以我们可以判断，如果父亲是红色，那么我们可以通过把父亲变成黑色来弥补这一缺陷。但如果父亲是黑色呢，既然遇到到黑色了我们就只好往上遍历了。

方法：兄=>红；子=黑；红父=>黑;

往上遍历(黑父);

补充：其实子节点就是空节点，没有必要变。就算遍历上去，父节点也为黑

b2黑兄左黑侄右红侄

注解：绿色表示，颜色不影响修复的方式。依然我们可以肯定父节点的左子树高度减一，所以我们可以通过将父节点旋转下来并且变为黑色来弥补，但由于兄弟被旋转上去了，又导致右子树高度减一，但我们这有一个红侄，所以可以通过红侄变成黑色来弥补。父亲所在位置的颜色不变；(子为空)
方法：兄=>父色；父=>黑；侄=>黑；(子=>黑)；左旋转父节点；

b3 黑兄左红侄右黑侄

注解：绿色表示，颜色不影响修复的方式。依然我们可以肯定父节点的左子树高度减一,同样我们通过父节点左旋转到左子树来弥补这一缺陷。但如果直接旋转的话，我们可以推出左右子树将不平衡(黑父)，或者两个红色节点相遇(红父)；这样将会更加的复杂，甚至不可行。因此，我们考虑首先将兄弟所在子树右旋转，然后再左旋转父子树。这样我们就可以得到旋转后的树。然后通过修改颜色来使其达到平衡，且高度不变。
方法：侄=>父色；父=>黑;右旋转兄；左旋转父；

总结：

如果我们通过上面的情况画出所有的分支图，我们可以得出如下结论

插入操作：解决的是红-红问题

删除操作：解决的是黑-黑问题

即你可以从分支图中看出，需要往上遍历的情况为红红(插入)；或者为黑黑黑（删除）的情况，，如果你认真分析并总结所有的情况后，并坚持下来，红黑树也就没有想象中的那么恐怖了，并且很美妙；

程序样列：

点击这里下载源码

声明：

此文档为《C语言常用数据结构源代码全注解-红黑树源码》所写，此文档遵循GNU FDL协议，你可以修改重发，但因保留原始版权信息；

此文档版本V1.0为初次发布，所以难面有错误的地方，如果你发现任何错误或缺点，非常感谢你发信息联系我。此文档仅供学习使用。

参考文献：

《百度百科红黑树》地址：.htm