Red-Black Tree (ZH && EN)

或许你需要同时打开两份此文章,上下对照理解 || Maybe you need to open two copies of this article at the same time.
mahamah.png

Introduction || 介绍

A red-black tree (RBT) is a balanced version of a Binary Search Tree guaranteeing that the basic operations (search, predecessor, successor, minimum, maximum, insert and delete) have a logarithmic worst case performance.
红黑树(RBT)是二叉搜索树的平衡版本,能保证基本操作(搜索,前驱,后继,最小,最大,插入和删除)具有对数最坏情况的性能。

Binary search trees (BSTs) have the disadvantage that they can become unbalanced after some insert or delete operations. In the worst case, this could lead to a tree where the nodes build a linked list as shown in the following example:

二叉搜索树(BST)的缺点是它们在一些插入或删除操作之后可能变得不平衡。 在最坏的情况下,这可能会变成链接列表的树,如以下示例所示:

1
2
3
4
5
6
7
a
\
b
\
c
\
d

To prevent this issue, RBTs perform rebalancing operations after an insert or delete and store an additional color property at each node which can either be red or black. After each operation a RBT satisfies the following properties:

为了防止出现此问题,RBT在插入或删除后执行重新平衡操作,并在每个节点上存储其他颜色属性,可以是红色或黑色。 每次操作后,RBT都满足以下属性:

Properties || 属性

  1. Every node is either red or black

  2. The root is black

  3. Every leaf (nullLeaf) is black

  4. If a node is red, then both its children are black

  5. For each node, all paths from the node to descendant leaves contain the same number of black nodes

  1. 每个节点都是红色或黑色

  2. 根是黑色的

  3. 叶节点(nullLeaf)都是黑色的

  4. 如果节点为红色,则其子节点均为黑色

  5. 对于每个节点,从节点到后代叶子的所有路径都包含相同数量的黑色节点

Property 5 includes the definition of the black-height of a node x, bh(x), which is the number of black nodes on a path from this node down to a leaf not counting the node itself.
From [CLRS]
属性5包括节点x的黑色高度的定义,bh(x),它是从该节点到不计算节点本身的叶子的路径上的黑色节点的数量。(来自 [CLRS])

译注: CLRS 是指《算法导论》

Methods || 方法

Nodes:

  • nodeX.getSuccessor() Returns the inorder successor of nodeX
  • nodeX.minimum() Returns the node with the minimum key of the subtree of nodeX
  • nodeX.maximum() Returns the node with the maximum key of the subtree of nodeX
    Tree:
  • search(input:) Returns the node with the given key value
  • minValue() Returns the minimum key value of the whole tree
  • maxValue() Returns the maximum key value of the whole tree
  • insert(key:) Inserts the key value into the tree
  • delete(key:) Delete the node with the respective key value from the tree
  • verify() Verifies that the given tree fulfills the red-black tree properties

The rotation, insertion and deletion algorithms are implemented based on the pseudo-code provided in [CLRS]

节点:

  • nodeX.getSuccessor() 返回nodeX的inorder后继
  • nodeX.minimum() 返回具有nodeX子树最小键的节点
  • nodeX.maximum() 返回具有nodeX子树的最大键的节点
    树:
  • search(input:) 返回具有给定键值的节点
  • minValue() 返回整个树的最小键值
  • maxValue()返回整个树的最大键值
  • insert(key:) 将键值插入树中
  • delete(key:) 使用树中相应的键值删除节点
  • verify() 验证给定的树是否满足红黑树属性

旋转,插入和删除算法基于[CLRS]中提供的伪代码实现

Implementation Details || 实施细节

For convenience, all nil-pointers to children or the parent (except the parent of the root) of a node are exchanged with a nullLeaf. This is an ordinary node object, like all other nodes in the tree, but with a black color, and in this case a nil value for its children, parent and key. Therefore, an empty tree consists of exactly one nullLeaf at the root.
为方便起见,所有指向子节点的nil指针或节点的父节点(根节点的父节点)都与nullLeaf交换。 这是一个普通的节点对象,就像树中的所有其他节点一样,但是使用黑色,在这种情况下,它的子节点是父节点和键的nil值。 因此,空树在根处只包含一个nullLeaf。

