Java高阶数据结构之红黑树_java 红黑树

---

提示：以下是本篇文章正文内容，Java系列学习将会持续更新

数据结构动态模型：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

一、红黑树的概念

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

红黑树的性质:

1. 最长路径最多是最短路径的2倍
   原因：每条路径黑色节点数相同，则最短路径 = 没有红色节点的路径(一般不会出现这种极端情况)；最长路径 = 红色节点最多的路径(由于红色节点不能连续，所以最多也就是和黑色节点数相同)。所以, 最长路径 = 2 x 最短路径 = 2 x 黑色节点数
2. 每个结点不是红色就是黑色
3. 根节点是黑色的
4. 如果一个节点是红色的，则它的两个孩子结点是黑色的【没有2个连续的红色节点】
5. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
6. 每个叶子结点都是黑色的 (此处的叶子结点指的是空结点)

回到目录…

二、插入和调整

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

1. 按照二叉搜索的树规则插入新节点
2. 检测新节点插入后，红黑树的性质是否造到破坏
   因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论。

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

情况一: cur为红，p为红，g为黑，u存在且为红

解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

回到目录…

情况二: cur为红，p为红，g为黑，u不存在/u为黑

说明: u的情况有两种

1. 如果u节点不存在，则cur- -定是新插入节点，因为如果cur不是新插入节点，则cur和p一定有一个节点的颜色是黑色，就不满足性质4:每条路径黑色节点个数相同。
2. 如果u节点存在,则其-定是黑色的，那么cur节点原来的颜色一定是黑色的,现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色。

解决方式：
p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，
p为g的右孩子，cur为p的右孩子，则进行左单旋转
p、g变色 —— p变黑，g变红

回到目录…

情况三: cur为红，p为红，g为黑，u不存在/u为黑

解决方式：
p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，
p为g的右孩子，cur为p的左孩子，则针对p做右单旋转
则转换成了情况2

回到目录…

四、删除

博客园：红黑树的删除
CSDN：红黑树

五、性能分析

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

红黑树的应用：

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

回到目录…

六、完整代码

public class RBTree {

    class RBTreeNode {
        RBTreeNode left = null;
        RBTreeNode right = null;
        RBTreeNode parent = null;
        COLOR color; // 节点的颜色
        int val;

        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) {
            this.root = node;
            root.color = COLOR.BLACK;
            return true;
        }

        RBTreeNode parent = null;
        RBTreeNode cur = root;
        while (cur != null) {
            if (val == cur.val) {
                return false;
            } else if (val < cur.val) {
                parent = cur;
                cur = cur.left;
            } else {
                parent = cur;
                cur = cur.right;
            }
        }
        // 此时，cur = null
        if (val < parent.val) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        node.parent = parent;
        cur = node;

