红黑树

发表于 | 分类于 | 阅读次数:

综述

本文主要介绍红黑树的概念、方法以及实现。本文的完整代码可以在我的github找到。

概念

红黑树是一种自平衡的二叉搜索树，其满足以下性质：

  1. 每个结点或是红色或是黑色的
  2. 根结点是黑色的
  3. 每个叶结点(NIL)是黑色的
  4. 如果一个叶结点是红色的，则它的两个子结点都为黑色的
  5. 对每个结点，从该结点到其后代的所有结点的简单路径上，均包含相同数目的黑色结点

为方便起见，我们使用一个哨兵结点来代表NIL， 哨兵结点颜色属性为黑色，其他属性为任意，所有指向NIL的指针均指向该哨兵结点。红黑树具有以下性质：

一棵具有n个内部结点的红黑树的高度至多为$2log(n+1)$

红黑树的方法

红黑树具有旋转、插入、删除、最值，中序遍历等方法，其python代码示例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Node:
    def __init__(self, key, color):
        self.parent = None
        self.key = key
        self.color = color
        self.left = None
        self.right = None


class RBTree:
    def __init__(self):
        self.nil = Node(-1, 'black')
        self.root = self.nil

self.nil即为哨兵结点，其颜色为黑色，key值为-1。根结点也初始化为哨兵结点。当根结点不为哨兵结点，其父亲指向哨兵结点。

旋转

旋转操作是一种能保持二叉搜索树性质的局部操作。注意，并不一定能保持红黑树性质。选中包括左旋和右旋，左旋操作假设当前结点的右孩子不为nil，右旋操作假设当前结点的左孩子不为nil。

假设当前结点为x，x的右孩子y不为nil。左旋操作沿着x->y的边进行旋转，使y变为x的父结点，由于二叉搜索树的性质，将y的左孩子给x，作为x的右孩子，y的左孩子变为x，x的父结点变为y的父结点。

假设当前结点为y，y的左孩子x不为nil。右旋操作沿着y->x的边进行旋转，使得x变成y的父结点，x的右孩子给y，使其成为y的左孩子。x的右孩子变为y，x的父结点变为y的父结点。

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
def left_rotate(self, x):
    # 假设x的右孩子不为nil
    y = x.right
    x.right = y.left
    if y.left != self.nil:
        y.left.parent = x

    y.parent = x.parent
    if x.parent == self.nil:
        self.root = y
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y

    y.left = x
    x.parent = y

def right_rotate(self, x):
    # 假设x的左孩子不为nil
    y = x.left
    x.left = y.right
    if y.right != self.nil:
        y.right.parent = x

    y.parent = x.parent
    if x.parent == self.nil:
        self.root = y
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y

    y.right = x
    x.parent = y

插入