Rotation || 旋转

Left rotation (around x):
Assumes that x.rightChild y is not a nullLeaf, rotates around the link from x to y, makes y the new root of the subtree with x as y’s left child and y’s left child as x’s right child, where n = a node, [n] = a subtree

左旋(围绕x):
假设x.rightChild y不是nullLeaf,围绕从x到y的链接旋转,使y成为子树的新根,x为y的左子,y的左子为x的右子,其中 n = a node, [n] = a subtree

1
2
3
4
5
6
| |
x y
/ \ ~> / \
[A] y x [C]
/ \ / \
[B] [C] [A] [B]

Right rotation (around y):
Assumes that y.leftChild x is not a nullLeaf, rotates around the link from y to x, makes x the new root of the subtree with y as x’s right child and x’s right child as y’s left child, where n = a node, [n] = a subtree

右旋(围绕y):
假设y.leftChild x不是nullLeaf,围绕从y到x的链接旋转,使x成为子树的新根,其中y为x的右子,x的右子为y的左子,其中 n = a node, [n] = a subtree

1
2
3
4
5
6
| |
x y
/ \ <~ / \
[A] y x [C]
/ \ / \
[B] [C] [A] [B]

As rotation is a local operation only exchanging pointers it’s runtime is O(1).
由于旋转是仅交换指针的本地操作,因此它的运行时为O(1)。

Insertion || 插入

We create a node with the given key and set its color to red. Then we insert it into the the tree by performing a standard insert into a BST. After this, the tree might not be a valid RBT anymore, so we fix the red-black properties by calling the insertFixup algorithm.
The only violation of the red-black properties occurs at the inserted node z and its parent. Either both are red, or the parent does not exist (so there is a violation since the root must be black).

我们用给定的键创建一个节点,并将其颜色设置为红色。 然后我们通过在BST中执行标准插入将其插入树中。 在此之后,树可能不再是有效的RBT,因此我们通过调用insertFixup算法来修复红黑属性。
唯一违反红黑属性的情况发生在插入的节点z及其父节点上。 两者都是红色,或者父级不存在(因此存在违规,因为根必须是黑色)。

We have three distinct cases:
Case 1: The uncle of z is red. If z.parent is left child, z’s uncle is z.grandparent’s right child. If this is the case, we recolor and move z to z.grandparent, then we check again for this new z. In the following cases, we denote a red node with (x) and a black node with {x}, p = parent, gp = grandparent and u = uncle

我们有三个不同的案例:
案例1: z的叔叔是红色的。 如果z.parent留给孩子,z的叔叔是z.grandparent的右孩子。 如果是这种情况,我们重新着色并将z移动到z.grandparent,然后我们再次检查这个新z。 在下面的例子中,我们用(x)表示红色节点,用{x}表示黑色节点,p =父,gp =祖父母,u =叔叔

1
2
3
4
5
6
7
8
| |
{gp} (newZ)
/ \ ~> / \
(p) (u) {p} {u}
/ \ / \ / \ / \
(z) [C] [D] [E] (z) [C] [D] [E]
/ \ / \
[A] [B] [A] [B]

Case 2a: The uncle of z is black and z is right child. Here, we move z upwards, so z’s parent is the newZ and then we rotate around this newZ. After this, we have Case 2b.
案例2a: z的叔叔是黑人,z是右孩子。 在这里,我们将z向上移动,因此z的父级是newZ,然后我们围绕这个newZ旋转。 在此之后,我们有案例2b。

1
2
3
4
5
6
7
8
| |
{gp} {gp}
/ \ ~> / \
(p) {u} (z) {u}
/ \ / \ / \ / \
[A] (z) [D] [E] (newZ) [C] [D] [E]
/ \ / \
[B] [C] [A] [B]

