目录

红黑树

红黑树的引入

二叉搜索树极端情况下可能退化成链表,时间复杂度提高到O(n)。平衡二叉树保证了在最差情况下,任何节点的平衡因此不超过1,但是由于平衡二叉树的定义过于严格,导致每次插入或删除一个元素之后都要去维护二叉树整体的平衡,这样产生的额外代价又太大了。怎么可以在保证平衡的情况下尽量减少平衡的开销呢,这就引出了下面要讲的红黑树。

红黑树的分类

  1. 红黑树(普通红黑树):允许一个节点有两个红色子节点, 对应2-3-4树
  2. 左倾红黑树:一个节点只能有一个红色子节点,并且是左节点,对应2-3树

红黑树的性质

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须除了满足二叉搜索树的性质外,还要满足下面的性质:

  1. 节点要么是红色要么是黑色
  2. 根节点是黑色
  3. 叶子节点(nil,这儿指的值二叉搜索树中叶子节点的左右空指针)都得是黑色的。
  4. 红色节点的两个子节点都是黑色
  5. 任一节点到每个叶子节点的路径上黑色节点的数目是相同的。 https://gitee.com/lienhui68/picStore/raw/master/null/20200629231750.png

我们来分析一下上面5个性质

  1. 性质4表明:红色节点的父、左子、右子只能是黑色节点,红色和红色不能连在一起;而黑色无论红黑都可以连在一起。(红色暴脾气互不相容,黑色和蔼可亲)
  2. 性质5表明:随便选一个节点,不论从哪条路径走到叶子节点时,路径上的黑色节点数目相同(完全黑平衡)。
  3. 性质4和性质5共同决定了:最长路径的节点总数不超过最短路径节点总数的2倍。因为黑色节点数量要一样,红色节点不能相连,从而路径上节点全黑时最短,路径上红黑交替时最长。最短(3):黑+黑+黑,最长(5):黑+红+黑+红+黑。正因为路径长度有了一定限制,所以称红黑树是有一定平衡性的,不会出现极端倾斜的情况。
  4. 性质4对于定义红黑树没有什么实际意义,添加null结点表示数据结束,保证了所有结点都有两个子结点,这样做的好处是使得红黑树在算法的实现上更简单些。

红黑树的应用

  1. 散列表的冲突处理 map的实现,底层一般会采用红黑树,在节点多的时候效率高。 在节点少的时候,可用链表方式。
  2. 动态插入、删除和查询较多的场景

新增节点

开始之前,先约定一下名称: https://gitee.com/lienhui68/picStore/raw/master/null/20200629232300.png 红黑树属于二叉搜索树,插入动作也与二叉搜索树一致,只不过红黑树在插入之后,多了平衡动作(旋转与涂色)。 新插入的节点均为红色节点,因为红色不会影响路径上黑色节点的数量,保持性质5。如果父节点为黑色,就直接结束了;如果父节点为红色,则需要另外处理了。

插入步骤

  1. N为根节点, 将N涂黑

  2. 父黑, 无需其他操作

  3. 父红 3.1. 叔红, P和U涂黑,GP涂红,以GP为N进行递归处理,如下图插入21 https://gitee.com/lienhui68/picStore/raw/master/null/20200629233447.png 3.2. 叔黑, 如下图插入7, https://gitee.com/lienhui68/picStore/raw/master/null/20200629233400.png 将以GP(节点1)为根的子树看成是RR型,然后进行RR型的调整(就是AVL树中的RR型),最后将新的根节点涂成黑色,将其两个孩子中不是红色的节点改成红色。如下图,此时整颗树就已经是红黑树了。 https://gitee.com/lienhui68/picStore/raw/master/null/20200630002750.png 同理还有LL型、LR型和RL型

    当情况为3.1时,递归处理的结束条件是N的父节点是黑色或者N的叔叔节点为黑色,否则要一直迭代到根节点,如果最终迭代到根节点需要将根节点置成红色。

