红黑树理解以及Java实现_java红黑树原理

作者：运维做开发 | 2024-06-20 05:36:39

踩

java红黑树原理

红黑树本身并不复杂，只是在插入删除的时候情况比较多，如果强行记忆的话会显得比较困难，而且容易忘记。所以以前对红黑树一直没有很好的掌握。恰好这次借着复习数据结构的机会，静下心来仔细的学习了一下红黑树，并用Java实现了一番。所以用这篇文章把我对红黑树的操作的理解记录下来，在理解的基础上记忆会容易得多，这样以后就不用重复学习啦！

1. 红黑树的定义

红黑树是一颗二叉查找树，且具有如下特性：
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点。

2. 操作的核心思想

通过上面的定义，可以看到红黑树本质上还是一颗二叉查找树，所以，对红黑树的插入删除操作都可以分为两阶段来完成，首先，将红黑树看成一颗普通的二叉查找树完成插入删除操作，然后，通过旋转以及颜色调整来使得操作后的树满足红黑树的所有特性即可。

3. 基础操作之左旋右旋

旋转操作是基础操作，后面的一些情况处理就是基于旋转来完成的。所以，首先我们需要理解左旋右旋的工作方式。
对x点进行右旋：
这里写图片描述
对y点进行左旋：

4. 核心操作之插入

说明：以下的讨论，在如下前提下进行：插入的节点为S（son），S的父亲节点为F（father），F的父亲节点为G（grandfather），而F的兄弟节点为U（uncle）。并且F为G的左儿子。（F为G的右儿子对称操作即可）

Step 1：执行二叉搜索树插入逻辑
Step 2：将插入的节点着色为红色

我们希望这次插入尽可能不破坏红黑树的性质，这样我们就可以不用进行额外的调整操作！所以，根据特性(5)，我们显然不能将节点涂成黑色，因为这样所有经过点S的路径的黑色节点都多了一个，就破坏了特性(5)，所以我们将S的颜色首先着色为红。
Step 3：进行适当得旋转以及颜色调整

如果插入节点的父节点是红，那么违反了特性(4)，所以需要进行调整，共有三个case
- case 1：F为红，U为红
  
  操作：将F以及U设置为黑，G设为红，并将G看成新插入的节点（即下一轮的S），递归操作。
  
  原因：这个操作实际是想将红色往根处移动。将红色往上移了一层，并不会打破红黑树的特性，不断的把红色往上移动，当移动到根时，直接将根设置为黑色，就完全符合红黑树的性质了。
- case 2：F为红，U为黑，并且，S为F的右儿子
  
  操作：将F左旋，并把F看成新加入的节点（即下一轮的S），继续后面的判断。
  
  原因：这个操作是为了将这一case转换为case 3，
- case 3：F为红，U为黑，并且，S为F的左儿子
  
  操作：先将F设为黑，G设为红，然后G右旋。这样操作后，就完全符合红黑树的性质了。
  
  原因：G与F颜色互换，对左边路并没有影响，不过，对于右边路来说，由于G变为了红，其实少了一个黑，因此，将G右旋，使得黑色的F变为新的G，这样，就为右边路加回去了一个黑，而左边路只是损失了一个红，并不影响红黑树的平衡，这样操作后将会完全符合红黑树的性质，之所以说是完全符合，因为原来G的地方是个黑色节点，后来用了黑色的F去代替了G，对于G往上的层来说，并没有发生颜色变化，自然就是平衡的，所以，经过这一步的操作，红黑树恢复所有特性。

5. 核心操作之删除

说明：S的父亲节点为P，S的兄弟节点为B，B的左儿子为BL，B的右儿子为BR，且S为P的左儿子。（S为P的右儿子对称操作即可）

step 1：进行二叉查找树的删除操作

二叉查找树的删除操作相对来说还是比较复杂，涉及到替代节点的选择等一些情况，如果不了解这一过程的可以自己去百度一下。我们假设想要删除的节点是X，找到的替代节点为Y（选择方式是X的右子树的最小点），那么我们可以将Y的值拷贝到X，然后将这个Y删除，将Y删除，也会需要有一个人顶替现在的Y的位置，我们设为S，接下来的讨论就会围绕着S展开。