Case 2b: The uncle of z is black and z is left child. In this case, we recolor z.parent to black and z.grandparent to red. Then we rotate around z’s grandparent. Afterwards we have valid red-black tree.
案例2b: z的叔叔是黑人而z是小孩子。 在这种情况下,我们将z.parent重新着色为黑色,将z.grandparent重新着色为红色。 然后我们围绕z的祖父母转动。 之后我们有了有效的红黑树。

1
2
3
4
5
6
7
8
| |
{gp} {p}
/ \ ~> / \
(p) {u} (z) (gp)
/ \ / \ / \ / \
(z) [C] [D] [E] [A] [B] [C] {u}
/ \ / \
[A] [B] [D] [E]

Running time of this algorithm:

  • Only case 1 may repeat, but this only h/2 steps, where h is the height of the tree
  • Case 2a -> Case 2b -> red-black tree
  • Case 2b -> red-black tree
    As we perform case 1 at most O(log n) times and all other cases at most once, we have O(log n) recolorings and at most 2 rotations.
    The overall runtime of insert is O(log n).
    该算法的运行时间:
  • 只有案例1可以重复,但这只有h / 2步,其中h是树的高度
  • 案例2a -> 案例2b -> 红黑树
  • 案例2b -> 红黑树
    由于我们在最多O(log n)次执行情况1并且所有其他情况最多执行一次,我们有O(log n)重新着色并且最多2次旋转。
    insert的整个运行时为O(log n)。

Deletion || 删除

We search for the node with the given key, and if it exists we delete it by performing a standard delete from a BST. If the deleted nodes’ color was red everything is fine, otherwise red-black properties may be violated so we call the fixup procedure deleteFixup.
Violations can be that the parent and child of the deleted node x where red, so we now have two adjacent red nodes, or if we deleted the root, the root could now be red, or the black height property is violated.
We have 4 cases: We call deleteFixup on node x
Case 1: The sibling of x is red. The sibling is the other child of x’s parent, which is not x itself. In this case, we recolor the parent of x and x.sibling then we left rotate around x’s parent. In the following cases s = sibling of x, (x) = red, {x} = black, |x| = red/black.

我们使用给定密钥搜索节点,如果存在,我们通过从BST执行标准删除来删除它。 如果删除的节点的颜色为红色,则一切正常,否则可能会违反红黑属性,因此我们调用修复程序deleteFixup。
违规可以是已删除节点x的父节点和子节点为红色,因此我们现在有两个相邻的红色节点,或者如果我们删除了根节点,则根目录可能是红色,或者违反了黑色高度属性。
我们有4种情况:我们在节点x上调用deleteFixup
案例1: x的兄弟是红色的。 兄弟姐妹是x的父母的另一个孩子,而不是x本身。 在这种情况下,我们重新着色x和x.sibling的父级,然后我们围绕x的父级旋转。 在下列情况下,s = x的兄弟,(x)=红色,{x} =黑色,| x | =红色/黑色。

1
2
3
4
5
6
7
8
| |
{p} {s}
/ \ ~> / \
{x} (s) (p) [D]
/ \ / \ / \
[A] [B] [C] [D] {x} [C]
/ \
[A] [B]

Case 2: The sibling of x is black and has two black children. Here, we recolor x.sibling to red, move x upwards to x.parent and check again for this newX.

案例2: x的兄弟是黑人,有两个黑人孩子。 在这里,我们将x.sibling重新着色为红色,将x向上移动到x.parent并再次检查此newX。

1
2
3
4
5
6
7
8
| |
|p| |newX|
/ \ ~> / \
{x} {s} {x} (s)
/ \ / \ / \ / \
[A] [B] {l} {r} [A] [B] {l} {r}
/ \ / \ / \ / \
[C][D][E][F] [C][D][E][F]

Case 3: The sibling of x is black with one black child to the right. In this case, we recolor the sibling to red and sibling.leftChild to black, then we right rotate around the sibling. After this we have case 4.

案例3: x的兄弟是黑色,右边有一个黑人孩子。 在这种情况下,我们将兄弟重新着色为红色和sibling.leftChild为黑色,然后我们右旋转兄弟。 在此之后我们有案例4。

