数据结构之旅：红黑树怎样驱动 Set 和 Map
一、红黑树1、定义
红黑树是一种二叉搜索树，在每个节点上增长一个存储位表示结点的颜色(红色或者黑色)。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保不会有一条路径比其他路径长出两倍，因而这种树是一种接近平衡的。和AVL（平衡二叉搜索树）区别就是不需要严格计算并控制平衡因子使得左右子树之间的高度差不高出1的繁琐过程。
2、满足条件
（1）根节点是黑色。
（2）每个结点不是黑色就是红色
（3）对于每个结点，从该结点到其所有后代叶子结点的简单路径上均包含雷同数量的黑色结点。
（4）每个叶子结点都是黑色的（这里的叶子结点和前面差异指的是空结点）。
定理：红黑树中最长路径中的结点的个数不会高出最短路径结点个数的两倍。
3、实现原理
（1）要包管插入结点一定是红色结点，否则会导致结点路径黑色结点个数增长，进而导致其他结点路径的黑色结点数量也要跟着变化。
（2）景象一：插入结点父结点为黑色，则直接插入即可，无需其他处理。
https://i-blog.csdnimg.cn/direct/63d5676e231b4cbda14224643249a9f1.png
（3）景象二：插入结点cur、cur的父结点p和叔叔结点u均为红色(c,p,u均红)。
这种情况只需要颜色变更即可，首先将g变红，p,u变黑，然后假如g为根节点则直接将g变黑即可，假如g不是根节点，则需要将c结点变为cur结点,g,p,u按照雷同规则更新，然后按照上述方法继续调整，直到父节点为黑色或者g为根节点。
https://i-blog.csdnimg.cn/direct/aed1900da28b4e20904121638c05be0d.png
（4）景象三：插入结点的父结点p为红色，而且叔叔结点u为黑色或者不存在的情况。
a、当叔叔结点存在且为黑色的情况：此中cur为p的左节点，而且p为g的左节点。下面图中的cur肯定不是插入结点，假如是插入结点的话，原来的二叉树就不满足红黑树的要求了，因此cur是因为下面结点更新颜色而导致变红的（原来是黑色）。
处理方法:将原来红黑树以g为中心向右旋转，然后举行颜色更新（p变黑，g变红）。
https://i-blog.csdnimg.cn/direct/b5927adddb2e4aecad1b338c8384b5df.png
b、当叔叔结点不存在的情况：此中cur为p的左节点，而且p为g的左节点。这里的cur和上面差异的是，cur可以为当前插入结点，处理方法和上面一样。
https://i-blog.csdnimg.cn/direct/047a95ae762b498b96e2f41cb20e8279.png
c、当cur结点为parent结点的右结点，而且p为g的左节点。这里的cur不是插入结点缘故原由和a一样。处理方法：首先要以parent为中心向左旋转，然后再以g为中心向右旋转，最后将cur变为黑色，然后g变为红色。
https://i-blog.csdnimg.cn/direct/696642607549493d916c834df4d2492a.png
d、当叔叔结点不存在的情况：c结点为p结点的右结点，而且p为g的左节点。处理方式和方案c一样。
https://i-blog.csdnimg.cn/direct/6f9214bd69244bd283695427a42350d5.png
别的当p为g的右节点时，和上面一样仍旧有四种情况，处理方式：在旋转过程中方向相反即可。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]