step 2：红黑树性质判断

由于我们将Y删除了，并且用S代替了Y的位置，如果Y原来是红色的，那么并不会破坏红黑树的颜色平衡，我们不需要额外的操作，删除成功！如果Y是黑色的，那么相当于经过Y的路径（现在是经过S）都会少了一个黑。那么我们怎么把这个黑弥补回来呢？那就是给S再加上一个黑，用来弥补删除Y而损失的那个黑。这时候，相当于S节点拥有了两个颜色，违反了特性(1)，所以，我们现在想办法把这个多出来的黑色删除掉！
如果原来S是红色的，那么我们直接不要S的红色，将S设置为黑色即可，因为丢弃红色是不会打破红黑树的颜色平衡的，我们这一操作时安全的。可是，如果S原来就是黑色呢？那就要看S是不是根了，如果是根，将黑色丢弃了也没啥，相当于所有的路径都减少了一个黑，也是不影响平衡的，最糟糕的情况在于S原来时黑，且不是根，这时候，我们就要进行一些旋转以及颜色调整来恢复红黑树的特性了！

step 3旋转以及颜色调整

共有四个case：
- Case 1: S是“黑+黑”，且B为红。
  
  操作：将P设为红，B设为黑，然后将P左旋，这时S获得了新的B，用新的B进行后续的判断
  
  原因：在这种情况下，我们可以得到P必定为黑，并且BL & BR 也都为黑。由于我们想要左旋，而又不能破坏红黑树的平衡，所以，将P设为红，B设为黑。左旋的目的是让S有新的B，从而转化为后面的case 2 or 3 or 4，进行下一步的操作。
- Case 2：S是“黑+黑”，且B为黑，并且BL BR也都是黑。
  
  操作：将B设为红，并且让P为新的S，进行新一轮的递归。
  
  原因：我们的目的就是想让多余的黑往上走，这时候，把这个多余的黑给到P，左边路的黑是不变的，而右边路多了一个，为了平衡，恰好BL BR都是黑，所以我们直接把B设为红就好啦，这样，黑就上浮到了P，将P看作新的起点，递归后面的操作就好啦~！
- Case 3：S是“黑+黑”，且B为黑，并且BL为红，BR为黑。
  
  操作：将B设为红，BL设为黑，然后B右旋
  
  原因：这个操作是为了转换到case 4。B和BL的颜色互换也是为了平衡。
- S是“黑+黑”，且B为黑，并且BR为红，BL任意颜色。
  
  操作：将P的颜色给到B，将P设为黑，将BR设为黑，对P左旋，最后将S设置为root以结束循环。
  
  （注：蓝色表示任意颜色）
  
  原因：这是最复杂的一种情况了。我们将P的颜色给到B，然后将P左旋，这时候，不管P初始是什么颜色，对于左边路来说，都多了一个黑色，为了保证颜色平衡，正好把S中多余的那个黑丢掉啦！但是左旋带来了一些后遗症，首先是BL变成了P的儿子，而这里我们不关心BL的颜色，所以，必须要把P设置为黑色，这样即使BL为红色也不会破坏红黑树，还有一点，不管P的初始颜色，左旋之后，右边路少了一个黑，为了补回来，我们让BR由红变黑就好啦！这就是完整的操作，精髓在于通过左旋P来消除多余的那个黑色，但由于左旋带来的后遗症需要相应的<改变颜色>措施来弥补。

6. 完整java实现

节点：

package RBTree;

import java.util.Objects;

public class RBTreeNode {
    private final boolean RED = false;
    private final boolean BLACK = true;
    private int key;
    private boolean color;
    private RBTreeNode left;
    private RBTreeNode right;
    private RBTreeNode parent;

    public RBTreeNode(int key) {
        this.key = key;
        this.color = RED;
    }

    public int getKey() {
        return key;
    }

    public void setKey(int key) {
        this.key = key;
    }

    public boolean getColor() {
        return color;
    }

    public void setColor(boolean color) {
        this.color = color;
    }

    public RBTreeNode getLeft() {
        return left;
    }