1
2
3
4
5
6
7
8
9
10
| |
|p| |p|
/ \ ~> / \
{x} {s} {x} {l}
/ \ / \ / \ / \
[A] [B] (l) {r} [A] [B] [C] (s)
/ \ / \ / \
[C][D][E][F] [D]{e}
/ \
[E] [F]

Case 4: The sibling of x is black with one red child to the right. Here, we recolor the sibling to the color of x.parent and x.parent and sibling.rightChild to black. Then we left rotate around x.parent. After this operation we have a valid red-black tree. Here, ||x|| denotes that x can have either color red or black, but that this can be different to |x| color. This is important, as s gets the same color as p.

案例4: x的兄弟是黑色的,右边是一个红色的孩子。 在这里,我们将兄弟重新着色为x.parent和x.parent以及sibling.rightChild的颜色为黑色。 然后我们左右旋转x.parent。 在此操作之后,我们有一个有效的红黑树。 这里,|| x || 表示x可以有红色或黑色,但这可能与| x |不同 颜色。 这很重要,因为s与p具有相同的颜色。

1
2
3
4
5
6
7
8
| |
||p|| ||s||
/ \ ~> / \
{x} {s} {p} {r}
/ \ / \ / \ / \
[A] [B] |l| (r) {x} |l| [E] [F]
/ \ / \ / \ / \
[C][D][E][F] [A][B][C][D]

Running time of this algorithm:

  • Only case 2 can repeat, but this only h many times, where h is the height of the tree
  • Case 1 -> case 2 -> red-black tree
    Case 1 -> case 3 -> case 4 -> red-black tree
    Case 1 -> case 4 -> red-black tree
  • Case 3 -> case 4 -> red-black tree
  • Case 4 -> red-black tree
    As we perform case 2 at most O(log n) times and all other steps at most once, we have O(log n) recolorings and at most 3 rotations.
    The overall runtime of delete is O(log n).

该算法的运行时间:

  • 只有情况2可以重复,但这只有很多次,其中h是树的高度
  • 案例1 -> 案例2 -> 红黑树
    案例1 -> 案例3 -> 案例4 -> 红黑树
    案例1 -> 案例4 -> 红黑树
  • 案例3 -> 案例4 -> 红黑树
  • 案例4 -> 红黑树
    由于我们在最多O(log n)次执行情况2并且所有其他步骤最多执行一次,因此我们有O(log n)重新着色并且最多3次旋转。
    删除的总体运行时间是O(log n)。

Code || 代码

Basic || 基本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import Foundation
private enum RBTreeColor {
case red
case black
}
private enum RotationDirection {
case left
case right
}
// MARK: - RBNode
// 标记: - RBNode
public class RBTreeNode<T: Comparable>: Equatable {
public typealias RBNode = RBTreeNode<T>
fileprivate var color: RBTreeColor = .black
fileprivate var key: T?
var leftChild: RBNode?
var rightChild: RBNode?
fileprivate weak var parent: RBNode?
public init(key: T?, leftChild: RBNode?, rightChild: RBNode?, parent: RBNode?) {
self.key = key
self.leftChild = leftChild
self.rightChild = rightChild
self.parent = parent
self.leftChild?.parent = self
self.rightChild?.parent = self
}
// nullleaf initialization
// 初始化nullleaf
public convenience init(key: T?) {
self.init(key: key, leftChild: nil, rightChild: nil, parent: nil)
self.color = .black
}
var isRoot: Bool {
return parent == nil
}
var isLeaf: Bool {
return rightChild == nil && leftChild == nil
}
var isNullLeaf: Bool {
return key == nil && isLeaf && color == .black
}
var isRightChild: Bool {
return parent?.rightChild == self
}
var isLeftChild: Bool {
return parent?.leftChild == self
}
// Parent node of the parent node
// 父节点的父节点
var grandparent: RBNode? {
return parent?.parent
}
var sibling: RBNode? {
if isLeftChild {
return parent?.rightChild
} else {
return parent?.leftChild
}
}
var uncle: RBNode? {
return parent?.sibling
}
}

