【数据结构进阶】红黑树【TreeMap TreeSet底层就是红黑树】_stl treemap

作者：繁依Fanyi0 | 2024-05-16 12:34:43

踩

stl treemap

红黑树【TreeMap TreeSet底层就是红黑树】

概念

红黑树是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可能是Red或者Black。通过对任何一条从根到叶子结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nDPYQQ9K-1671756615998)(C:\Users\17512\AppData\Roaming\Typora\typora-user-images\1671330013337.png)]$

红黑树的性质

最长路径最多是最短路径的2倍。
每个结点不是红色就是黑色。
根结点是黑色的。
如果一个结点是红色的，则它的两个孩子结点是黑色的。【没有2个连续的红色结点】不能有两个连续的红色结点
对于每个结点，从该结点到其后代叶结点的简单路径上，均包含相同数目的黑色结点。每条路径上，都有相同个数的黑色结点
每个叶子结点都是黑色的。【此处的叶子节点指的是空结点】

2，3，4，5，6 => 1

最短路径：就是当前路径全部都是黑色结点

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-W06eocR4-1671756615999)(C:\Users\17512\AppData\Roaming\Typora\typora-user-images\1671332563267.png)]$

假设一棵红黑树当中有 X 个黑色的结点。这棵树总共有N个结点。那么N的范围是多少？

【x 2x】最短路径的时间复杂度：
$l o g 2 n$
最短路径的长度：
$l o g n$
最长路径的长度：
$2 l o g n$

红黑树结点的定义

static class rbTreeNode{
        public rbTreeNode left ;
        public rbTreeNode right;
        public rbTreeNode parent;
        public int val;
        public COLOR color;

        public rbTreeNode(int val){
            this.val = val;
            //我们新创建的结点，颜色默认是红色的 为什么呢？见下面详解！
            this.color =COLOR.RED;
        }
    }
    public rbTreeNode root;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

新增的结点不能是黑色的，如果是黑色的，就需要保证每条路径上的黑色结点必须是相同的。势必会有以下问题：

你需要继续新增结点

红黑树的插入

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

按照二叉搜索的树规则插入新节点
检测新节点插入后，红黑树的性质是否造到破坏

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要

调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对

红黑树分情况来讨论：

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况一： cur为红，p为红，g为黑，u存在且为红
- 解决方法：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。 $[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nSNogo0G-1671756616000)(C:\Users\17512\AppData\Roaming\Typora\typora-user-images\1671754258083.png)]$
情况二：cur为红，p为红，g为黑，u不存在/u为黑
- 解决方法：p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转
情况三：cur为红，p为红，g为黑，u不存在/u为黑
- 解决方法：p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转

