红黑树

一、红黑树是什么

红黑树是允许节点里包含最多两个 Node 的二叉树。

二、红黑树要解决什么问题

普通二叉树最大的问题在于,插入有序的序列会使二叉树会成为 N 的深度。
红黑树允许每个节点上最多挂两个 Node, 每当第三个 Node 插入的时候, 把中间值的 Node 往上冒泡。
如果在 root 上有三个 Node, 把中间的 Node 上冒做为新的 root。
由此可见,红黑树的深度是通过 root 往上冒增加的, 从而保证了每条路径到 root 的深度一致为 lg N (黑 Node 数量一致)。

三、红黑树的程序表达

红黑树是二叉树的一个变种, 数据结构和大部分行为与二叉树的几乎一样。
最大的不同是它的 Node 多了一个颜色属性, 颜色为“红”或者“黑”。
当一个 Node 的颜色为红色时, 可以认为该 Node 和其父 Node 属于同一个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
RED = True
BLACK = False

class Node:
def __init__(self, key, value, color):
self.key = key
self.value = value
self.color = color
self.size = 1 # node 的子 node 数量,包括自己

self.left = None
self.right = None

@property
def is_red(self):
return self.color == RED

红黑树有这么几个特性:

  1. 根 Node 的颜色为黑色;
  2. 红 Node 只能悬在左侧;
  3. 新插入的 Node 的颜色默认为红色。 新插入的 Node 总是倾向于和已有的 Node 挤到同一个节点里;
  4. 每个 Node 只能与一个红 Node 连接(包括自己)。 因为红黑树允许每个节点有最多两个 Node;
  5. 每条路径上黑色的 Node 数量一致(深度一致)。
    红黑树的所有行为都是根据以上五点而来。

3.1 增加 Node
插入 Node 遵循一个思路, 即插入的 Node 总是和其它 Node 挤在一个节点里面(插入的 Node 颜色为红色)。
当被插入的 Node 使节点包含多余两个节点时, 把中间的那个 Node 往上冒泡。 最终使 Root 往上冒了一级。

我们从最简单的情况开始分析:
在最开始的情况下, 红黑树只有一个根 Node, 根据特性1, 其颜色为黑色;
现在插入一个 Node, 根据特性3, 其颜色为红色:

  • 当它比 Root 小时, 插入位置在 Root 左侧;
  • 当它比 Root 大时, 插入位置在 Root 右侧, 违反特性2, 这时需要把右侧的红 Node 旋转到左侧。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    RED = True
    BLACK = False

    def rotate_left(node):
    """把 node 右侧的 node 旋转到左侧 """
    new_node = node.right
    node.right = new_node.left
    new_node.left = node
    new_node.color = node.color
    node.color = RED
    new_node.size = node.size
    node.size = 1 + node.left.size + node.right.size

    def rotate_right(node):
    """把 node 左侧的 node 旋转到右侧 """
    new_node = node.left
    node.left = new_node.right
    new_node.right = node
    new_node.color = node.color
    node.color = RED
    new_node.size = node.size
    node.size = 1 + node.left.size + node.right.size

再插入第三个 Node, 其颜色为红色。此时可能会出现三种情况:

  • 情况1, 第三个 Node 比 Root 大,和第二个 Node 并列, 这时违反特性4, 此时只需要把各 Node 的颜色翻转;
  • 情况2, 第三个 Node 比 Root 小,比第二个 Node 小, 这时还是违反特性4, 此时把 Root 右旋得到情况1, 再相应处理;
  • 情况3, 第三个 Node 比 Root 小,比第二个 Node 大, 仍然违反特性4, 此时把第二个 Node 左旋得到情况2, 再相应处理;
1
2
3
4
5
def flip_color(node):
"""把 node 及其子 node 的颜色翻转"""
node.left.color = not node.left.color
node.right.color = not node.right.color
node.color = not node.color

