Definition
A red-black tree is a binary search tree that satisfies the following red-black properties:
(1) Every node is either red or black.
(2) The root is black.
(3) Every leaf (NIL) is black.
(4) If a node is red, then both its children are black.
(5) For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.
The black-height of any node x, denoted by bh(x), is the number of black nodes on any simple path from x (x not included) down to a leaf. bh(Tree) = bh(root).
A red-black tree with n internal nodes has height at most 2log(n+1).
红黑树没有左右子树高度差小于等于1的条件!
Insertion
考虑它的叔叔,维护的主要是颜色(性质4)
bottom-up
情况1:N为红,P为红(GP一定为黑),U为红。
令X = T.root,在向下遍历的过程中,我们如果遇到X.right.color = x.left.color = RED时我们将x与它孩子的颜色翻转,即把x涂成红色,把x.right和x.left涂成黑色。如果x的父亲为黑色,没有违反性质;如果x的父亲为红色,那么可以把x当成新插入的红色结点N,那么只需要处理情况2即可。
情况2:N,P都为红(GP一定为黑),U为黑
此情况可分为镜像的四种,可通过旋转转为如下
通过交换GP与P的颜色,然后调用right_rotate(T,GP),此时不再违反任何性质。
1 | //RB-INSERT-FIXUP(T,z) |
(a) A node z after insertion. Because both z and its parent z.p are red, a violation of property 4 occurs. Since z’s uncle y is red, case 1 in the code applies. We recolor nodes and move the pointer z up the tree, resulting in the tree shown in (b). Once again, z and its parent are both red, but z’s uncle y is black. Since z is the right child of z.p, case 2 applies. We perform a left rotation, and the tree that results is shown in (c). Now, z is the left child of its parent, and case 3 applies. Recoloring and right rotation yield the tree in (d), which is a legal red-black tree.
Time Complexity: O(log n)
Deletion
考虑它的兄弟,维护的主要是黑色结点数量(性质5)。
top-down
Time complexity: O(log n)
Code
definition
1 |
|
left-rotation
1 | /* |
right-rotation
1 | /* |
insert
1 | /* |
insert-fixup
1 | /* |
delete
1 | /* |
delete-fixup
1 | /* |
rbtree.h
1 |
|
Rbtree.c
1 | /** |
Exercise
In the red-black tree that results after successively inserting the keys 41; 38; 31; 12; 19; 8 into an initially empty red-black tree, which one of the following statements is FALSE? (2分)
B
A. 38 is the root
B. 19 and 41 are siblings, and they are both red
C. 12 and 31 are siblings, and they are both black
D. 8 is redAfter deleting 15 from the red-black tree given in the figure, which one of the following statements must be FALSE? (2分)
CA. 11 is the parent of 17, and 11 is black
B. 17 is the parent of 11, and 11 is red
C. 11 is the parent of 17, and 11 is red
D. 17 is the parent of 11, and 17 is black
Reference
https://www.cnblogs.com/skywang12345/p/3624177.html
https://blog.csdn.net/weewqrer/article/details/51866488
https://www.cnblogs.com/tongy0/p/5460623.html
https://blog.csdn.net/Woolseyyy/article/details/51530558
《Introduction to Algorithms》