首页 > 代码库 > 红黑树的详细介绍一
红黑树的详细介绍一
本文参考《算法导论》
红黑树的性质
红黑树的性质
红黑树是一棵二叉搜索树,它在每个节点上增加了一个存储位来表示结点的颜色,可以是RED或者是BLACK,红黑树确保没有一条路径会比其它路径长2倍,因而是近似平衡的。
树中的每个结点包含5个属性:color、key、left、right、parent,如果一个结点没有子结点或者是父结点,则该结点相应指针属性的值为NIL。可以把NIL视为指向二叉搜索树
的也结点的指针,而把带有关键字的结点视为树的内部结点。
一棵红黑树是满足下面红黑性质的二叉树:
- 每个结点或是红色的,或是黑色的。
- 根节点是黑色的。
- 每个叶结点(NIL)是黑色的。
- 如果一个结点是红色的,则它的两个子结点都是黑色的。
- 对每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点。
引理:一棵有n个内部结点的红黑树的高度至多为2lg(n+1)
一棵使用了公共结点的红黑树如下:
旋转
1、左旋转
LEFT-ROTATE(T,x)
y = x.right //set y x.right = y.left //set x.right if y.left != T.nil y.left.p = x y.p = x.p //link x‘s parent to y if x.p == T.nil T.root = y elif x.p == x.p.left x.p.left = y else x.p.right = y y.left = x //put x on y‘s left x.p = y
2、右旋转
RIGHT-ROTATE(T,y)
x = y.left //set x y.left = x.right if x.right != T.nil x.right.p = y y.p = x.p //link y‘s parent to x if y.p == T.nil T.root = x elif y.p == y.p.left y.p.left = x else y.p.right = x x.right = y //put y on x‘s right y.p = x
红黑树的插入
我们可以在O(lgn)时间内完成想一棵含n个结点的红黑树中插入一个新的结点。为了做到这一点,利用TREE-INSERT过程,将结点z插入树T中,
就好像T是一棵普通的二叉搜索树一样,然后将z着为红色,为了能保持红黑性质,我们设计了一个辅助程序RB-INSERT-FIXUP来对结点重新着色并
旋转。
RB-INSERT(T,z)
y = T.nil x = T.root if x != T.nil y = x if z.key < x.key x = x.left else x = x.right z.p = y if y == T.nil T.root = z elif z.key < y.key y.left = z else y.right = z z.left = T.nil z.right = T.nil z.color = RED RB-INSERT-FIXUP(T,z)
红黑树的修订
RB-INSERT-FIXUP(T,z)
while z.p.color == RED if z.p == z.p.p.left y = z.p.p.right if y.color == RED z.p.color = BLACK //case 1 z.p.p = RED //case 1 y.color = BLACK //case 1 z = z.p.p //case 1 else if z == z.p.right z = z.p //case 2 LEFT-ROTATE(T, z) //case 2 else z.p.color = BLACK //case 3 z.p.p.color = RED //case 3 RIGHT-ROTATE(T, z.p.p) //case 3 else y = z.p.p.left if y.color == RED z.p.color = BLACK y.color = BLACK z.p.p.color = RED z = z.p.p else if z == z.p.left z = z.p RIGHT-ROTATE(T,z) else z.p.color = BLACK z.p.p.color = RED LEFT-ROTATE(T,z.p.p) T.root.color = BLACK
在调用RB-INSERT-FIXUP操作时,哪些红黑性质可能会被破坏呢?性质1和性质3继续成立,因为新插入的红姐点的两个子结点都是哨兵T.nil。性质5,即从一个制定结点开始的每条
简单路径上的黑节点的个数都是相等的,也会成立,因为结点z代替了(黑色)哨兵,并且结点z本省是哨兵孩子的红姐点。这样开来,仅可能被破坏的就是性质2和性质4,即根结点需要为黑
色以及一个红结点不能有哄孩子。这两个性质可能被破坏是因为z被着为红色。如果z是根节点,则破坏了性质2;如果z是父结点是红结点,则破坏了性质4。
在1~15行中的while循环在每次迭代的开头保持下列3个部分的不变式:
- 结点z是红结点。
- 如果z.p是根结点,则z.p是黑结点。
- 如果有任何红黑性质被破坏,则至多只有一条被破坏,或是性质2,或是性质4.如果性质2被破坏,则原因是z是根结点且是红结点。如果性质4被破坏,其原因是z和z.p都是红结点。
证明循环不变式
红黑树的5个性质:
- 每个结点或是红色的,或是黑色的。
- 根节点是黑色的。
- 每个叶结点(NIL)是黑色的。
- 如果一个结点是红色的,则它的两个子结点都是黑色的。
- 对每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点。
初始化:在循环的第一次迭代之前,从一棵正常的红黑树开始,并新增一个红结点z。
要证明当RB-INSERT-FIXUP被调用时,不变式的每个部分都成立,以下是循环不变式。
- 当调用RB-INSERT-FIXUP时,z是新增的红结点。
- 如果z.p是根,那么z.p开始是黑色的,且在调用RB-INSERT-FIXUP之前保持不变。
- 注意在调用RB-INSERT-FIXUP时,性质1、性质3和性质5成立。
反红黑性质的地方。
如果违反了性质4,则由于z的子结点是黑色哨兵,且该树在z加入之前没有其它性质的违反,所以违反必然是因为z和z.p都是红色。而且,没有其它性质被违反。
终止:循环终止是因为z.p是黑色的。这样,树在循环终止时没有违反性质4.根据循环不变式,唯一可能不成立的是性质2。第16行恢复这个性质,所以当RB-INSERT-FIXUP终止时,所
有的红黑性质都成立。
保持:实际需要考虑while循环中的6种情况,而其中三种和另外三种是对称的。取决于z的父结点z.p是z的祖父结点z.p.p的左孩子还是右孩子。根据循环不变式的第二条,如果z.p是根
结点,那么z.p是黑色的,可知结点z.p.p存在。因为只有z.p是红色时才进入一次循环迭代,所以z.p不可能是根结点。因此,z.p.p存在。
情况1和情况2、情况3的区别在于z父亲的兄弟结点的颜色不同。第3行使y指向z的叔结点z.p.p.right,在第4行测试y的颜色。如果y是红色的,那么执行情况1.否则,控制转向情况2和3.
在所有三种情况中,z的祖父结点z.p.p是黑色的,因为它的父结点z.p是红色的,故性质4只在z和z.p之间被破坏。
- 情况1: z的叔结点y是红色
a.因为每次迭代把z.p.p着为红色,结点z.p.p.p在下次迭代的开始是红色。
b.在这次迭代中结点z.p.p.p,且这个结点的颜色不会改变。如果它是根结点,则在此次迭代之前它是黑色,且在下次迭代的开头任是黑色。
2.情况2:z的叔结点y是黑色的且z是一个右孩子
3.情况3:z的叔结点y是黑色的且z是一个左孩子
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。