Java TreeMap源码解析

四、红黑树性质

先看看红黑树的样子:

叶子节点为上图中的NIL节点,国内一些教材中没有这个NIL节点,我们在画图时有时也会省略这些NIL节点,但是我们需要明确,当我们说叶子节点时,指的就是这些NIL节点。

红黑树通过下面5条规则,保证了树是平衡的:

树的节点只有红与黑两种颜色

根节点为黑色的

叶子节点为黑色的

红色节点的字节点必定是黑色的

从任意一节点出发,到其后继的叶子节点的路径中,黑色节点的数目相同

满足了上面5个条件后,就能够保证:根节点到叶子节点的最长路径不会大于根节点到叶子最短路径的2倍。 其实这个很好理解,主要是用了性质4与5,这里简单说下:

假设根节点到叶子节点最短的路径中,黑色节点数目为B,那么根据性质5,根节点到叶子节点的最长路径中,黑色节点数目也是B,最长的情况就是每两个黑色节点中间有个红色节点(也就是红黑相间的情况),所以红色节点最多为B-1个。这样就能证明上面的结论了。

五、红黑树操作

关于红黑树的插入、删除、左旋、右旋这些操作,我觉得最好可以做到可视化,文字表达比较繁琐,我这里就不在献丑了,网上能找到的也比较多,像v_July_v的《教你透彻了解红黑树》。我这里推荐个swf教学视频(视频为英文,大家不要害怕,重点是看图??),7分钟左右,大家可以参考。 这里还有个交互式红黑树的可视化网页,大家可以上去自己操作操作,插入几个节点,删除几个节点玩玩,看看左旋右旋是怎么玩的。

六、总结

TreeMap的key是有序的,增删改查操作的时间复杂度为O(log(n)),为了保证红黑树平衡,在必要时会进行旋转

HashMap的key是无序的,增删改查操作的时间复杂度为O(1),为了做到动态扩容,在必要时会进行resize。


上一篇:
下一篇:
关于尚硅谷
教育理念
名师团队
学员心声
资源下载
视频下载
资料下载
工具下载
加入我们
招聘岗位
岗位介绍
招贤纳师
联系我们
全国统一咨询电话:010-56253825
地址:北京市昌平区宏福科技园综合楼6层(北京校区)

深圳市宝安区西部硅谷大厦B座C区一层(深圳校区)

上海市松江区谷阳北路166号大江商厦6层(上海校区)

武汉市东湖高新开发区中国光谷(武汉校区)