技术控

    今日:11| 主题:49448
收藏本版 (1)
最新软件应用技术尽在掌握

[其他] 史上最清晰的红黑树讲解(上)

[复制链接]
九命猫 发表于 2016-10-2 08:09:27
182 2

立即注册CoLaBug.com会员,免费获得投稿人的专业资料,享用更多功能,玩转个人品牌!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本文github地址
  本文以Java TreeMap为例,从源代码层面,结合详细的图解,剥茧抽丝地讲解红黑树(Red-Black tree)的插入,删除以及由此产生的调整过程。
  总体介绍

   Java TreeMap 实现了 SortedMap 接口,也就是说会按照 key 的大小顺序对 Map 中的元素进行排序, key 大小的评判可以通过其本身的自然顺序(natural ordering),也可以通过构造时传入的比较器(Comparator)。
   TreeMap 底层通过红黑树(Red-Black tree)实现 ,也就意味着 containsKey() ,  get() ,  put() ,  remove() 都有着 log(n) 的时间复杂度。其具体算法实现参照了《  算法导论  》。
   
史上最清晰的红黑树讲解(上)-1 (natural,search,源代码,程序员,多线程)

   出于性能原因, TreeMap 是非同步的(not synchronized),如果需要在多线程环境使用,需要程序员手动同步;或者通过如下方式将 TreeMap 包装成(wrapped)同步的:
  [code]SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));[/code]   红黑树是一种近似平衡的二叉查找树,它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一陪。具体来说,红黑树是满足如下条件的二叉查找树(binary search tree):
  
       
  • 每个节点要么是红色,要么是黑色。   
  • 根节点必须是黑色   
  • 红色节点不能连续(也即是,红色节点的孩子和父亲都不能是红色)。   
  • 对于每个节点,从该点至 null (树尾端)的任何路径,都含有相同个数的黑色节点。  
  在树的结构发生改变时(插入或者删除操作),往往会破坏上述条件3或条件4,需要通过调整使得查找树重新满足红黑树的条件。
  预备知识

   前文说到当查找树的结构发生改变时,红黑树的条件可能被破坏,需要通过调整使得查找树重新满足红黑树的条件。调整可以分为两类:一类是颜色调整,即改变某个节点的颜色;另一类是结构调整,集改变检索树的结构关系。结构调整过程包含两个基本操作: 左旋(Rotate Left),右旋(RotateRight)
  左旋

   左旋的过程是将 x 的右子树绕 x 逆时针旋转,使得 x 的右子树成为 x 的父亲,同时修改相关节点的引用。旋转之后,二叉查找树的属性仍然满足。

史上最清晰的红黑树讲解(上)-2 (natural,search,源代码,程序员,多线程)

   TreeMap 中左旋代码如下:
  [code]//Rotate Left
private void rotateLeft(Entry p) {
    if (p != null) {
        Entry r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}[/code]  右旋

   右旋的过程是将 x 的左子树绕 x 顺时针旋转,使得 x 的左子树成为 x 的父亲,同时修改相关节点的引用。旋转之后,二叉查找树的属性仍然满足。
123下一页
友荐云推荐




上一篇:TLS总结(上)——我们为啥需要TLS
下一篇:Tsickle - TypeScript to Closure Annotator
酷辣虫提示酷辣虫禁止发表任何与中华人民共和国法律有抵触的内容!所有内容由用户发布,并不代表酷辣虫的观点,酷辣虫无法对用户发布内容真实性提供任何的保证,请自行验证并承担风险与后果。如您有版权、违规等问题,请通过"联系我们"或"违规举报"告知我们处理。

阿萨德在 发表于 2016-10-4 05:12:14
我本非随便的人,但如果你想随便,那我就随你的便好啦!  
回复 支持 反对

使用道具 举报

eeclqac 发表于 2016-10-8 07:52:03
在哪里跌倒,就在那里多爬一会儿!
回复 支持 反对

使用道具 举报

*滑动验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

我要投稿

推荐阅读

扫码访问 @iTTTTT瑞翔 的微博
回页顶回复上一篇下一篇回列表手机版
手机版/CoLaBug.com ( 粤ICP备05003221号 | 文网文[2010]257号 )|网站地图 酷辣虫

© 2001-2016 Comsenz Inc. Design: Dean. DiscuzFans.

返回顶部 返回列表