最新公告
  • 欢迎光临数据科学与编程,我们是数据学科学兴趣交流小组立即加入我们
  • 红黑树

    1,算法思想一

    红黑树主要是对2-3树进行编码,红黑树的基本思想是用标准的二叉查找树(完全由2-节点构成)和一些额外的信息(替换3-节点)来表示2-3树。我们将树的链接分为两种:

    红链接:将两个2-节点连接起来构成一个3-节点。

    黑链接:是2-3树中的普通链接。

    确切的说,3-节点表示为由一条左斜红色链接相连的两个2-节点。这种表示法的一个优点是,我们无需修改就可以直接使用标准的二叉查找树的get方法。

     

     

    2,算法思想二

    红黑树也是一种自平衡二叉树,但在统计上,它的性能要优于平衡二叉树。

    1)      节点是红色或者黑色

    2)      根节点是黑色

    3)      每个叶子结点(NIL节点,虚拟的外部空节点,不真实存在)为黑色

    4)      每个红色节点的两个子节点都是黑色

    5)      从任一节点到其每个叶子结点的所有路径都包含相同数目的黑色节点。

    根据这些性质,可以得出推论:从根到叶子的最长距离,不超过最短距离的两倍。 因为性质5约束了左支和右支黑色节点数目一定相等,性质4又约束了不会有两个相邻的红色节点,最长路径为红黑相间的节点序列,红色节点数最多为黑色节点数-1,因此红色+黑色<黑色*2。

    对红黑树进行增删操作,会是树结构违背这些性质,因此像平衡二叉树一样需要在插入时进行自平衡操作。

    红黑树的节点除了和其它二叉树一样的left/right/parent节点外,还有颜色red/black属性和是否为叶子节点标记isNil。

    3,算法流程(插入)

    由于性质5的约束,所有新插入的节点,都是红色节点,假设插入节点为N,父节点为P,祖父节点为G,叔节点为U,定义一个函数f(A,B),函数返回A节点相对B节点的位置(left/right)。

    1)      如果该树为空树,那么N节点为根节点,根据性质2变色为黑。

    2)      如果P为黑色,那么新增节点为红色,不会违背性质5,满足红黑树性质,不做任何操作。

    3)      如果P为红色,那么分多种子情况:

    • U为红色,把P、U改为黑色、G改为红色。G改为红色后,由于G的父节点也可能是红色,从而违背性质4,这时把G节点视为新插入的节点,递归进行插入操作。

     

    • U为黑色,且f(P,G)=f(N,P),则将P、G变色,对G为根节点的树做单向旋转(f(P,G)=L则LL右旋转,为R则RR左旋转),旋转是为了保证子树上黑色节点总数一致。

     

    • U为黑色,且f(P,G)!=f(N,P),对P进行一次单向旋转,转化为f(P,G)=f(P,N)情况。

     

    总结:红黑树的插入过程主要操作有两种。

    变色,用于调整两个红色节点相邻的情况,以适应性质4

    旋转,用于调整左右子树黑色节点数目不等的情况,以适应情况5.

    4,算法实现

    5,算法分析

    通过”数学归纳法”开始论证高度为h的红黑树,它的包含的内节点个数至少为 2bh(x)-1个”。

    (01) 当树的高度h=0时,
    内节点个数是0,bh(x) 为0,2bh(x)-1 也为 0。显然,原命题成立。

    (02) 当h>0,且树的高度为 h-1 时,它包含的节点个数至少为 2bh(x)-1-1。这个是根据(01)推断出来的!

    下面,由树的高度为 h-1 的已知条件推出“树的高度为 h 时,它所包含的节点树为 2bh(x)-1”。

    当树的高度为 h 时,
    对于节点x(x为根节点),其黑高度为bh(x)。
    对于节点x的左右子树,它们黑高度为 bh(x) 或者 bh(x)-1。
    根据(02)的已知条件,我们已知 “x的左右子树,即高度为 h-1 的节点,它包含的节点至少为 2bh(x)-1-1 个”;

    所以,节点x所包含的节点至少为 ( 2bh(x)-1-1 ) + ( 2bh(x)-1-1 ) + 1 = 2^bh(x)-1。即节点x所包含的节点至少为 2bh(x)-1。
    因此,原命题成立。

    由(01)、(02)得出,”高度为h的红黑树,它的包含的内节点个数至少为 2^bh(x)-1个”。
    因此,“一棵含有n个节点的红黑树的高度至多为2log(n+1)”。

    结论

    红黑树的时间复杂度为: O(lgn)

    6,算法应用

    红黑树在HashMap中的应用

    1)      treeifyBin方法

    当table容量小于最小建树容量64时,调整table大小。最小建树容量的意义在于,重新规划table大小和树化某个哈希桶(哈希值对应下标的容器),都可以提高查询效率。这里取一个经验数字64作为衡量,当table容量超过64,调用TreeNode.treeify方法把链表转化为红黑树。

    2)      putTreeVal方法

    执行二叉树查找,每一次都比较当前节点和待插入节点大小,如果带插入节点较小,那么从当前节点左子树查找,否则从右子树查找,这种查询效率等同于二分法,时间复杂度为O(log2n),待找到空位可以存放节点值之后,执行两个方法。

    balanceInsertion(root,x),平衡插入,一方面把节点插入红黑树中,一方面对红黑树进行变换使之平衡。

    moveRootToFront(table, root)由于红黑树重新平衡之后,root节点可能发生了变化,table里记录的节点不再是红黑树的root,需要重置。

    3)      balanceInsertion方法

    此方法即上边插入分析的代码实现。

    4)      rotateLeft和rotateRight方法

    左旋与右旋,改变节点左右子树引用即可实现。

    本站上原创文章未经作者许可,不得用于商业用途,仅做学习交流使用,本站免责声明。转载请注明出处,否则保留追究法律责任的权利。《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
    数据科学与编程 » 红黑树

    发表评论

    • 52会员总数(位)
    • 312资源总数(个)
    • 31本周发布(个)
    • 3 今日发布(个)
    • 331稳定运行(天)

    提供最优质的博文资源集合

    立即阅览 了解详情