RedBlackTree || 红黑树

1
2
3
4
5
6
7
8
9
10
11
public class RedBlackTree<T: Comparable> {
public typealias RBNode = RBTreeNode<T>
fileprivate(set) var root: RBNode
fileprivate(set) var size = 0
fileprivate let nullLeaf = RBNode()
public init() {
root = nullLeaf
}
}

Equatable Protocol|| Equatable 协议

1
2
3
4
5
extension RBTreeNode {
static public func == <T>(lhs: RBTreeNode<T>, rhs: RBTreeNode<T>) -> Bool {
return lhs.key == rhs.key
}
}

Get the precursor node || 获取前驱节点

.getSuccessor()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
extension RBTreeNode {
public func getSuccessor() -> RBNode? {
if let rightChild = self.rightChild {
if !rightChild.isNullLeaf {
return rightChild.minimun()
}
}
var currentNode = self
var parent = currentNode.parent
while currentNode.isRightChild {
if let parent = parent {
currentNode = parent
}
parent = currentNode.parent
}
return parent
}
}

Searching || 搜索

.minimun() && .maximum()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
extension RBTreeNode {
public func minimun() -> RBNode? {
if let leftChild = leftChild {
if !leftChild.isNullLeaf {
return leftChild.minimun()
}
return self
}
return self
}
public func maximum() -> RBNode? {
if let rightChild = rightChild {
if !rightChild.isNullLeaf {
return rightChild.maximum()
}
return self
}
return self
}
}

.search(input:)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
extension RedBlackTree {
public func search(input: T) -> RBNode? {
return search(key: input, node: root)
}
fileprivate func search(key: T, node: RBNode?) -> RBNode? {
guard let node = node else {
return nil
}
if !node.isNullLeaf {
if let nodeKey = node.key {
if key == nodeKey {
return node
} else if key < nodeKey {
return search(key: key, node: node.leftChild)
} else {
return search(key: key, node: node.rightChild)
}
}
}
return nil
}
}

.minValue()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
extension RedBlackTree {
public func minValue() -> T? {
guard let minNode = root.minimun() else {
return nil
}
return minNode.key
}
public func maxValue() -> T? {
guard let maxNode = root.maximum() else {
return nil
}
return maxNode.key
}
}

Insertion || 插入

.insert(key:)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
extension RedBlackTree {
public func insert(key: T) {
if root.isNullLeaf {
root = RBNode(key: key)
} else {
insert(input: RBNode(key: key), node: root)
}
}
private func insert(input: RBNode, node: RBNode) {
guard let inputKey = input.key, let nodeKey = node.key else {
return
}
if inputKey < nodeKey {
guard let child = node.leftChild else {
addAsLeftChild(child: input, parent: node)
return
}
if child.isNullLeaf {
addAsLeftChild(child: input, parent: node)
} else {
insert(input: input, node: child)
}
} else {
guard let child = node.rightChild else {
addAsRightChild(child: input, parent: node)
return
}
if child.isNullLeaf {
addAsRightChild(child: input, parent: node)
} else {
insert(input: input, node: child)
}
}
}
private func addAsLeftChild(child: RBNode, parent: RBNode) {
parent.leftChild = child
child.parent = parent
child.color = .red
insertFixup(node: child)
}
private func addAsRightChild(child: RBNode, parent: RBNode) {
parent.rightChild = child
child.parent = parent
child.color = .red
insertFixup(node: child)
}
private func insertFixup(node z: RBNode) {
if !z.isNullLeaf {
guard let parentZ = z.parent else {
return
}
// If both |z| and his parent are red -> violation of red-black property -> need to fix it
// 如果两个 | z | 且而他的父母是红色的 - > 违反红黑属性 - > 需要修复它
if parentZ.color == .red {
guard let uncle = z.uncle else {
return
}
// Case 1: Uncle red -> recolor + move z
// 案例1: 叔叔是红色 -> 重写着色 + 移动z
if uncle.color == .red {
parentZ.color = .black
uncle.color = .black
if let grandparentZ = parentZ.parent {
grandparentZ.color = .red
// Move z to grandparent and check again
// 将 z 移至祖父母并再次检查
insertFixup(node: grandparentZ)
}
}
// Case 2: Uncle black
// 案例 2: 叔叔是黑色
else {
var zNew = z
// Case 2.a: z right child -> rotate
// 案例 2.a: z 左边的孩子 -> 回转
if parentZ.isLeftChild && z.isRightChild {
zNew = parentZ
leftRotate(node: zNew)
} else if parentZ.isRightChild && z.isLeftChild {
zNew = parentZ
rightRotate(node: zNew)
}
// Case 2.b: z left child -> recolor + rotate
// 案例 2.a: z 左边的孩子 -> 回转
zNew.parent?.color = .black
if let grandparentZnew = zNew.grandparent {
grandparentZnew.color = .red
if z.isLeftChild {
rightRotate(node: grandparentZnew)
} else {
leftRotate(node: grandparentZnew)
}
// We have a valid red-black-tree
// 我们有一个有效的红黑树
}
}
}
}
root.color = .black
}
}