红黑树的插入操作与二叉搜索树类似，先查找到要插入的叶结点，然后将其插入，并将其颜色设置为红色。与二叉搜索树不同的是，插入操作可能会导致红黑树的性质无法保持。由于将新插入的结点设置为红色结点，将可能会破坏红黑树的性质2和性质4。即，如果原来红黑树为空，新插入的结点则为根结点，由于根结点为红色，破坏性质2。如果插入的结点的父结点的颜色为红，则违反性质4。插入的基本思路如下：

  1. 如同二叉搜索树的插入过程，我们先找到其应该插入的位置，将其颜色设为红色。然后进入插入的修复过程insert_fix。
  2. 如果z.p的颜色为黑色时，退出循环并设置树的根的颜色为黑色。

  3. 如果z.p的颜色为红色，且z.p = z.p.p.left时，有以下三种情况：

    • y = z.p.p.right即为z的叔结点，当y为红色时，将z.p.p的颜色设置为红色，将z.p以及y的颜色设置黑色，令z=z.p.p，递归的进行这一过程。
    • 当y为黑色时，此时，如果z=z.p.right，令z=z.p，左旋使得z=z.p.left，则z和z.p为红色，且z=z.p.left，转换为情况3。
    • 当y为黑色时，z=z.p.left, 将z.p的颜色置为黑色，z.p.p置为红色，然后对z.p.p进行右旋。

  4. 如果z.p的颜色为红色，且z.p=z.p.right时，与情况3类似。只不过，左右的方向换了下。

    insert_fix过程主要修复红黑树可能被破坏的性质2和性质4。其在运行过程中满足以下不变式：

    1. 若z.p为根结点，z.p为黑色结点。
    2. 结点z为红色结点。
    3. 每次迭代，只有一条红黑树性质被破坏，要么为性质2，要么为性质4。

    如果当前结点z为红黑树的根结点，且z为红色，则必是将新增结点z插入到空的红黑树中，此时z.p的颜色为哨兵的颜色黑色，将不会进入循环，直接将树的根结点的颜色设置为黑色。这也是设置根结点父亲为哨兵的原因。如果z不为根结点，且违反性质4，insert_fix的局部操作保证各个分支上的黑色结点数目不变。当叔结点为红色时，令z沿着树上升，直至其父结点为黑色，z最多上升到根结点的孩子。当叔结点不为红时，此时经过一系列的左旋和右旋操作，修复性质4。此时z.p的颜色为黑，将在本次迭代后退出循环。因此，其时间复杂度为O(logn)。

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
def insert(self, z):
    y = self.nil
    x = self.root
    while x != self.nil:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right

    if y == self.nil:
        self.root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

    z.parent = y
    z.left = self.nil
    z.right = self.nil
    z.color = 'red'
    self.insert_fix(z)

def insert_fix(self, z):
    while z.parent.color == 'red':
        if z.parent == z.parent.parent.left:
            y = z.parent.parent.right
            if y.color == 'red':
                y.color = 'black'
                z.parent.color = 'black'
                z.parent.parent.color = 'red'
                z = z.parent.parent
            else:
                if z == z.parent.right:
                    z = z.parent
                    self.left_rotate(z)

                z.parent.color = 'black'
                z.parent.parent.color = 'red'
                self.right_rotate(z.parent.parent)
        else:
            y = z.parent.parent.left
            if y.color == 'red':
                y.color = 'black'
                z.parent.color = 'black'
                z.parent.parent.color = 'red'
                z = z.parent.parent
            else:
                if z == z.parent.left:
                    z = z.parent
                    self.right_rotate(z)

                z.parent.color = 'black'
                z.parent.parent.color = 'red'
                self.left_rotate(z.parent.parent)

    self.root.color = 'black'

删除

删除结点z的基本思路如下：

  1. 如果z的左孩子为哨兵，用y_origin_color记录z之前的颜色，用x记录将要替换z的结点，即z的右孩子x，然后用z的右孩子替换z。
  2. 如果z的右孩子为哨兵，用y_origin_color记录z之前的颜色，用x记录将要替换z的结点，即z的左孩子x， 然后用z的左孩子替换z。
  3. 如果z的左右孩子均存在，则找到z的后继，赋值为y，y_origin_color记录y的颜色，因为y为z的后继，则y必定没有左孩子，用y的右孩子替换y，用y替换z。
  4. 如果y_origin_color为黑色，则进入delete_fix过程。如果x为根结点，或者x的颜色为红色，则直接退出循环，将x的颜色设为黑色。当x不满足以上条件时，共有以下四种情况：
    • x的兄弟结点w为红色，则w的孩子必然为黑色。交换w和x.p的颜色，并对x.p进行右旋，令w为x.p旋转后新的兄弟结点， 则w必为黑色，进入情况2，3或4。
    • x的兄弟结点w为黑色，且其左右孩子均为黑色，则减去x的一层黑色，为保持性质5，w也减去一层黑色，变为红色。设置x为x.p，如果新的x为红色，则退出循环，并设置x为黑色。如果新的x为黑色，则x为双重黑色，在此进入循环。由情况1进入情况2，新的x必为红色。
    • x的兄弟结点w为黑色，且其左孩子为红色，右孩子为黑色，则交换w.left和w的颜色，进行右旋，此时w.left即为x新的兄弟结点，且满足其右孩子为红色，进入情况4。
    • x的兄弟结点w为黑色，且w的右孩子为红色，则将w的颜色与x.p进行交换，对x.p进行左旋，此时w变成x.p的父结点，将w的右孩子设置成黑色，则平衡树平衡。将x设置为树的根，然后退出循环。

