数据结构与算法——红黑树_两个节点可以构成红黑树吗

红黑树

我们前面介绍了2-3树，可以看到2-3树能保证在插入元素之后，树依然保持平衡状态，它的最坏情况下所有子结点 都是2-结点，树的高度为lgN,相比于我们普通的二叉查找树，最坏情况下树的高度为N，确实保证了最坏情况下的 时间复杂度，但是2-3树实现起来过于复杂，所以我们介绍一种2-3树思想的简单实现：红黑树。

红黑树主要是对2-3树进行编码，红黑树背后的基本思想是用标准的二叉查找树(完全由2-结点构成)和一些额外的信 息(替换3-结点)来表示2-3树。我们将树中的链接分为两种类型：

**红链接：**将两个2-结点连接起来构成一个3-结点； **黑链接：**则是2-3树中的普通链接。

确切的说，我们将3-结点表示为由由一条左斜的红色链接(两个2-结点其中之一是另一个的左子结点)相连的两个2- 结点。这种表示法的一个优点是，我们无需修改就可以直接使用标准的二叉查找树的get方法。

1 红黑树的定义

从链接的角度来看，红黑树有以下三个特性

1. 红链接均为左链接；
2. 没有任何一个结点同时和两条红链接相连； （左倾红黑树）《算法4》
3. 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同；

从结点的角度来看，红黑树有以下五个特性：

1. 节点是红色或黑色。

2. 根节点是黑色。

3. 所有叶子都是黑色。

4. 每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）

5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

2 结点API设计

因为每个结点都只会有一条指向自己的链接（从它的父结点指向它），我们可以在之前的Node结点中添加一个布 尔类型的变量color来表示链接的颜色。如果指向它的链接是红色的，那么该变量的值为true，如果链接是黑色 的，那么该变量的值为false。

3 平衡化

在对红黑树进行一些增删改查的操作后，很有可能会出现红色的右链接或者两条连续红色的链接，而这些都不满足 红黑树的定义，所以我们需要对这些情况通过旋转进行修复，让红黑树保持平衡。

3.1 左旋

当某个结点的左子结点为黑色，右子结点为红色，此时需要左旋。

**前提：**当前结点为h，它的右子结点为x；

左旋过程：

1. 让x的左子结点变为h的右子结点
2. 让h成为x的左子结点
3. 让h的color属性变为x的color属性值
4. 让h的color属性变为RED

3.2 右旋

当某个结点的左子结点是红色，且左子结点的左子结点也是红色，需要右旋

**前提：**当前结点为h，它的左子结点为x；

右旋过程：

1. 让x的右子结点成为h的左子结点：
2. 让h成为x的右子结点：
3. 让x的color变为h的color属性值
4. 让h的color为RED；

3.3 向单个2-结点插入新键

一棵只含有一个键的红黑树只含有一个2-结点。插入另一个键后，我们马上就需要将他们旋转。

• 如果新键小于当前结点的键，我们只需要新增一个红色结点即可，新的红黑树和单个3-结点完全等价。

• 如果新键大于当前结点的键，那么新增的红色结点将会产生一条红色的右链接，此时我们需要通过左旋，把 红色右链接变成左链接，插入操作才算完成。形成的新的红黑树依然和3-结点等价，其中含有两个键，一条红 色链接。

3.4 向底部的2-结点插入新键

用和二叉查找树相同的方式向一棵红黑树中插入一个新键，会在树的底部新增一个结点（可以保证有序性），唯一 区别的地方是我们会用红链接将新结点和它的父结点相连。如果它的父结点是一个2-结点，那么刚才讨论的两种方 式仍然适用。

3.5 变色

当一个结点的左子结点和右子结点的color都为RED时，也就是出现了临时的4-结点，此时只需要把左子结点和右子结点的颜色变为BLACK，同时让当前结点的颜色变为RED即可。

3.6 向一棵双键树（即一个3-结点）中插入新键

这种情况有可以分为三种子情况：

1. 新键大于原树中的两个键

2. 新键小于原树中的两个键

3. 新键介于原树中两个键之间

3.7 根节点的颜色总是黑色

之前我们介绍结点API的时候，在结点Node对象中color属性表示的是父结点指向当前结点的连接的颜色，由于根 结点不存在父结点，所以每次插入操作后，我们都需要把根结点的颜色设置为黑色。

3.8 向树底部的3-结点插入新键

假设在树的底部的一个3-结点下加入一个新的结点。前面我们所讲的3种情况都会出现。指向新结点的链接可能是 3-结点的右链接（此时我们只需要转换颜色即可），或是左链接(此时我们需要进行右旋转然后再转换)，或是中链 接(此时需要先左旋转然后再右旋转，最后转换颜色)。颜色转换会使中间结点的颜色变红，相当于将它送入了父结 点。这意味着父结点中继续插入一个新键，我们只需要使用相同的方法解决即可，直到遇到一个2-结点或者根结点 为止。

3.9 代码实现

API 设计

代码实现

public class RedBlackTree<Key extends Comparable<Key>, Value> {

