介绍
red-black tree是许多平衡搜索树中的一种，可以保证最坏情况下基本动态集合操作的时间复杂度是O(lgn)
13.1 红黑树的性质
-
红黑树是一棵二叉搜索树，它在每个结点上增加了一个存储位来表示结点颜色，RED或BLACK，它保证没有一条路径会比其它路径长出2倍。
-
一棵红黑树：
- 1、每个结点是红色的，或是黑色的
- 2、根结点是黑色的
- 3、每个叶结点是黑色的(NIL)
- 4、如果一个结点是红色的，它的两个child都是黑色的
- 5、对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
-
通常将注意力放在红黑树的内部结点上，因为它们存储了关键字的值。忽略了叶节点。
-
从某个结点出发到达一个叶结点的任意一条简单路径上的黑色结点数称为黑高(black-height)，记为bh(x)
-
练习13.1-1 In the style of Figure 13.1(a), draw the complete binary search tree of height 3 on the keys {1, 2, …, 15}. Add the NIL leaves and color the nodes in three different ways such that the black- heights of the resulting red-black trees are 2, 3, and 4.
black-height为2:
8b
4 12
2b 6b 10b 14b
1 3 5 7 9 11 13 15
black-height为3:
8b
4b 12b
2b 6b 10b 14b
1 3 5 7 9 11 13 15
black-height为4:(全部是b)
8
4 12
2 6 10 14
1 3 5 7 9 11 13 15
- 练习13.1-2 Draw the red-black tree that results after TREE-INSERT is called on the tree in Figure 13.1 with key 36. If the inserted node is colored red, is the resulting tree a red-black tree? What if it is colored black?
红色违反规则4
黑色违反规则5
- 练习13.1-3 Let us define a relaxed red-black tree as a binary search tree that satisfies red- black properties 1, 3, 4, and 5. In other words, the root may be either red or black. Consider a relaxed red-black tree T whose root is red. If we color the root of T black but make no other changes to T, is the resulting tree a red-black tree?
是哒~
- 练习13.1-4 Suppose that we “absorb” every red node in a red-black tree into its black parent, so that the children of the red node become children of the black parent. (Ignore what happens to the keys.) What are the possible degrees of a black node after all its red children are absorbed? What can you say about the depths of the leaves of the resulting tree?
2, 如果该节点的两个子结点都是黑的.
3, 如果仅有一个子结点是红的.
4, 如果两个子结点都是红的.
所得所有叶节点深度相等。
- 练习13.1-5 Show that the longest simple path from a node x in a red-black tree to a descendant leaf has length at most twice that of the shortest simple path from node x to a descendant leaf.
黑高相等，红色至多1/2
- 练习13.1-6 What is the largest possible number of internal nodes in a red-black tree with black-height k? What is the smallest possible number?
最少时没有红结点，2^k-1
最多时每条路径有k-1个红结点，2^2k-1
- 练习13.1-7 Describe a red-black tree on n keys that realizes the largest possible ratio of red internal nodes to black internal nodes. What is this ratio? What tree has the smallest possible ratio, and what is the ratio?
最大是2，根结点black，两个子结点red
最小是0
13.2 旋转
- 旋转是一种能保持二叉搜索树性质的搜索树局部操作。在旋转操作中只有指针改变，其他所有属性都不变。
LEFT-ROTATE(T, x)
y = x.right
x.right = y.left
if y.left != T.nil
y.left.p = x
y.p = x.p
if x.p == T.nil
T.root = y
elif x == x.p.left
x.p.left = y
else x.p.right = y
y.left = x
x.p = y
- 练习13.2-1 Write pseudocode for RIGHT-ROTATE.
RIGHT-ROTATE(T, x)
y = x.left
x.left = y.right
if y.right != T.nil
y.right.p = x
y.p = x.p
if x.p == T.nil
T.root = y
elif x == x.p.left
x.p.left = y
else x.p.right = y
y.right = x
x.p = y
- 练习13.2-2 Argue that in every n-node binary search tree, there are exactly n - 1 possible rotations.
一对父子结点对应一个旋转
父子结点共有n-1个
- 练习13.2-3 Let a, b, and c be arbitrary nodes in subtrees α, β, and γ, respectively, in the left tree of Figure 13.2. How do the depths of a, b, and c change when a left rotation is performed on node x in the figure?
a深度+1
b深度不变
c深度-1
- 练习13.2-4 Show that any arbitrary n-node binary search tree can be transformed into any other arbitrary n-node binary search tree using O(n) rotations. (Hint: First show that at most n - 1 right rotations suffice to transform the tree into a right-going chain.)
对根结点左边的结点，有right child就左旋，对根结点右边的结点，有left child就右旋，可以得到一个排序好的链表
另一个二叉搜索树也这样子，可以得到相同的链表
逆着刚刚的操作，可以把链表转回二叉搜索树，加起来需要O(n)次旋转。
- 练习13.2-5 We say that a binary search tree T1 can be right-converted to binary search tree T2 if it is possible to obtain T2 from T1 via a series of calls to RIGHT-ROTATE. Give an example of two trees T1 and T2 such that T1 cannot be right-converted to T2. Then show that if a tree T1 can be right-converted to T2, it can be right-converted using O(n^2) calls to RIGHT-ROTATE.
T1(1,#,2),T2(2,1,#),T1无法右旋成T2.
O(n^2)是这样来的. 如果T1和T2的根节点不同，那么可以通过O(n)次右旋将T1的根节点变成T2的根节点. 接下来递归调用root的右节点. 可以得到T(n) = T(n-1) + O(n). 所以是O(n^2).
13.3 插入
- 先把T当作一棵普通的二叉搜索树，将结点z插入其中，然后将z着为红色，为保证红黑性质能继续保持，调用一个辅助程序RB-INSERT-FIXUP来对结点重新着色并旋转。
RB-INSERT(T, z)
y = T.nil
x = T.root
while 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
y.color = BLACK
z.p.p.color = RED
z = z.p.p
elif z == z.p.right
z = z.p
LEFT-ROTATE(T, z)
z.p.color = BLACK
z.p.p.color = RED
RIGHT-ROTATE(T, z.p.p)
else(same as then clause with "right" and "left" exchanged)
T.root.color = BLACK
- 练习13.3-1 In line 16 of RB-INSERT, we set the color of the newly inserted node z to red. Notice that if we had chosen to set z’s color to black, then property 4 of a red-black tree would not be violated. Why didn’t we choose to set z’s color to black?
会破坏性质5
- 练习13.3-2 Show the red-black trees that result after successively inserting the keys 41, 38, 31, 12, 19, 8 into an initially empty red-black tree.
https://github.com/gzc/CLRS/blob/master/C13-Red-Black-Trees/13.3.md
- 练习13.3-3 Suppose that the black-height of each of the subtrees α, β, γ, δ, ε in Figures 13.5 and 13.6 is k. Label each node in each figure with its black-height to verify that property 5 is preserved by the indicated transformation.
算法是保持黑高的。
- 练习13.3-4 Professor Teach is concerned that RB-INSERT-FIXUP might set color[nil[T]] to RED, in which case the test in line 1 would not cause the loop to terminate when z is the root. Show that the professor’s concern is unfounded by arguing that RB-INSERT-FIXUP never sets color[nil[T]] to RED.
只有第7行和第13行会修改颜色.
在第7行这个分支，z.p是红的，因为根不可能为红所以z.p.p肯定不是nil,所以这一行不会设置color[nil[T]]. 同理对于13行也是如此.
- 练习13.3-5 Consider a red-black tree formed by inserting n nodes with RB-INSERT. Argue that if n > 1, the tree has at least one red node.
观察RB-INSERT-FIXUP的伪代码，一个分支会减少一个红节点，另一个分支则不变. 当n=2时，红节点 ＝ 黑节点 ＝ 1. 之后每次调用RB-INSERT时会插入一个红节点再调用RB-INSERT-FIXUP,如果为情况2或情况3红节点数不会减少. 而对于情况1，必有新插入的结点为红色结点。所以n>2时红色结点个数至少一个.
- 练习13.3-6 Suggest how to implement RB-INSERT efficiently if the representation for red-black trees includes no storage for parent pointers.
用一个hash table保存父结点。
13.4 删除、
- 和插入操作相比，删除操作要稍微复杂些。
RB-TRANSPLANT(T, u, v)
if u.p == nil
T.root = v
elif u == u.p.left
u.p.left = v
else u.p.right = v
v.p = u.p
RB-DELETE(T, z)
y = z
y-original-color = y.color
if z.left == T.nil
x = z.right
RB-TRANSPLANT(T, z, z.right)
elif z.right == T.nil
x = z.left
RB-TRANSPLANT(T, z, z.left)
else y = TREE-MINIMUM(z.right)
y-original-color = y.color
x = y.right
if y.p == z
x.p = y
else RB-TRANSPLANT(T, y, y.right)
y.right = z.right
y.right.p = y
RB-TRANSPLANT(T, z, y)
y.left = z.left
y.left.p = y
y.color = z.color
if y-original-color == BLACK
RB-DELETE-FIXUP(T, x)
RB-DELETE-FIXUP(T, x)
while x != T.root and x.color == BLACK
if x == x.p.left
w = x.p.right
if w.color == RED
w.color = BLACK
x..color = RED
LEFT-ROTATE(T, x.p)
w = x.p.right
if w.left.color == BLACK and w.right.color == BLACK
w.color = RED
x = x.p
elif w.right.color == BLACK
w.left.color = BLACK
w.color = RED
RIGHT-ROTATE(T, w)
w = x.p.right
w.color = x.p.color
x.p.color = BLACK
w.right.color = BLACK
LEFT-ROTATE(T, x.p)
x = T.root
else (same as then clause with "right" and "left" exchanged)
x.color = BLACK
- 练习13.4
https://github.com/gzc/CLRS/blob/master/C13-Red-Black-Trees/13.4.md
思考题
- 13-1 持久动态集合
a.
插入时需要改变叶结点路径上所有结点。
删除时需要改变被影响的路径。
b.
PERSISTENT-TREE-INSERT(r, k)
if r == NIL
x = MAKE-NEW-NODE(k)
else x = COPY-NODE(r)
if k < r.key
x.left = PERSISTENT-TREE-INSERT(r.left, k)
else
x.right = PERSISTENT-TREE-INSERT(r.right, k)
return x
c.
O(h)的时间和空间。
d.
因为根节点变了，所以引起所有结点的改变。
e.
我都不会在红黑树插入删除= =
- 13-3 AVL树
a.
高度为h的AVL树至少是由h-1和h-2的子树构成，就是一个斐波那契数列。
In the base b representation, the number of digits in Fn is asymptotic to nlogb(fai)
b.
http://courses.csail.mit.edu/6.046/spring04/handouts/ps5-sol.pdf
- 13-4 treap树
