近期看io相关文章,在看到linux下epoll组织结构的时候,偶然发现epoll居然也是用红黑树作为socket的存储结构。意识到红黑树确实是一个性能很良好的组织结构。之前也浏览过几次红黑树相关的操作原理,但都没能理解透彻,这次,希望能够把它研究透彻,并把它记录下来。
这一篇,先分析红黑树的添加。(以TreeMap源码作分析)
1,首先,按照先根遍历找到需要添加节点的父节点及在父节点上的插入位置(左孩子还是右孩子)。
2,然后将此状态下的该插入节点x(默认为红色)到爷爷节点g(包含叔叔节点ps,和堂兄弟节点psl,psr)的数据结构画出来(只以插入节点的父亲节点p为pp的做孩子距离,反之镜像操作)
case1:要插入的节点是根节点,这时直接将x置为黑色
case2:p为黑色,这时整棵树自然符合红黑树特性,所以不用做任何操作
case3: p为红色,ps也为红色,将p和ps置为黑色,g置为红色,这样,就保证g以下符合了红黑树的特性,但是因为p换了颜色,将g传递给x作递归操作。
case4:p为红色 ,ps为黑色,这时又分两种情况:
case4-1: x是p的左孩子,这时x和p同为红色且紧邻,这时单纯的通过变色已经不能满足红黑树的特性,所以,还要借用旋转来平衡整棵g以下的红黑树,注意,在这里,旋转在不变色的基础上并不会立刻改变红黑树的既有情况,而是将插入节点后所得的g以下的红黑树更加平衡,再结合变色控制使得整棵树符合红黑树特性。更通俗的讲就是将左树的某一个红色节点移到g节点,然后进行变色。
case4-2:x是p的右孩子,这时x和p同为红色且紧邻,这时同样期望通过右旋转来达到平衡整个红黑树的目的,但是因为p的左孩子长度不够,暴力右旋转的话,会将左子树的bh(黑色节点路径总数)变小,改变了原有红黑树的特性,这违反了红黑树的原则,所以,解决办法是将x先左旋转,使得g左子树bh足够长,满足右旋条件,再进行右旋转,最后通过变色方式使得整个树维持红黑树的特性。
最后,附上TreeMap中插入关于红黑树特性调整部分源码,加深理解。
总结一下转换原则,1,如果可以仅仅通过变色来使得红黑树平衡,则只进行变色2,如果需要进行旋转的话,旋转的反方向孩子侧要确保比旋转侧方向孩子树高高出两层,才能保证旋转后有平衡的可能性,如果此时红黑树平衡,则不需要后续操作,3,如果此时依然不平衡,则将操作节点的父节点置为红色,来拥有后续通过变色达到平衡的可能性