把一个 node 的颜色变成红色, 其实就是在把它往上挤。 flip_color 其实是在把挤在一个节点里的三个 Node 的中间那个往上冒泡。
需要注意的是, Root 的颜色需要始终为黑色。

以上几个例子覆盖了所有的新增 Node 时需要处理的情况。

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
RED = True
BLACK = False

class Node:
def __init__(self, key, value, color):
self.key = key
self.value = value
self.color = color
self.size = 1 # node 的子 node 数量,包括自己

self.left = None
self.right = None

@property
def is_red(self):
return self.color == RED


class RedBlackBST:
def __init__(self, root_node=None):
self._root = root_node

@property
def root(self):
return self._root

@root.setter
def root(self, value):
if value is None:
return
assert isinstance(value, Node)
self._root = value
self._root.color = BLACK

@staticmethod
def rotate_left(node):
"""把 node 右侧的 node 旋转到左侧 """
new_node = node.right
node.right = new_node.left
new_node.left = node
new_node.color = node.color
node.color = RED
new_node.size = node.size
node.size = 1 + node.left.size + node.right.size
return node

@staticmethod
def rotate_right(node):
"""把 node 左侧的 node 旋转到右侧 """
new_node = node.left
node.left = new_node.right
new_node.right = node
new_node.color = node.color
node.color = RED
new_node.size = node.size
node.size = 1 + node.left.size + node.right.size
return node

@staticmethod
def flip_color(node):
"""把 node 及其子 node 的颜色翻转"""
node.left.color = not node.left.color
node.right.color = not node.right.color
node.color = not node.color
return node

@staticmethod
def is_red(node):
if node is None:
return False
return node.is_red

def _put(self, key, value, node):
if node is None:
return Node(key, value, BLACK)

if key < node.key:
node.left = self._put(key, value, node.left)
elif key > node.key:
node.right = self._put(key, value, node.right)
else:
node.value = value

if not node.left.is_red and node.right.is_red:
node = RedBlackBST.rotate_left(node)
if node.left.is_red and node.left.left.is_red:
node = RedBlackBST.rotate_right(node)
if node.left.is_red and node.right.is_red:
node = RedBlackBST.flip_color(node)
node.size = node.left.size + node.right.size + 1
return node

def put(self, key, value):
self.root = self._put(key, value, self.root)

3.2 删除 Node
被删除的 Node 只能是红色的 Node, 否则会违反红黑树的特性 5。
如果它不是叶 Node, 则把它替换成它右侧的最小 Node, 然后再删除右侧的最小 Node。

也就是说最终的删除操作是在删除某个树里面的最小 Node, 而且这个 Node 必须放在一个包含两个 Node 节点中。

最小的 Node 一定是左侧的子 Node, 所以删除某个树的最小 Node 也就是一个递归的从左侧子树里面删除最小 Node 的方法:

1
2
3
4
5
6

def delete_min(node):
if node.left is None:
return None
node.left = delete_min(node.left)
return node

但被删除的 Node 必须放在一个包含两个 Node 节点中,如果左侧的节点不是包含两个 node 的节点, 那还要做点什么呢?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Red = True
Black = False

def is_red(node):
if node is None:
return False
return node.color == Red

def do_something(node):
return node


def delete_min(node):
if node.left is None:
return None
# 如果左侧的节点不是包含两个 node 的节点, 那还要做点什么呢?
if not is_red(node.left) and not is_red(node.left.left):
node = do_something(node)
node.left = delete_min(node.left)
return node

我们还要做点什么呢?我们有两个办法, 一是把 node.left 和 node 自己放到一个节点来, 二是把 node.left 和 node.left.left 放到一个节点来。

  • 对 R 执行 flip_color 把左右两个子 Node 和 R 放到一个节点里面来, 如果 R 之前和它的父 Node 在一个节点,则 R 降一级, 否则两个子节点升一级;
  • 如果 R 的右节点只有一个 Node, 那这时什么都不用做了, 如果 R 的右节点有两个 Node, 那么就有四个 Node 在一个节点了, 这时我们把右节点的一个 Node 移到左边来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def move_red_left(node):
