TreeMap原理实现及常用方法(5)

当待操作节点为左节点时,上面描述了四种场景,而且场景之间可以相互转换,如deleteEntry后进入了场景1,经过场景1的一些列操作后,红黑树的结构并没有调整完成,而是进入了场景2,场景2执行完成后跳出循环,将待操作节点设置为黑色,完成。我们下面用图来说明一下四种场景帮助理解,当然大家最好自己手动画一下。

场景1:

当x是左黑色节点,兄弟节点sib是红色节点,需要兄弟节点由红转黑,父节点由黑转红,按父节点左旋,左旋后树的结构变化了,这时重新赋值sib,这个时候sib指向了x的兄弟节点。

TreeMap原理实现及常用方法

但经过这一系列操作后,并没有结束,而是可能到了场景2,或者场景3和4

场景2:

节点x、x的兄弟节点sib、sib的左子节点和右子节点都为黑色时,需要将该节点sib由黑变红,同时将x指向当前x的父节点

TreeMap原理实现及常用方法

经过场景2的一系列操作后,循环就结束了,我们跳出循环,将节点x设置为黑色,自平衡调整完成。

场景3:

节点x、x的兄弟节点sib、sib的右子节点都为黑色,sib的左子节点为红色时,需要将sib左子节点设置为黑色,sib节点设置为红色,同时按sib右旋,再将sib指向x的兄弟节点

TreeMap原理实现及常用方法

并没有完,场景3的一系列操作后,会进入到场景4

场景4:

节点x、x的兄弟节点sib都为黑色,而sib的左右子节点都为红色或者右子节点为红色、左子节点为黑色,此时需要将sib节点的颜色设置成和x的父节点p相同的颜色,设置x的父节点颜色为黑色,设置sib右孩子的颜色为黑色,左旋x的父节点p,然后将x赋值为root

TreeMap原理实现及常用方法

四种场景讲完了,删除后的自平衡操作不太好理解,代码层面的已经弄明白了,但��果让我自己去实现的话,还是差了一些,还需要再研究。

七. 遍历

遍历比较简单,TreeMap的遍历可以使用map.values(), map.keySet(),map.entrySet(),map.forEach(),这里不再多说。

八. 总结

本文详细介绍了TreeMap的基本特点,并对其底层数据结构红黑树进行了回顾,同时讲述了其自动排序的原理,并从源码的角度结合红黑树图形对put方法、get方法、remove方法进行了讲解,最后简单提了一下遍历操作,若有不对之处,请批评指正,望共同进步,谢谢!

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/cc4283d0a1a10ea5fb552fbdb04fdcad.html