        // 调整颜色
        // 新节点插入后，如果parent节点的颜色是红色，一定违反性质三
        while (parent != null && parent.color == COLOR.RED) {
            RBTreeNode grandFather = parent.parent;
            if (parent == grandFather.left) {
                RBTreeNode uncle = grandFather.right;
                if (uncle != null && uncle.color == COLOR.RED) {
                    // 情况一：叔叔节点存在且为红,
                    // 解决方式：将叔叔和父节点改为黑色，祖父节点改为红色
                    // 如果祖父的双亲节点的颜色是红色，需要继续往上调整
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandFather.color = COLOR.RED;
                    // 把 g当成cur，继续向上调整
                    cur = grandFather;
                    parent = cur.parent;
                } else { // 此时，叔叔节点不存在 || 叔叔节点存在，但是颜色是黑色
                    // 再讨论cur是左孩子还是右孩子 ?
                    if (cur == parent.left) {
                        // 情况二
                        rotateR(grandFather);
                        parent.color = COLOR.BLACK;
                        grandFather.color = COLOR.RED;
                    } else {
                        // 情况三
                        rotateL(parent);
                        RBTreeNode temp = parent;
                        parent = cur;
                        cur = temp;
                    }
                }
            } 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;
                    // 把 g当成cur，继续向上调整
                    cur = grandFather;
                    parent = cur.parent;
                } else { // 此时，叔叔节点不存在 || 叔叔节点存在，但是颜色是黑色
                    // 再讨论cur是左孩子还是右孩子 ?
                    if (cur == parent.right) {
                        // 情况二
                        rotateL(grandFather);
                        parent.color = COLOR.BLACK;
                        grandFather.color = COLOR.RED;
                    } else {
                        // 情况三
                        rotateR(parent);
                        RBTreeNode temp = parent;
                        parent = cur;
                        cur = temp;
                    }
                }
            }
        }
        // 在上述循环更新期间，可能会将根节点给成红色，因此此处必须将根节点改为黑色
        root.color = COLOR.BLACK;
        return true;
    }

    // 左单旋
    private void rotateL(RBTreeNode p) {
        // p 的母节点
        RBTreeNode pp = p.parent;
        // p 的右孩子
        RBTreeNode subR = p.right;
        // subR 的左孩子，可能不存在
        RBTreeNode subRL = subR.left;

        // subR 提上去
        if (pp == null) {
            this.root = subR;
        } else if (pp.left == p) {
            pp.left = subR;
        } else {
            // pp.right == parent
            pp.right = subR;
        }
        subR.parent = pp;
        // p 作为 subR 的左孩子
        subR.left = p;
        p.parent = subR;
        // p 与 subRL 连接
        p.right = subRL;
        if (subRL != null) {
            subRL.parent = p;
        }
    }

    // 右单旋
    private void rotateR(RBTreeNode p) {
        // p 的父节点
        RBTreeNode pp = p.parent;
        // p 的左孩子
        RBTreeNode subL = p.left;
        // subL 的右孩子，可能不存在
        RBTreeNode subLR = subL.right;

        if (pp == null) {
            this.root = subL;
        } else if (pp.left == p) {
            pp.left = subL;
        } else {
            pp.right = subL;
        }
        subL.parent = pp;
        subL.right = p;
        p.parent = subL;
        p.left = subLR;
        if (subLR != null) {
            subLR.parent = p;
        }
    }

    /**
     * 打印二叉树, 中序遍历的结果
     **/
    @Override
    public String toString() {
        List<Integer> list = new ArrayList<>();
        inOrder(list, root);
        return list.toString() + "\n" + "是否标准红黑树: " + isValidRBTree();
    }
    // 中序遍历
    private void inOrder(List<Integer> list, RBTreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(list, root.left);
        list.add(root.val);
        inOrder(list, root.right);
    }
    /**
     * 检验是否符合红黑树的性质
     */
    private boolean isValidRBTree() {
        // 空树也是红黑树
        if (root == null) {
            return true;
        }
        // 根节点是黑色
        if (root.color != COLOR.BLACK) {
            System.err.println("违反了性质2：根节点不是黑色");
            return false;
        }
        // 获取单条路径中节点的个数
        int blackCount = 0;
        RBTreeNode cur = root;
        while (cur != null) {
            if (cur.color == COLOR.BLACK) {
                blackCount ++;
            }
            cur = cur.left;
        }
        // 具体的检验方式
        return _isValidRBtree(root, 0, blackCount);
    }
    // 检验是否存在连续的红色节点
    // 检验是否每条路径黑色节点数相同
    private boolean _isValidRBtree(RBTreeNode root, int pathCount, int blackCount) {
        if (root == null) {
            return true;
        }
        // 遇到一个黑色节点，统计当前路径中黑色节点个数
        if(root.color == COLOR.BLACK) {
            pathCount ++;
        }
        // 验证性质4
        RBTreeNode parent = root.parent;
        if(parent != null && parent.color == COLOR.RED && root.color == COLOR.RED) {
            System.err.println("违反了性质4：有连在一起的红色节点");
            return true;
        }
        // 验证性质5
        // 如果是叶子节点，则一条路径已经走到底，检验该条路径中黑色节点总个数是否与先前统计的结果相同
        if (root.left == null && root.right == null) {
            if (pathCount != blackCount) {
                System.err.println("违反了性质5：每条路径中黑色节点个数不一致");
                return false;
            }
        }
        // 以递归的方式检测 root 的左右子树
        return _isValidRBtree(root.left, pathCount, blackCount) &&
                _isValidRBtree(root.right, pathCount, blackCount);
    }
}
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

回到目录…

---

总结:
提示：这里对文章进行总结：
以上就是今天的学习内容，本文是Java高阶数据结构的学习，剖析红黑树底层原理，红黑树的时间复杂度，红黑树的插入以及插入时的平衡调整。之后的学习内容将持续更新！！！