算法学习---红黑树原理演示总结

目标

理解红黑树，掌握红黑树新增元素方法,总结概括口诀
折线反旋不变色，斜线反旋反着色
单子删除继父业，双子右子选最小
子继父业重调整，平衡规则如添丁

概念

红黑树(Red-Black Tree，简称R-B Tree)，它一种特殊的二叉查找树。
红黑树是特殊的二叉查找树，意味着它满足二叉查找树的特征：任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值。
除了具备该特性之外，红黑树还包括许多额外的信息。

红黑树的每个节点上都有存储位表示节点的颜色，颜色是红(Red)或黑(Black)。
红黑树的特性:
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

关于它的特性，需要注意的是：
第一，特性(3)中的叶子节点，是只为空(NIL或null)的节点。
第二，特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

新增方法：

规则一：默认规则： 为了满足第5条特性每次新增元素，默认为红色

规则二：两种不平衡情况（不平衡情况，指叔叔节点为空情况）：

1. 情况一：黑红红，成一条线，以父节点进行直线方向的反方向旋转后重新着色，父节点变为黑色，祖父节点为红色
   图示：
   方向一

方向二

2. 情况二：黑红红，成折线，以父节点先进行折线方向反向旋转成直线，然后按情况一处理
   方向一

方向二

总结下，不平衡情况解决方法是：
折线反旋不变色，斜线反旋反着色，

规则三：平衡情况，父叔节点都为红色，进行反着色处理，父叔节点改为黑色，爷爷改为红色
例：

平衡情况处理

删除方法：

规则一：无子节点，直接删除

规则二：有一个子节点，子节点直接替换父几点

规则三：有两个子节点：选取右侧最小节点，替换被删除节点，替换后如果出现不平衡情况（叔叔节点为空），进行折线正旋不变色，斜线反旋反着色

图示：

删除双子节点情况

最后，再次回顾下口诀

折线反旋不变色，斜线反旋反着色
单子删除继父业，双子右子选最小
子继父业重调整，平衡规则如添丁

参考资料：https://www.cnblogs.com/skywang12345/p/3624343.html