Deletion || 删除

.delete() && .deleteFixup()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
extension RedBlackTree {
public func delete(key: T) {
if size == 1 {
root = nullLeaf
size -= 1
} else if let node = search(key: key, node: root) {
if !node.isNullLeaf {
delete(node: node)
size -= 1
}
}
}
private func delete(node z: RBNode) {
var nodeY = RBNode()
var nodeX = RBNode()
if let leftChild = z.leftChild, let rightChild = z.rightChild {
if leftChild.isNullLeaf || rightChild.isNullLeaf {
nodeY = z
} else {
if let successor = z.getSuccessor() {
nodeY = successor
}
}
}
if let leftChild = nodeY.leftChild {
if !leftChild.isNullLeaf {
nodeX = leftChild
} else if let rightChild = nodeY.rightChild {
nodeX = rightChild
}
}
nodeX.parent = nodeY.parent
if let parentY = nodeY.parent {
// Should never be the case, as parent of root = nil
//
if parentY.isNullLeaf {
root = nodeX
} else {
if nodeY.isLeftChild {
parentY.leftChild = nodeX
} else {
parentY.rightChild = nodeX
}
}
} else {
root = nodeX
}
if nodeY != z {
z.key = nodeY.key
}
// If sliced out node was red -> nothing to do as red-black-property holds
// If it was black -> fix red-black-property
if nodeY.color == .black {
deleteFixup(node: nodeX)
}
}
private func deleteFixup(node x: RBNode) {
var xTmp = x
if !x.isRoot && x.color == .black {
guard var sibling = x.sibling else {
return
}
// Case 1: Sibling of x is red
if sibling.color == .red {
// Recolor
sibling.color = .black
if let parentX = x.parent {
parentX.color = .red
// Rotation
if x.isLeftChild {
leftRotate(node: parentX)
} else {
rightRotate(node: parentX)
}
// Update sibling
if let sibl = x.sibling {
sibling = sibl
}
}
}
// Case 2: Sibling is black with two black children
if sibling.leftChild?.color == .black && sibling.rightChild?.color == .black {
// Recolor
sibling.color = .red
// Move fake black unit upwards
if let parentX = x.parent {
deleteFixup(node: parentX)
}
// We have a valid red-black-tree
} else {
// Case 3: a. Sibling black with one black child to the right
if x.isLeftChild && sibling.rightChild?.color == .black {
// Recolor
sibling.leftChild?.color = .black
sibling.color = .red
// Rotate
rightRotate(node: sibling)
// Update sibling of x
if let sibl = x.sibling {
sibling = sibl
}
}
// Still case 3: b. One black child to the left
else if x.isRightChild && sibling.leftChild?.color == .black {
// Recolor
sibling.rightChild?.color = .black
sibling.color = .red
// Rotate
leftRotate(node: sibling)
// Update sibling of x
if let sibl = x.sibling {
sibling = sibl
}
}
// Case 4: Sibling is black with red right child
// Recolor
if let parentX = x.parent {
sibling.color = parentX.color
parentX.color = .black
// a. x left and sibling with red right child
if x.isLeftChild {
sibling.rightChild?.color = .black
// Rotate
leftRotate(node: parentX)
}
// b. x right and sibling with red left child
else {
sibling.leftChild?.color = .black
//Rotate
rightRotate(node: parentX)
}
// We have a valid red-black-tree
xTmp = root
}
}
}
xTmp.color = .black
}
}