    private Node<Key, Value> root;
    private int n;
    /**
     * 红色标识
     */
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    public RedBlackTree() {
        n = 0;
    }

    /**
     * 判断当前节点的父指向链接是否为红色
     *
     * @return
     */
    private boolean isRed(Node<Key, Value> node) {
        if (node == null) {
            return false;
        }
        // 非空节点
        return node.color == RED;
    }

    /**
     * 左旋调整
     *
     * @param h
     * @return
     */
    private Node<Key, Value> rotateLeft(Node<Key, Value> h) {
        // 找出h的右节点
        Node<Key, Value> hRight = h.right;
        // 找出右节点的左子节点
        Node<Key, Value> lhRight = hRight.left;
        // 让当前节点h的右子节点的左子节点成为当前结点的右子节点
        h.right = lhRight;
        // 让当前结点h成为右子节点的左子节点
        hRight.left = h;
        // 让当前节点h的color变成右子节点的color
        hRight.color = h.color;
        // 让当前节点h的color变为red
        h.color = RED;
        return hRight;
    }

    /**
     * 右旋调整
     *
     * @param h
     * @return
     */
    private Node<Key, Value> rotateRight(Node<Key, Value> h) {
        // 获取当前节点h的左子节点
        Node<Key, Value> hLeft = h.left;
        // 找出当前节点h的左子节点的右子节点
        Node<Key, Value> rhLeft = hLeft.right;
        // 让当前节点h的左子节点的右子节点成为当前节点的左子节点
        h.left = rhLeft;
        // 让当前节点成为左子节点的右子节点
        hLeft.right = h;
        // 让当前节点h的color值变为左子节点的color值
        hLeft.color = h.color;
        // 让当前节点h的color变为RED
        h.color = RED;
        return hLeft;
    }

    /**
     * 颜色反转，相当于完成拆分4-节点
     *
     * @param h
     */
    private void flipColors(Node<Key, Value> h) {
        // 当前节点的color变为RED
        h.color = RED;
        h.left.color = BLACK;
        h.right.color = BLACK;
    }

    /**
     * 获取树中元素的个数
     *
     * @return
     */
    public int size() {
        return n;
    }

    public Value get(Key key) {
        return get(root, key);
    }

    /**
     * 从指定的树x中找到key对应的值
     *
     * @param x
     * @param key
     * @return
     */
    private Value get(Node<Key, Value> x, Key key) {
        if (x == null) {
            return null;
        }
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            return get(x.left, key);
        } else if (cmp > 0) {
            return get(x.right, key);
        } else {
            return x.value;
        }
    }

    /**
     * 在整个树上完成插入操作
     *
     * @param key
     * @param value
     */
    public void put(Key key, Value value) {
        root = put(root, key, value);
        root.color = BLACK;
    }

    /**
     * 在指定的树中，完成插入操作，并返回添加元素后的新树
     *
     * @param h
     * @param key
     * @param value
     * @return
     */
    private Node<Key, Value> put(Node<Key, Value> h, Key key, Value value) {
        if (h == null) {
            // 标准的插入操作，和父节点用红链接相连
            n++;
            return new Node<>(null, null, key, value, RED);
        }
        // 比较要插入的键和当前节点的键
        int cmp = key.compareTo(h.key);
        // 当前插入的key小于当前节点的key
        if (cmp < 0) {
            // 继续寻找左子树插入
            h.left = put(h.left, key, value);
        } else if (cmp > 0) {
            // 当前插入的key大于当前节点的key
            // 继续寻找节点的右子树插入
            h.right = put(h.right, key, value);
        } else {
            // key相等，直接替换
            h.value = value;
        }
        // 如果当前节点的右连接是红色，左链接是黑色，需要左旋
        if (isRed(h.right) && !isRed(h.left)) {
            h = rotateLeft(h);
        }
        // 如果当前结点的左子节点和左子节点的左子节点都是红色，就需要右旋
        if (isRed(h.left) && isRed(h.left.left)) {
            h = rotateRight(h);
        }
        // 如果当前结点的左链接和右连接都是红色，则需要变色
        if (isRed(h.left) && isRed(h.right)) {
            flipColors(h);
        }
        // 返回当前节点
        return h;
    }

    private static class Node<Key, Value> {
        public Node<Key, Value> left;
        public Node<Key, Value> right;
        public Key key;
        public Value value;
        /**
         * 如果指向它的链接是红色的，那么该变量的值为true，
         * 如果链接是黑色 的，那么该变量的值为false
         */
        public boolean color;

        public Node(Node<Key, Value> left, Node<Key, Value> right, Key key, Value value, boolean color) {
            this.left = left;
            this.right = right;
            this.key = key;
            this.value = value;
            this.color = color;
        }
    }

}

class Test15 {
    public static void main(String[] args) {
        RedBlackTree<Integer, String> tree = new RedBlackTree<>();
        tree.put(4, "二哈");
        tree.put(1, "张三");
        tree.put(3, "李四");
        tree.put(5, "王五");
        System.out.println(tree.size());
    }

}
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205