红黑树的删除过程的相关注解：

  1. delete过程中，y始终指向要删除的结点，x始终指向要替换y的结点。当替换完成后，x占据y的位置。当z只有一个孩子时，显而易见。当左右孩子都存在时，只需找到找到z的后继y，删除y，然后用y替换z。即将删除y变成了删除z。此时z只有一个孩子，即右孩子。
  2. delete_fix过程中，循环过程中保持不变式，即x为双重黑色。所谓双重黑色，即为x的颜色为黑色，x取代的结点的颜色为黑色。将x设置成双重黑色，则能保持红黑树的性质5。
  3. 情况1、情况3和情况4只需进入一次循环，只有情况2才会多次进入循环，将x的双重黑色向上传递。情况1处理结束后，立刻进入情况2，情况2处理结束后，必定不满足循环条件而退出循环。情况3处理结束后立刻进入情况4，情况4处理结束后，即可退出循环。
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
def transplant(self, u, v):
    if u.parent == self.nil:
        self.root = v
    elif u == u.parent.left:
        u.parent.left = v
    else:
        u.parent.right = v

    v.parent = u.parent

def minimum(self, node):
    while node.left != self.nil:
        node = node.left

    return node

def delete(self, z):
    y = z
    y_origin_color = y.color
    if z.left == self.nil:
        x = z.right
        self.transplant(z, z.right)
    elif z.right == self.nil:
        x = z.left
        self.transplant(z, z.left)
    else:
        y = self.minimum(z.right)
        y_origin_color = y.color
        x = y.right
        if y.parent == z:
            x.parent = y
        else:
            self.transplant(y, y.right)
            y.right = z.right
            y.right.parent = y

        self.transplant(z, y)
        y.left = z.left
        y.left.parent = y
        y.color = z.color

    print(x.key, x.color, x.parent.key)
    if y_origin_color == 'black':
        self.delete_fix(x)

def delete_fix(self, x):
    while x != self.root and x.color == 'black':
        if x == x.parent.left:
            w = x.parent.right
            if w.color == 'red':
                w.color = 'black'
                x.parent.color = 'red'
                self.left_rotate(x.parent)
                w = x.parent.right
            if w.left.color == 'black' and w.right.color == 'black':
                w.color = 'red'
                x = x.parent
            else:
                if w.right.color == 'black':
                    w.color = 'red'
                    w.left.color = 'black'
                    self.right_rotate(w)
                    w = x.parent.right

                w.color = x.parent.color
                x.parent.color = 'black'
                w.right.color = 'black'
                self.left_rotate(x.parent)
                x = self.root
        else:
            w = x.parent.left
            if w.color == 'red':
                w.color = 'black'
                x.parent.color = 'red'
                self.right_rotate(x.parent)
                w = x.parent.left
            if w.right.color == 'black' and w.left.color == 'black':
                w.color = 'red'
                x = x.parent
            else:
                if w.left.color == 'black':
                    w.color = 'red'
                    w.right.color = 'black'
                    self.left_rotate(w)
                    w = x.parent.left

                w.color = x.parent.color
                x.parent.color = 'black'
                w.right.color = 'black'
                self.right_rotate(x.parent)
                x = self.root

    x.color = 'black'

中序遍历

中序遍历类似二叉搜索树，时间复杂度O(logn)。

1
2
3
4
5
def midsort(self, x):
    if x != self.nil:
        self.midsort(x.left)
        print(x.key, x.color, x.parent.key)
        self.midsort(x.right)

查找

查找类似二叉搜索树，时间复杂度O(logn)。

1
2
3
4
5
6
7
8
9
10
11
def search(self, k):
    cur = self.root
    while cur != self.nil:
        if k < cur.key:
            cur = cur.left
        elif k > cur.key:
            cur = cur.right
        else:
            return cur

    return None

Reference

本文主要参考《算法导论》。