Rotation || 旋转

.rotate()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
extension RedBlackTree {
/*
* Left rotation around node x
* Assumes that x.rightChild y is not a nullLeaf, rotates around the link from x to y,
* makes y the new root of the subtree with x as y's left child and y's left child as x's right
* child, where n = a node, [n] = a subtree
* 左旋(围绕x):
*假设x.rightChild y不是nullLeaf,围绕从x到y的链接旋转,使y成为子树的新根
*x为y的左子,y的左子为x的右子,其中 n = a node, [n] = a subtree
* | |
* x y
* / \ ~> / \
* [A] y x [C]
* / \ / \
* [B] [C] [A] [B]
*/
fileprivate func leftRotate(node x: RBNode) {
rotate(node: x, direction: .left)
}
/*
* Right rotation around node y
* Assumes that y.leftChild x is not a nullLeaf, rotates around the link from y to x,
* makes x the new root of the subtree with y as x's right child and x's right child as y's left
* child, where n = a node, [n] = a subtree
*右旋(围绕y):
*假设y.leftChild x不是nullLeaf,围绕从y到x的链接旋转,使x成为子树的新根
*其中y为x的右子,x的右子为y的左子,其中 n = a node, [n] = a subtree
* | |
* x y
* / \ <~ / \
* [A] y x [C]
* / \ / \
* [B] [C] [A] [B]
*/
fileprivate func rightRotate(node x: RBNode) {
rotate(node: x, direction: .right)
}
/*
* Rotation around a node x
* Is a local operation preserving the binary-search-tree property that only exchanges pointers.
* Runntime: O(1)
* 绕节点 x 旋转
     * 本地操作是否保留仅交换指针的 binary-search-tree 属性。
     * 运行时间:O(1)
*/
private func rotate(node x: RBNode, direction: RotationDirection) {
var nodeY: RBNode? = RBNode()
// Set |nodeY| and turn |nodeY|'s left/right subtree into |x|'s right/left subtree
// 设置 | nodeY | 并将 | nodeY | 的左 / 右子树转换为 | x | 的右 / 左子树
switch direction {
case .left:
nodeY = x.rightChild
x.rightChild = nodeY?.leftChild
x.rightChild?.parent = x
case .right:
nodeY = x.leftChild
x.leftChild = nodeY?.rightChild
x.leftChild?.parent = x
}
// Link |x|'s parent to nodeY
// 链接 | x | 的父节点到 nodeY
nodeY?.parent = x.parent
if x.isRoot {
if let node = nodeY {
root = node
}
} else if x.isLeftChild {
x.parent?.leftChild = nodeY
} else if x.isRightChild {
x.parent?.rightChild = nodeY
}
// Put |x| on |nodeY|'s left
// 把 | x | on | nodeY | 的左边
switch direction {
case .left:
nodeY?.leftChild = x
case .right:
nodeY?.rightChild = x
}
x.parent = nodeY
}
}

Verification || 核查

