曹耘豪的博客

数据结构之红黑树

  1. 特点
  2. 旋转
    1. 左旋
    2. 右旋
  3. 插入节点
    1. 1. 根节点为null
    2. 2. 父节点是黑色
    3. 3. 父节点是红色，叔叔节点为红色
    4. 4. 父节点是红色，叔叔节点为黑色，直线型
    5. 5. 父节点是红色，叔叔节点为黑色，三角型
  4. 代码实现
  5. 删除节点
  6. 参考

近似平衡的二叉搜索树

特点

旋转

左旋

假设对A进行左旋，左旋前后如下：

1
2
3
4
5
6
7
8
9
10
11
  A
 / \
B   C
   / \
  D   E

    C
   / \
  A   E
 / \
B   D

右旋

假设对A进行右旋，右旋前后如下：

1
2
3
4
5
6
7
8
9
10
11
    A
   / \
  B   C
 / \
D   E

  B
 / \
D   A
   / \
  E   C

插入节点

新插入的节点都是红色，就有5种情况，其中后3种需要进一步的调整：

  1. 根节点为null
  2. 父节点是黑色
  3. 父节点是红色，叔叔节点为红色
  4. 父节点是红色，叔叔节点为黑色，直线型
  5. 父节点是红色，叔叔节点为黑色，三角型

1. 根节点为null

最简单的情况，直接赋值即可

2. 父节点是黑色

添加的节点是红色，此时依然满足红黑树的条件，直接添加即可

3. 父节点是红色，叔叔节点为红色

4. 父节点是红色，叔叔节点为黑色，直线型

如下所示为直线型，新加入的节点为4，是左子节点，而其父节点也是左子节点

1
2
3
4
5
     1(黑)
   /   \
  2(红)  3(黑)
 /
4(红)
1
2
3
4
5
   2(黑)
 /   \
4(红) 1(红)
       \
        3(黑)

5. 父节点是红色，叔叔节点为黑色，三角型

如下所示为三角型，新加入的节点为4，是右子节点，而其父节点是左子节点

1
2
3
4
5
   1(黑)
 /   \
2(红) 3(黑)
  \
   4(红)
1
2
3
4
5
     1(黑)
   /   \
  4(红)  3(黑)
 /
2(红)

代码实现

参考TreeMap实现

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
public void insert(int value) {
    if (root == null) {
        root = new Node(value);  // 情况1
    } else {
        Node node = root, parent;
        boolean left;
        do {
            parent = node;
            left = value < node.value;
            if (left) {
                node = node.left;
            } else {
                node = node.right;
            }
        } while (node != null);

        Node newNode = new Node(value, parent);
        if (left) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }

        fixAfterInsertion(newNode);
    }
}

public void fixAfterInsertion(Node node) {
    node.color = RED;
    // 情况2，node.parent.color == BLACK，直接跳出循环
    while (node != null && node != root && node.parent.color == RED) {
        Node parent = parentOf(node);
        Node grandparent = parentOf(parent);
        if (parent == leftOf(grandparent)) {
            Node uncle = rightOf(grandparent);
            if (colorOf(uncle) == RED) {         // 情况3
                setColor(parentOf(node), BLACK); // 情况3
                setColor(uncle, BLACK);          // 情况3
                setColor(grandparent, RED);      // 情况3
                node = grandparent;              // 情况3
            } else {
                if (node == rightOf(parent)) {   // 情况5
                    node = parent;               // 情况5
                    rotateLeft(node);            // 情况5
                }
                setColor(parentOf(node), BLACK); // 情况4
                setColor(grandparent, RED);      // 情况4
                rotateRight(grandparent);        // 情况4
            }
        } else {
            Node uncle = leftOf(grandparent);
            if (colorOf(uncle) == RED) {
                setColor(parent, BLACK);
                setColor(uncle, BLACK);
                setColor(grandparent, RED);
                node = grandparent;
            } else {
                if (node == leftOf(parent)) {
                    node = parent;
                    rotateRight(node);
                }
                setColor(parentOf(node), BLACK);
                setColor(grandparent, RED);
                rotateLeft(grandparent);
            }
        }
    }
    root.color = BLACK; // 根节点总是黑色
}

private static boolean colorOf(Node n) {
    return n == null ? BLACK : n.color; // 空节点为黑节点
}

删除节点

待续

参考

  算法