public boolean insert(int val) {
        rbTreeNode node = new rbTreeNode(val);
        if (root == null) {
            root = node;
            return true;
        }
        rbTreeNode parent = null;
        rbTreeNode cur = root;
        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val == val) {
                return false;
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
        //cur == null
        if (parent.val < val) {
            parent.right = node;
        } else {
            parent.left = node;
        }

        node.parent = parent;
        cur = node;
        //红黑树来说：需要调整颜色
        while (parent!=null && parent.color ==COLOR.RED){
            rbTreeNode grandFather = parent.parent; //这个引用不可能为空
            //cur为红，p为红，g为黑，u存在且为红
            if (parent ==  grandFather.left){
                rbTreeNode  uncle = grandFather.right;
                if (uncle!=null && uncle.color == COLOR.RED){
                    //将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。
                    parent.color= COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandFather.color =COLOR.RED;
                }else{//uncle不存在 || uncle是黑色
                    //cur为红，p为红，g为黑，u不存在/u为黑
                    //情况三：
                    if(cur == parent.right) {
                        rotateLeft(parent);
                        rbTreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;
                    }//情况三  变成了情况二

                    //情况二
                    rotateRight(grandFather);
                    grandFather.color = COLOR.RED;
                    parent.color = COLOR.BLACK;
                }
            }else {
                //parent == grandFather.right
                rbTreeNode uncle = grandFather.left;
                if(uncle != null && uncle.color == COLOR.RED) {
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandFather.color = COLOR.RED;
                    //继续向上修改
                    cur = grandFather;
                    parent = cur.parent;
                }else {
                    //uncle不存在 或者 uncle是黑色的
                    //情况三：
                    if(cur == parent.left) {
                        rotateRight(parent);
                        rbTreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;
                    }//情况三  变成了情况二
                    //情况二
                    rotateLeft(grandFather);
                    grandFather.color = COLOR.RED;
                    parent.color = COLOR.BLACK;
                }

            }
        }
        root.color = COLOR.BLACK;
        return true;
    }
    /**
     * 左单旋
     * @param parent
     */
    private void rotateLeft(rbTreeNode parent) {
        rbTreeNode subR = parent.right;
        rbTreeNode subRL = subR.left;

        parent.right = subRL;

        subR.left = parent;
        if(subRL != null) {
            subRL.parent = parent;
        }

        rbTreeNode pParent = parent.parent;
        parent.parent = subR;

        if(root == parent) {
            root = subR;
            root.parent = null;
        }else {
            if(pParent.left == parent) {
                pParent.left = subR;
            }else {
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
    }

    /**
     * 右单旋
     * @param parent
     */
    private void rotateRight(rbTreeNode parent) {

        rbTreeNode subL = parent.left;
        rbTreeNode subLR = subL.right;

        parent.left = subLR;
        subL.right = parent;
        //没有subLR
        if(subLR != null) {
            subLR.parent = parent;
        }
        //必须先记录
        rbTreeNode pParent = parent.parent;
        parent.parent = subL;
        //检查 当前是不是就是根节点
        if(parent == root) {
            root = subL;
            root.parent = null;
        }else {
            //不是根节点，判断这棵子树是左子树还是右子树
            if(pParent.left == parent) {
                pParent.left = subL;
            }else {
                pParent.right = subL;
            }
            subL.parent = pParent;
        }
    }
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

红黑树的验证

public void inorder(rbTreeNode root) {
        if(root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }
1
2
3
4
5
6
7
8

/**
     * 判断当前树 是不是红黑树
     *  得满足 红黑树的性质
     * @return
     */
    public boolean isRBTree() {
        if(root == null) {
            //如果一棵树是空树，那么这棵树就是红黑树
            return true;
        }

        if(root.color != COLOR.BLACK) {
            System.out.println("违反了性质：根节点必须是黑色的！");
        }

        //存储当前红黑树当中 最左边路径的黑色的节点个数
        int blackNum = 0;
        rbTreeNode cur = root;
        while (cur != null) {
            if(cur.color == COLOR.BLACK) {
                blackNum++;
            }
            cur = cur.left;
        }
        //检查是否存在两个连续的红色节点  && 每条路径上黑色的节点的个数是一致的
        return checkRedColor(root) && checkBlackNum(root,0,blackNum);
    }

    /**
     *
     * @param root
     * @param pathBlackNum 每次递归的时候，计算黑色节点的个数  0
     * @param blackNum 事先计算好的某条路径上的黑色节点的个数   2
     * @return
     */
    private boolean checkBlackNum(rbTreeNode root,int pathBlackNum,int blackNum) {
        if(root == null) {
            return true;
        }
        if(root.color == COLOR.BLACK) {
            pathBlackNum++;
        }
        if(root.left == null && root.right == null) {
            if(pathBlackNum != blackNum) {
                System.out.println("违反了性质：每条路径上黑色的节点个数是不一样的！");
                return false;
            }
        }
        return checkBlackNum(root.left,pathBlackNum,blackNum) &&
                checkBlackNum(root.right,pathBlackNum,blackNum);
    }

    /**
     * 检查是否存在两个连续的红色节点
     * @param root
     * @return
     */
    private boolean checkRedColor(rbTreeNode root) {
        if(root == null) {
            return true;
        }
        if(root.color == COLOR.RED) {
            rbTreeNode parent = root.parent;
            if(parent.color == COLOR.RED) {
                System.out.println("违反了性质：连续出现了两个红色的节点");
                return false;
            }
        }
        return checkRedColor(root.left) && checkRedColor(root.right);
    }
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

红黑树的删除

http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html

AVL树和红黑树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是 O（log2N），红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

红黑树的应用

java集合框架中的：TreeMap**、TreeSet底层使用的就是红黑树**
C++ STL库 – map/set、mutil_map/mutil_set
linux内核：进程调度中使用红黑树管理进程控制块，epoll在内核中实现时使用红黑树管理事件块
其他一些库：比如nginx中用红黑树管理timer等

完整代码

package RBtree;


/**
 * @author SunYuHang
 * @date 2022-12-17 21:34
 * @ClassName : rbTree  //类名
 */

public class rbTree {
    static class rbTreeNode {
        public rbTreeNode left;
        public rbTreeNode right;
        public rbTreeNode parent;
        public int val;
        public COLOR color;
        public rbTreeNode(int val) {
            this.val = val;
            //我们新创建的结点，颜色默认是红色的 为什么呢？见下面详解！
            this.color = COLOR.RED;
        }
    }

    public rbTreeNode root;

    public boolean insert(int val) {
        rbTreeNode node = new rbTreeNode(val);
        if (root == null) {
            root = node;
            return true;
        }
        rbTreeNode parent = null;
        rbTreeNode cur = root;
        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val == val) {
                return false;
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
        //cur == null
        if (parent.val < val) {
            parent.right = node;
        } else {
            parent.left = node;
        }

        node.parent = parent;
        cur = node;
        //红黑树来说：需要调整颜色
        while (parent!=null && parent.color ==COLOR.RED){
            rbTreeNode grandFather = parent.parent; //这个引用不可能为空
            //cur为红，p为红，g为黑，u存在且为红
            if (parent ==  grandFather.left){
                rbTreeNode  uncle = grandFather.right;
                if (uncle!=null && uncle.color == COLOR.RED){
                    //将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。
                    parent.color= COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandFather.color =COLOR.RED;
                }else{//uncle不存在 || uncle是黑色
                    //cur为红，p为红，g为黑，u不存在/u为黑
                    //情况三：
                    if(cur == parent.right) {
                        rotateLeft(parent);
                        rbTreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;
                    }//情况三  变成了情况二

                    //情况二
                    rotateRight(grandFather);
                    grandFather.color = COLOR.RED;
                    parent.color = COLOR.BLACK;
                }
            }else {
                //parent == grandFather.right
                rbTreeNode uncle = grandFather.left;
                if(uncle != null && uncle.color == COLOR.RED) {
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandFather.color = COLOR.RED;
                    //继续向上修改
                    cur = grandFather;
                    parent = cur.parent;
                }else {
                    //uncle不存在 或者 uncle是黑色的
                    //情况三：
                    if(cur == parent.left) {
                        rotateRight(parent);
                        rbTreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;
                    }//情况三  变成了情况二
                    //情况二
                    rotateLeft(grandFather);
                    grandFather.color = COLOR.RED;
                    parent.color = COLOR.BLACK;
                }

            }
        }
        root.color = COLOR.BLACK;
        return true;
    }
    /**
     * 左单旋
     * @param parent
     */
    private void rotateLeft(rbTreeNode parent) {
        rbTreeNode subR = parent.right;
        rbTreeNode subRL = subR.left;

        parent.right = subRL;

        subR.left = parent;
        if(subRL != null) {
            subRL.parent = parent;
        }

        rbTreeNode pParent = parent.parent;
        parent.parent = subR;

        if(root == parent) {
            root = subR;
            root.parent = null;
        }else {
            if(pParent.left == parent) {
                pParent.left = subR;
            }else {
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
    }

    /**
     * 右单旋
     * @param parent
     */
    private void rotateRight(rbTreeNode parent) {

        rbTreeNode subL = parent.left;
        rbTreeNode subLR = subL.right;

        parent.left = subLR;
        subL.right = parent;
        //没有subLR
        if(subLR != null) {
            subLR.parent = parent;
        }
        //必须先记录
        rbTreeNode pParent = parent.parent;
        parent.parent = subL;
        //检查 当前是不是就是根节点
        if(parent == root) {
            root = subL;
            root.parent = null;
        }else {
            //不是根节点，判断这棵子树是左子树还是右子树
            if(pParent.left == parent) {
                pParent.left = subL;
            }else {
                pParent.right = subL;
            }
            subL.parent = pParent;
        }
    }

    /**
     * 判断当前树 是不是红黑树
     *  得满足 红黑树的性质
     * @return
     */
    public boolean isRBTree() {
        if(root == null) {
            //如果一棵树是空树，那么这棵树就是红黑树
            return true;
        }

        if(root.color != COLOR.BLACK) {
            System.out.println("违反了性质：根节点必须是黑色的！");
        }

        //存储当前红黑树当中 最左边路径的黑色的节点个数
        int blackNum = 0;
        rbTreeNode cur = root;
        while (cur != null) {
            if(cur.color == COLOR.BLACK) {
                blackNum++;
            }
            cur = cur.left;
        }
        //检查是否存在两个连续的红色节点  && 每条路径上黑色的节点的个数是一致的
        return checkRedColor(root) && checkBlackNum(root,0,blackNum);
    }

    /**
     *
     * @param root
     * @param pathBlackNum 每次递归的时候，计算黑色节点的个数  0
     * @param blackNum 事先计算好的某条路径上的黑色节点的个数   2
     * @return
     */
    private boolean checkBlackNum(rbTreeNode root,int pathBlackNum,int blackNum) {
        if(root == null) {
            return true;
        }
        if(root.color == COLOR.BLACK) {
            pathBlackNum++;
        }
        if(root.left == null && root.right == null) {
            if(pathBlackNum != blackNum) {
                System.out.println("违反了性质：每条路径上黑色的节点个数是不一样的！");
                return false;
            }
        }
        return checkBlackNum(root.left,pathBlackNum,blackNum) &&
                checkBlackNum(root.right,pathBlackNum,blackNum);
    }

    /**
     * 检查是否存在两个连续的红色节点
     * @param root
     * @return
     */
    private boolean checkRedColor(rbTreeNode root) {
        if(root == null) {
            return true;
        }
        if(root.color == COLOR.RED) {
            rbTreeNode parent = root.parent;
            if(parent.color == COLOR.RED) {
                System.out.println("违反了性质：连续出现了两个红色的节点");
                return false;
            }
        }
        return checkRedColor(root.left) && checkRedColor(root.right);
    }

    public void inorder(rbTreeNode root) {
        if(root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }
    

}



package RBtree;

public enum COLOR {
    RED,BLACK
}

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/578757