.verify()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
extension RedBlackTree {
/*
* Verifies that the existing tree fulfills all red-black properties
* Returns true if the tree is a valid red-black tree, false otherwise
*/
/*
      * 验证现有树是否满足所有红黑属性
      * 如果树是有效的红黑树,则返回 true,否则返回 false
     */
public func verify() -> Bool {
if root.isNullLeaf {
print("The tree is empty")
return true
}
return property2() && property4() && property5()
}
// Property 1: Every node is either red or black -> fullfilled through setting node.color of type
// 属性 1:每个节点都是红色或黑色 - > 通过设置类型的 node.color 来填充
// RBTreeColor
// Property 2: The root is black
// 属性 2:根是黑色的
private func property2() -> Bool {
if root.color == .red {
print("Property-Error: Root is red")
return false
}
return true
}
// Property 3: Every nullLeaf is black -> fullfilled through initialising nullLeafs with color = black
// 属性 3:每个 null Leaf 都是黑色的 - > 通过初始化带有 color = black 的 null Leafs 来实现
// Property 4: If a node is red, then both its children are black
// 属性 4:如果节点为红色,则其子节点均为黑色
private func property4() -> Bool {
return property4(node: root)
}
private func property4(node: RBNode) -> Bool {
if node.isNullLeaf {
return true
}
if let leftChild = node.leftChild, let rightChild = node.rightChild {
if node.color == .red {
if !leftChild.isNullLeaf && leftChild.color == .red {
print("Property-Error: Red node with key \(String(describing: node.key)) has red left child")
return false
}
if !rightChild.isNullLeaf && rightChild.color == .red {
print("Property-Error: Red node with key \(String(describing: node.key)) has red right child")
return false
}
}
return property4(node: leftChild) && property4(node: rightChild)
}
return false
}
// Property 5: For each node, all paths from the node to descendant leaves contain the same number
// 属性 5:对于每个节点,从节点到后代叶子的所有路径都包含相同的数字
// of black nodes (same blackheight)
// 黑色节点(同样黑色高度)
private func property5() -> Bool {
if property5(node: root) == -1 {
return false
} else {
return true
}
}
private func property5(node: RBNode) -> Int {
if node.isNullLeaf {
return 0
}
guard let leftChild = node.leftChild, let rightChild = node.rightChild else {
return -1
}
let left = property5(node: leftChild)
let right = property5(node: rightChild)
if left == -1 || right == -1 {
return -1
} else if left == right {
let addedHeight = node.color == .black ? 1 : 0
return left + addedHeight
} else {
print("Property-Error: Black height violated at node with key \(String(describing: node.key))")
return -1
}
}
}

Debug || 调试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
extension RBTreeNode: CustomDebugStringConvertible {
public var debugDescription: String {
var s = ""
if isNullLeaf {
s = "nullLeaf"
} else {
if let key = key {
s = "key: \(key)"
} else {
s = "key: nil"
}
if let parent = parent {
s += ", parent: \(String(describing: parent.key))"
}
if let left = leftChild {
s += ", left = [" + left.debugDescription + "]"
}
if let right = rightChild {
s += ", right = [" + right.debugDescription + "]"
}
s += ", color = \(color)"
}
return s
}
}
extension RedBlackTree: CustomDebugStringConvertible {
public var debugDescription: String {
return root.debugDescription
}
}
extension RBTreeNode: CustomStringConvertible {
public var description: String {
var s = ""
if isNullLeaf {
s += "nullLeaf"
} else {
if let left = leftChild {
s += "(\(left.description)) <- "
}
if let key = key {
s += "\(key)"
} else {
s += "nil"
}
s += ", \(color)"
if let right = rightChild {
s += " -> (\(right.description))"
}
}
return s
}
}
extension RedBlackTree: CustomStringConvertible {
public var description: String {
if root.isNullLeaf {
return "[]"
} else {
return root.description
}
}
}

Reference || 引用:

[CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. “Introduction to Algorithms”, Third Edition. 2009

[CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. 《算法导论》, 第三版. 2009

https://github.com/raywenderlich/swift-algorithm-club/tree/master/Red-Black%20Tree

https://github.com/andyRon/swift-algorithm-club-cn

Title: Red-Black Tree (ZH && EN)

Author: Tuski

Published: 03/17/2019 - 21:06:55

Updated: 03/18/2019 - 13:25:28

Link: http://www.perphet.com/2019/03/Red-Black-Tree-ZH-EN/

Protocol: Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) Reprinted please keep the original link and author

Thx F Sup