插入部分代码

  1. 情况3.1处理
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
     * 插入时遇到父红叔红的情况处理
     *
     * @param node 新插入节点或者迭代的新起点
     * @return
     */
    private Node insert_case_1(Node node) {
        Node p = getFather(node.value);
        if (p == null) {
            return null;
        }
        // 祖父节点
        Node gp = getFather(p.value);
        if (gp == null) {
            return null;
        }
        // 叔叔节点
        Node u = (p == gp.left) ? gp.right : gp.left;
        // P和U涂黑,GP涂红
        p.color = NODE_COLOR.BLACK;
        u.color = NODE_COLOR.BLACK;
        gp.color = NODE_COLOR.RED;
        return gp;
    }
  1. 情况3.2处理
 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
 /**
     * 插入时遇到父红叔黑的情况处理
     *
     * @param node 新插入节点或者迭代的新起点
     * @return
     */
    private void insert_case_2(Node node) {
        Node p = getFather(node.value);
        if (p == null) {
            throw new RuntimeException();
        }
        Node gp = getFather(p.value);
        if (gp == null) {
            throw new RuntimeException();
        }
        // 获取以GP为根的子树类型
        TREE_TYPE treeType = getTreeType(gp, node.value);
        Node gpp = getFather(gp.value);
        Node big = null, middle = null, small = null;
        switch (treeType) {
            // 1. LL型最小非平衡子树
            case LL:
                // 1.1 确定big、middle和small
                big = gp;
                middle = gp.left;
                // 1.2 将middle的左右子树分配给big和small
                // 对于LL型,middle的左子不用分配,调整前后middle的左子都是small,对于middle的右子要分配给big的左子,这样才能保证二叉排序
                big.left = middle.right;
                // 1.3 将small和big分别作为middle的左右子节点
                middle.right = big;
                break;
            case LR:
                // 2.1 确定big、middle和small
                big = gp;
                middle = gp.left.right;
                small = gp.left;
                // 2.2 将middle的左右子树分配给big和small
                // 分配原则是将middle的左子分配给small的右子,将middle的右子分配给big的左子
                big.left = middle.right;
                small.right = middle.left;
                // 2.3 将small和big分别作为middle的左右子树
                middle.left = small;
                middle.right = big;
                break;
            case RL:
                // 3.1 确定big、middle和small
                big = gp.right;
                middle = gp.right.left;
                small = gp;
                // 3.2 将middle的左右子树分配给big和small
                // 分配原则是将middle的左子分配给small的右子,将middle的右子分配给big的左子
                big.left = middle.right;
                small.right = middle.left;
                // 2.3 将small和big分别作为middle的左右子树
                middle.left = small;
                middle.right = big;
                break;
            case RR:
                // 3.1 确定big、middle和small
                big = gp.right.right;
                middle = gp.right;
                small = gp;
                // 3.2 将middle的左右子树分配给big和small
                // 对于RR型middle的右子不用分配,调整前后middle的右子都是big。
                small.right = middle.left;
                // 2.3 将small和big分别作为middle的左右子树
                // 对于RR型middle的右子不用分配,调整前后middle的右子都是big。
                middle.left = small;
                break;

        }

        // 最后将新的根节点涂成黑色,将其两个孩子中不是红色的节点改成红色。
        middle.color = NODE_COLOR.BLACK;
        big.color = NODE_COLOR.RED;
        small.color = NODE_COLOR.RED;

        // 将middle作为调整后的最小非平衡子树根节点,也就是将middle作为parent的孩子,这里要分3种情况
        // parent为null表示根节点也被调整,此时应将root指向middle
        if (gpp == null) {
            root = middle;
            return;
        } else if (gpp.left != null && gpp.left.value == gp.value) {
            gpp.left = middle;
        } else if (gpp.right != null && gpp.right.value == gp.value) {
            gpp.right = middle;
        } else {
            throw new RuntimeException();
        }
    }
  1. 添加节点代码
 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
/**
     * 添加节点
     *
     * @param value
     */
    public void add(int value) {
        // 和二叉排序树一样, 区别是最后需要处理平衡性问题平衡性
        Node node = new Node(value);
        if (root == null) {
            root = node;
            root.color = NODE_COLOR.BLACK;
            return;
        }
        Node cur = root;
        while (true) {
            // 如果值比当前节点小
            if (value < cur.value) {
                // 如果当前节点左节点为空,将左节点指向新节点
                if (cur.left == null) {
                    cur.left = node;
                    break;
                } else { // 继续跟当前节点的左节点比较
                    cur = cur.left;
                }
            }
            if (value > cur.value) {
                if (cur.right == null) {
                    cur.right = node;
                    break;
                } else {
                    cur = cur.right;
                }
            }
            if (value == cur.value) {
                // 如果和已有节点值相同,直接报冲突,不处理这种情况
                throw new RuntimeException("已有相同的值,请勿重复插入!");
            }
        }
        // 如果父节点是黑色则无需处理,如果是红色那么需要调整
        if (cur.color == NODE_COLOR.RED) {
            while (node != root) {
                Node p = getFather(node);
                if (p == null) {
                    throw new RuntimeException();
                }
                if (p.color == NODE_COLOR.BLACK) {
                    return;
                }
                // 获取祖父节点
                Node gp = getFather(p);
                if (gp == null) {
                    return;
                }
                // 获取叔叔节点
                Node u = gp.left == cur ? gp.right : gp.left;
                if (u == null || u.color == NODE_COLOR.BLACK) { // 叔黑
                    insert_case_2(node);
                    return;
                } else { // 叔红
                    node = insert_case_1(node);
                }
            }
            if (node == root) {
                root.color = NODE_COLOR.BLACK;
            }
        }
    }