    public void setLeft(RBTreeNode left) {
        this.left = left;
    }

    public RBTreeNode getRight() {
        return right;
    }

    public void setRight(RBTreeNode right) {
        this.right = right;
    }

    public RBTreeNode getParent() {
        return parent;
    }

    public void setParent(RBTreeNode parent) {
        this.parent = parent;
    }

    @Override
    public String toString() {
        return "RBTreeNode{" +
                ",key=" + key +
                ", color=" + color +
                '}';
    }
}

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

树：

package RBTree;

public class RBTree {
    RBTreeNode root;
    private final boolean RED = false;
    private final boolean BLACK = true;

    public RBTreeNode query(int key) {
        RBTreeNode tmp = root;
        while (tmp != null) {
            if (tmp.getKey() == key)
                return tmp;
            else if (tmp.getKey() > key)
                tmp = tmp.getLeft();
            else
                tmp = tmp.getRight();
        }
        return null;
    }

    public void insert(int key) {
        RBTreeNode node = new RBTreeNode(key);
        if (root == null) {
            root = node;
            node.setColor(BLACK);
            return;
        }
        RBTreeNode parent = root;
        RBTreeNode son = null;
        if (key <= parent.getKey()) {
            son = parent.getLeft();
        } else {
            son = parent.getRight();
        }
        //find the position
        while (son != null) {
            parent = son;
            if (key <= parent.getKey()) {
                son = parent.getLeft();
            } else {
                son = parent.getRight();
            }
        }
        if (key <= parent.getKey()) {
            parent.setLeft(node);
        } else {
            parent.setRight(node);
        }
        node.setParent(parent);

        //fix up
        insertFix(node);
    }

    private void insertFix(RBTreeNode node) {
        RBTreeNode father, grandFather;
        while ((father = node.getParent()) != null && father.getColor() == RED) {
            grandFather = father.getParent();
            if (grandFather.getLeft() == father) {  //F为G左儿子的情况，如之前的分析
                RBTreeNode uncle = grandFather.getRight();
                if (uncle != null && uncle.getColor() == RED) {
                    setBlack(father);
                    setBlack(uncle);
                    setRed(grandFather);
                    node = grandFather;
                    continue;
                }
                if (node == father.getRight()) {
                    leftRotate(father);
                    RBTreeNode tmp = node;
                    node = father;
                    father = tmp;
                }
                setBlack(father);
                setRed(grandFather);
                rightRotate(grandFather);
            } else {                               //F为G的右儿子的情况，对称操作
                RBTreeNode uncle = grandFather.getLeft();
                if (uncle != null && uncle.getColor() == RED) {
                    setBlack(father);
                    setBlack(uncle);
                    setRed(grandFather);
                    node = grandFather;
                    continue;
                }
                if (node == father.getLeft()) {
                    rightRotate(father);
                    RBTreeNode tmp = node;
                    node = father;
                    father = tmp;
                }
                setBlack(father);
                setRed(grandFather);
                leftRotate(grandFather);
            }
        }
        setBlack(root);
    }

    public void delete(int key) {
        delete(query(key));
    }

    private void delete(RBTreeNode node) {
        if (node == null)
            return;
        if (node.getLeft() != null && node.getRight() != null) {
            RBTreeNode replaceNode = node;
            RBTreeNode tmp = node.getRight();
            while (tmp != null) {
                replaceNode = tmp;
                tmp = tmp.getLeft();
            }
            int t = replaceNode.getKey();
            replaceNode.setKey(node.getKey());
            node.setKey(t);
            delete(replaceNode);
            return;
        }
        RBTreeNode replaceNode = null;
        if (node.getLeft() != null)
            replaceNode = node.getLeft();
        else
            replaceNode = node.getRight();

        RBTreeNode parent = node.getParent();
        if (parent == null) {
            root = replaceNode;
            if (replaceNode != null)
                replaceNode.setParent(null);
        } else {
            if (replaceNode != null)
                replaceNode.setParent(parent);
            if (parent.getLeft() == node)
                parent.setLeft(replaceNode);
            else {
                parent.setRight(replaceNode);
            }
        }
        if (node.getColor() == BLACK)
            removeFix(parent, replaceNode);

    }