flip_color(node)
if is_red(node.right.left):
node.right = rotate_right(node.right)
node = rotate_left(node)
flip_color(node)
return node

do_something = move_red_left

```
很明显 `move_red_left` 可能会造成一些有三个 node 的节点, 在红黑树的操作过程中, 临时的 3 个 Node 的节点是 OK 的, 最后再去平衡以下它就好了。
```python
def balance_node(node):
if is_red(node.right):
node = rotate_left(node)
if is_red(node.left) and is_red(node.left.left):
node = rotate_right(node)
if is_red(node.left) and is_red(node.right):
flip_color(node)
node.size = size(node.left) + size(node.right) + 1
return node

至此, 我们就完整地实现了 delete_min 的过程。

我们再来实现完整的 delete 过程。
从 node 删除 Node x 时, x.key 可能等于 node.key, 可能大于或者小于 node.key。
当 x.key 小于 node.key 时, 从 node 左侧的子树中继续删除 key;
当 x.key 大于 node.key 时, 从 node 右侧的子树中继续删除 key;
当 x.key 等于 node.key 时, 又要区别 node 是不是叶 Node, 如果是, 则直接删除就好了, 否则就要把 node 换成 node 右侧子树的最小 Node , 再删除右侧子树的最小 Node。

怎么判断 node 是不是叶 Node 呢? 当 node 的左侧和右侧为空时。

显然, delete 也可以用递归实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def delete(node, key):
if key < node.key:
node.left = delete(node.left, key)

else:
if key == node.key and node.left is None and node.right is None:
return None
elif key == node.key:
node.val = get(node.right, min(node.right).key)
node.key = min(node.right).key
node.right = delete_min(node.right)
else:
node.right = delete(node.right, key)

但是这个 delete 方法并没有保证从 node 的左节点或者右节点删除 Node 时, 它们包含两个 Node。所以还需要改进:

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
def move_right_left(node):
flip_color(node)
if is_red(node.left.left):
node = rotate_right(node)
flip_color(node)
return node

def delete(node, key):
if key < node.key:
# 确保从左侧节点删除 Node 时, 左侧节点包含两个 Node
if not is_red(node.left) and not is_red(node.left.left):
node = move_red_left(node)
node.left = delete(node.left, key)

else:
if key == node.key and node.left is None and node.right is None:
return None

# 确保从右侧节点删除 Node 时, 右侧节点包含两个 Node
if not is_red(node.right) and not is_red(node.right.left):
node = move_red_right(node)

if key == node.key:
node.val = get(node.right, min(node.right).key)
node.key = min(node.right).key
node.right = delete_min(node.right)
else:
node.right = delete(node.right, key)

return balance(node)

node 左侧子 Node 为黑色, 右侧为 None 的情况违反红黑树的特性, 所以上述流程中,判断 node 是否为叶 Node 和 Node 右侧是否为单节点的情况可以稍加改进:

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
def move_right_left(node):
flip_color(node)
if is_red(node.left.left):
node = rotate_right(node)
flip_color(node)
return node

def delete(node, key):
if key < node.key:
if not is_red(node.left) and not is_red(node.left.left):
node = move_red_left(node)
node.left = delete(node.left, key)

else:
if is_red(node.left):
# node 左侧为红 Node 时, 把 红 Node 旋转到右边
# 可以略过 move_red_right 的情况,
# 也可以略过检查 node.left is None 的情况
node = rotate_right(node)

if key == node.key and node.right is None:
return None

if not is_red(node.right) and not is_red(node.right.left):
node = move_red_right(node)

if key == node.key:
node.val = get(node.right, min(node.right).key)
node.key = min(node.right).key
node.right = delete_min(node.right)
else:
node.right = delete(node.right, key)

return balance(node)

四、总结

红黑树就是二叉树, 它有两个最根本的特性:允许一个节点两个 Node, 保证每条路径深度相同。
它的其它特性都是实现或者保持以上两个特性的。