删除节点

todo

完整代码

  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
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
package com.eh.ftd.dsa.ds;


/**
 * todo
 *
 * @author David Li
 * @create 2020/06/30 00:37
 */
public class RedBlackTree {
    private Node root; // 根节点

    private class Node {
        int value; // 值
        Node left; // 左子节点
        Node right; // 右子节点
        NODE_COLOR color; // 节点颜色

        public Node(int value) {
            color = NODE_COLOR.RED;
            this.value = value;
        }

        public Node(int value, NODE_COLOR color) {
            this.value = value;
            this.color = color;
        }

        @Override
        public String toString() {
            return "Node{" +value +
                    ", " + color +
                    '}';
        }
    }

    private enum NODE_COLOR {
        RED, BLACK
    }

    /**
     * 子树类型
     */
    private enum TREE_TYPE {
        LL, LR, RL, RR
    }

    /**
     * 获得节点的父节点
     *
     * @param node
     * @return
     */
    private Node getFather(Node node) {
        if (node == null) {
            return null;
        }
        return getFather(node.value);
    }

    /**
     * 获得节点的父节点
     *
     * @param value
     * @return
     */
    private Node getFather(int value) {
        if (root == null) {
            return null;
        }
        Node cur = root, parent = null;
        while (cur != null) {
            if (value < cur.value) {
                parent = cur;
                cur = cur.left;
            } else if (value > cur.value) {
                parent = cur;
                cur = cur.right;
            } else {
                return parent;
            }
        }
        return null;
    }


    /**
     * 获取子树类型
     *
     * @param root  待调整子树的类型
     * @param value 新插入的节点或者新的起点的值(父红叔红情况下迭代的起点)
     * @return
     */
    private TREE_TYPE getTreeType(Node root, int value) {
        if (root == null) {
            throw new RuntimeException();
        }
        if (value > root.value) {
            // 说明是RX型
            if (value > root.right.value) {
                // 说明是RR型
                return TREE_TYPE.RR;
            } else {
                return TREE_TYPE.RL;
            }
        } else {
            // 说明是LX型
            if (value < root.left.value) {
                return TREE_TYPE.LL;
            } else {
                return TREE_TYPE.LR;
            }
        }
    }

    /**
     * 插入时遇到父红叔红的情况处理
     *
     * @param node 新插入节点或者迭代的新起点
     * @return
     */
    private Node insert_case_1(Node node) {
        Node p = getFather(node.value);
        if (p == null) {
            return null;
        }
        // 祖父节点
        Node gp = getFather(p.value);
        if (gp == null) {
            return null;
        }
        // 叔叔节点
        Node u = (p == gp.left) ? gp.right : gp.left;
        // P和U涂黑,GP涂红
        p.color = NODE_COLOR.BLACK;
        u.color = NODE_COLOR.BLACK;
        gp.color = NODE_COLOR.RED;
        return gp;
    }