    //多余的颜色在node里
    private void removeFix(RBTreeNode father, RBTreeNode node) {
        while ((node == null || node.getColor() == BLACK) && node != root) {
            if (father.getLeft() == node) {  //S为P的左儿子的情况，如之前的分析
                RBTreeNode brother = father.getRight();
                if (brother != null && brother.getColor() == RED) {
                    setRed(father);
                    setBlack(brother);
                    leftRotate(father);
                    brother = father.getRight();
                }
                if (brother == null || (isBlack(brother.getLeft()) && isBlack(brother.getRight()))) {
                    setRed(brother);
                    node = father;
                    father = node.getParent();
                    continue;
                }
                if (isRed(brother.getLeft())) {
                    setBlack(brother.getLeft());
                    setRed(brother);
                    rightRotate(brother);
                    brother = brother.getParent();
                }

                brother.setColor(father.getColor());
                setBlack(father);
                setBlack(brother.getRight());
                leftRotate(father);
                node = root;//跳出循环
            } else {                         //S为P的右儿子的情况，对称操作
                RBTreeNode brother = father.getLeft();
                if (brother != null && brother.getColor() == RED) {
                    setRed(father);
                    setBlack(brother);
                    rightRotate(father);
                    brother = father.getLeft();
                }
                if (brother == null || (isBlack(brother.getLeft()) && isBlack(brother.getRight()))) {
                    setRed(brother);
                    node = father;
                    father = node.getParent();
                    continue;
                }
                if (isRed(brother.getRight())) {
                    setBlack(brother.getRight());
                    setRed(brother);
                    leftRotate(brother);
                    brother = brother.getParent();
                }

                brother.setColor(father.getColor());
                setBlack(father);
                setBlack(brother.getLeft());
                rightRotate(father);
                node = root;//跳出循环
            }
        }

        if (node != null)
            node.setColor(BLACK);
    }

    private boolean isBlack(RBTreeNode node) {
        if (node == null)
            return true;
        return node.getColor() == BLACK;
    }

    private boolean isRed(RBTreeNode node) {
        if (node == null)
            return false;
        return node.getColor() == RED;
    }

    private void leftRotate(RBTreeNode node) {
        RBTreeNode right = node.getRight();
        RBTreeNode parent = node.getParent();
        if (parent == null) {
            root = right;
            right.setParent(null);
        } else {
            if (parent.getLeft() != null && parent.getLeft() == node) {
                parent.setLeft(right);
            } else {
                parent.setRight(right);
            }
            right.setParent(parent);
        }
        node.setParent(right);
        node.setRight(right.getLeft());
        if (right.getLeft() != null) {
            right.getLeft().setParent(node);
        }
        right.setLeft(node);
    }

    private void rightRotate(RBTreeNode node) {
        RBTreeNode left = node.getLeft();
        RBTreeNode parent = node.getParent();
        if (parent == null) {
            root = left;
            left.setParent(null);
        } else {
            if (parent.getLeft() != null && parent.getLeft() == node) {
                parent.setLeft(left);
            } else {
                parent.setRight(left);
            }
            left.setParent(parent);
        }
        node.setParent(left);
        node.setLeft(left.getRight());
        if (left.getRight() != null) {
            left.getRight().setParent(node);
        }
        left.setRight(node);
    }

    private void setBlack(RBTreeNode node) {
        if(node != null) {
			node.setColor(BLACK);
		}
    }

    private void setRed(RBTreeNode node) {
    	if(node != null) {
			node.setColor(RED);
		}
    }

    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(RBTreeNode node) {
        if (node == null)
            return;
        inOrder(node.getLeft());
        System.out.println(node);
        inOrder(node.getRight());
    }
}

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

7. 参考资料

我从这里：https://www.cnblogs.com/skywang12345/p/3624343.html学到了很多的思想，不过，他的图有好些画错了。
这里：http://www.cnblogs.com/geekma/archive/2012/06/27/2566226.html 有一个完整的红黑树操作过程的图示，可以当作很好的测试用例，看看自己的代码是否写对了。

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