    /**
     * 插入时遇到父红叔黑的情况处理
     *
     * @param node 新插入节点或者迭代的新起点
     * @return
     */
    private void insert_case_2(Node node) {
        Node p = getFather(node.value);
        if (p == null) {
            throw new RuntimeException();
        }
        Node gp = getFather(p.value);
        if (gp == null) {
            throw new RuntimeException();
        }
        // 获取以GP为根的子树类型
        TREE_TYPE treeType = getTreeType(gp, node.value);
        Node gpp = getFather(gp.value);
        Node big = null, middle = null, small = null;
        switch (treeType) {
            // 1. LL型最小非平衡子树
            case LL:
                // 1.1 确定big、middle和small
                big = gp;
                middle = gp.left;
                // 1.2 将middle的左右子树分配给big和small
                // 对于LL型,middle的左子不用分配,调整前后middle的左子都是small,对于middle的右子要分配给big的左子,这样才能保证二叉排序
                big.left = middle.right;
                // 1.3 将small和big分别作为middle的左右子节点
                middle.right = big;
                break;
            case LR:
                // 2.1 确定big、middle和small
                big = gp;
                middle = gp.left.right;
                small = gp.left;
                // 2.2 将middle的左右子树分配给big和small
                // 分配原则是将middle的左子分配给small的右子,将middle的右子分配给big的左子
                big.left = middle.right;
                small.right = middle.left;
                // 2.3 将small和big分别作为middle的左右子树
                middle.left = small;
                middle.right = big;
                break;
            case RL:
                // 3.1 确定big、middle和small
                big = gp.right;
                middle = gp.right.left;
                small = gp;
                // 3.2 将middle的左右子树分配给big和small
                // 分配原则是将middle的左子分配给small的右子,将middle的右子分配给big的左子
                big.left = middle.right;
                small.right = middle.left;
                // 2.3 将small和big分别作为middle的左右子树
                middle.left = small;
                middle.right = big;
                break;
            case RR:
                // 3.1 确定big、middle和small
                big = gp.right.right;
                middle = gp.right;
                small = gp;
                // 3.2 将middle的左右子树分配给big和small
                // 对于RR型middle的右子不用分配,调整前后middle的右子都是big。
                small.right = middle.left;
                // 2.3 将small和big分别作为middle的左右子树
                // 对于RR型middle的右子不用分配,调整前后middle的右子都是big。
                middle.left = small;
                break;

        }

        // 最后将新的根节点涂成黑色,将其两个孩子中不是红色的节点改成红色。
        middle.color = NODE_COLOR.BLACK;
        big.color = NODE_COLOR.RED;
        small.color = NODE_COLOR.RED;

        // 将middle作为调整后的最小非平衡子树根节点,也就是将middle作为parent的孩子,这里要分3种情况
        // parent为null表示根节点也被调整,此时应将root指向middle
        if (gpp == null) {
            root = middle;
            return;
        } else if (gpp.left != null && gpp.left.value == gp.value) {
            gpp.left = middle;
        } else if (gpp.right != null && gpp.right.value == gp.value) {
            gpp.right = middle;
        } else {
            throw new RuntimeException();
        }
    }

    /**
     * 添加节点
     *
     * @param value
     */
    public void add(int value) {
        // 和二叉排序树一样, 区别是最后需要处理平衡性问题平衡性
        Node node = new Node(value);
        if (root == null) {
            root = node;
            root.color = NODE_COLOR.BLACK;
            return;
        }
        Node cur = root;
        while (true) {
            // 如果值比当前节点小
            if (value < cur.value) {
                // 如果当前节点左节点为空,将左节点指向新节点
                if (cur.left == null) {
                    cur.left = node;
                    break;
                } else { // 继续跟当前节点的左节点比较
                    cur = cur.left;
                }
            }
            if (value > cur.value) {
                if (cur.right == null) {
                    cur.right = node;
                    break;
                } else {
                    cur = cur.right;
                }
            }
            if (value == cur.value) {
                // 如果和已有节点值相同,直接报冲突,不处理这种情况
                throw new RuntimeException("已有相同的值,请勿重复插入!");
            }
        }
        // 如果父节点是黑色则无需处理,如果是红色那么需要调整
        if (cur.color == NODE_COLOR.RED) {
            while (node != root) {
                Node p = getFather(node);
                if (p == null) {
                    throw new RuntimeException();
                }
                if (p.color == NODE_COLOR.BLACK) {
                    return;
                }
                // 获取祖父节点
                Node gp = getFather(p);
                if (gp == null) {
                    return;
                }
                // 获取叔叔节点
                Node u = gp.left == cur ? gp.right : gp.left;
                if (u == null || u.color == NODE_COLOR.BLACK) { // 叔黑
                    insert_case_2(node);
                    return;
                } else { // 叔红
                    node = insert_case_1(node);
                }
            }
            if (node == root) {
                root.color = NODE_COLOR.BLACK;
            }
        }
    }

    public void inOrderList(Node node) {
        if (node != null) {
            inOrderList(node.left);
            System.out.print(node + " ");
            inOrderList(node.right);
        }
    }

    public void preOrderList(Node node) {
        if (node != null) {
            System.out.println(node + "");
            preOrderList(node.left);
            preOrderList(node.right);
        }
    }

    public static void main(String[] args) {
        RedBlackTree redBlackTree = new RedBlackTree();
        for (int i = 0; i < 20; i++) {
            redBlackTree.add(i);
        }
        System.out.println("数列:");
        redBlackTree.preOrderList(redBlackTree.root);
        System.out.println();

    }
}

参考

红黑树之插入节点 红黑树之删除节点 彻底理解红黑树(三)之 删除