全网最强红黑树的理解和实现
程序员文章站
2022-05-16 11:23:55
...
红黑树我估计花费了30个小时左右来理解，看了各种视频和文章，以及阅读treemap的源码，最终自己java实现了一版。
红黑树的理解最重要最重要是 要理解234树，红黑树是由234树演变过来的。任何一颗红黑树都可以转变成一棵234树。对于234树我就这里不说了，自己百度下。
红黑树与234树的等价关系
- 2节点 对应 红黑树 就是一个单独的黑色节点
- 3节点 对应 红黑树 上黑下红 ，这里有2种 上黑左红 和上黑右红
- 4节点 对应 红黑树 上黑下面2个红
这3个关系牢记在心，我们其实可以看出每个节点都会只有一个黑色节点。把一颗红黑树转变成234树，可以从下往上看，父节点是黑色，当前节点是红色的 ，可以合并3或者4节点。
查询
查询和二叉树的查询是一样的，从根下面开始找，逐个判断值，小于就继续找左子树，大于找右子树。
插入 借助3个等价关系来处理
我们这里有个约束条件，插入的默认都是红色的。为什么这样做，因为当我们把红黑树转变成234树的时候，其实234树的每个节点都应该有且只有一个黑节点，红色节点可以有多个，这样黑色节点其实就是表示一个234节点，他们就有了个映射关系。我们从空开始逐个进行。
- 树一开始是空的，直接插入，因为根节点定义是黑色的，所以变黑
- 树不是空的，插入的位置肯定是挂在某个父节点上面，所以有2种情况，a.父节点是黑 b父节点红色，我们看等价关系，可以知道，红色节点是可以直接挂在黑色节点下面的。但是如果是父亲是红色节点，那么违反了等价关系，不能出现2个红色连一起的情况，这个时候我们需要进行调整。
调整
我们的调整都是基于上面已经排好的情况的，因为每次我们插入都是调整好了的。调整需要和234树进行分情况处理
- 插入到2节点（一个黑色节点）这种情况上面说了可以直接插入，就变成了3节点上黑下红。不需要调整
-
插入到3节点（上黑下红），严格来说，这里插入的位置有6种。
上黑左红：3种（左孩子的下面2种+黑节点的右边）
上黑右红：3种（右孩子的下面2种+黑色节点的左边）
上面讲了，只有插入的位置父节点是红色情况才需要调整，如果直接插入到黑节点的左边或者右边，那么就变成了4节点，无需调整。
因此需要调整的是3节点的4种情况。而这里面的4种情况我们只需要分析2种就行了，另外2种镜像操作。
分析上黑左红情况，插入点：左红的左孩子。现在的状态是从上到下为 黑 -红 - 红，想一想4节点是什么样的，4节点为上黑左右红，那我们可以把这个转变成4节点。
怎么转变：黑（A）- 红（B）-红（C待插入） 他们是在一条线上。
最终是变成4节点，可以通过把A进行右旋，那么就变成了
A （黑） B
/ / \
B （红） => C A 然后B变黑，A变红，调整完成
/
C （红）
分析上黑右红 可以把B左旋成上一种情况进行处理
A（黑） A(黑) B
/ / / \
B （红） => B（红） => C A
\ /
C （红） C（红）
如果直接把A进行右旋，虽然整体大小顺序合法，但是B没有左子树，那么当B变成A为父节点的那个位置时候，B的左边就空了，整颗树就不平衡了。
B
\
A
/
C
这个形态不属于任何234节点任何一种。
- 插入到4节点（3个元素）
A(黑)
/ \
B（红）C（红）
/
D(红 待插入)
D的位置可以有4个方向，对于234树的4节点插入，总会产生裂变 分裂出2个子节点，一个是2节点，一个是3节点。对于父节点可能是单独的黑节点，也可能是与别人组合的红节点，都是可能的。而且裂变之后，上升的父节点可能还会跟别的兄弟节点进行合并继续裂变。这里就是继续递归父节点的过程。
那么我们也要把他转变成2种节点，一个黑色节点和上黑下红，也就是说得至少得有2个黑色的节点。
这里D可以与父节点B组成一个上黑下红的3节点，而另一边的C可以变成一个独立的黑色2结点。因此可以把B和C变黑。问题来了，如果B和C变黑色，A不变色，那么这个局部的树就会多了一个黑色节点，那么整个树会黑色不平衡，因此我们还得把A变成红色才行。
根据234树的裂变规则，父亲节点可能还会继续合并后裂变，对应于我们红黑树，A变成了红色节点，那么A得上面可能也是红色的，所以我们继续递归A节点就行了。
以上就是红黑树的插入过程。
删除 略微复杂
- 删除和二叉树的删除一样，当删除的节点有左右孩子的时候，直接找它的前驱或者后继节点，然后交换值，这样就变成了删下面的前驱或者后继节点了。
- 前驱或者后继节点的位置有3种：a. 落在叶子节点上 b 落在倒数第二层且有一个孩子的节点上 c落在上层节点 。画个图想一想就知道了，这个不懂的可以百度下查找前驱或者后继节点的博客。
- 问题就变成了删除叶子节点或者倒数第二层有一个孩子的节点。而对于删除，落在上层节点的情况可以不考虑，因为如果是落在上层节点上，那么这个节点肯定没有左孩子或者右孩子，那就是倒数第二层。
调整
删除为叶子节点情况
a. 叶子是红色
红色节点不影响黑色的平衡，直接删除
b.叶子是黑色
删除了会影响平衡 需要调整。
红黑树的黑色叶子节点，对应于234树就是一个2节点 。删除了他，那么他需要找兄弟节点去借。所以继续分析兄弟节点能不能借出的情况。
能借出的情况 兄弟节点是3或者4结点，因为他们有>1个的元素，有红节点。
兄弟3节点 删除B情况 兄弟4节点
A（?） A(?) A(?)
/ \ / \ / \
B(黑) C（黑） B(黑) C(黑) B（黑） C(黑)
\ / / \
D (红) D(红) D（红）E（红）
怎么借？我们肯定不能通过直接赋值的方式借过来，因为还要考虑顺序，所以得通过旋转的方式来借。我总结的核心点就是相互顶替来达到原来的颜色状态且顺序合法。
- 拿3节点第一种情况来说，B是将要删除的点，他是黑色的，父亲我们不确定，可以为黑也可以为红，因为不影响这个局部的树的黑色平衡。B - A - C- D，只要我们把A顶替B,把C顶替A，D顶替C就行得通了。其实这个顶替在函数上实现就是旋转操作在这里就是A左旋，不过也不能直接随便旋转的，为什么？
因为旋转不会考虑C有没有右孩子的情况，假如C没有了右孩子，那么左旋后C变成了父亲，C的右边就空的了。所以必须得要一个元素来顶替C。因此对于3节点是第二种情况，我们得把C进行右旋就变成
A(?)
/ \
B(黑)D(黑)
\
C(红)
然后用第一种情况处理
- 4节点处理： 4节点左边和右边都有孩子，不需要经过什么特殊的旋转处理，直接用3节点第一种情况处理即可。
不能接出情况 兄弟节点是2节点只有一个元素 这个情况兄弟无法接出，那么就看父亲了
A(?)
/ \
B(黑)C(黑色)
- 假如父亲是红色节点，可以拿父亲来顶替下面2个孩子，注意是2个，因为B和C 是在同一层，B是要删除的，那么把C也删了（C变红），整棵树仍然只少了一个，而父亲是红色的，直接把父亲变成黑色就顶替上就OK了。
- 假如父亲是黑色的，父亲借不了。我们先把C变红，相当于这棵树还是只少了一个黑色的，我们再把父亲当做要删除的黑色叶子节点，继续下一轮递归调整。
删除为倒数第二层且有一个孩子的情况
A
/
B（黑）
\
C（红）
要删除B，把B唯一的孩子顶上去就行了，假如B是黑色，C顶上去也变成黑色。因为删除最终也是落在234树的叶子节点，无非就3种，2节点，3节点和4节点，B只能是黑色，C只能是红色。
关于兄弟节点是红色情况
转变为234树
A（只能是黑） AC C
/ \ /|\ / \
B(黑)C(红色) => B D E =>A左旋 A E
/ \ / \
D(黑)E(黑) B D
肯定有人说兄弟节点还有是红色情况呢，如果在红黑树上兄弟节点是红色，那么这个兄弟节点在234树上对应起来其实并不是真正的兄弟节点，比如这个里的C，他其实是和A在一起的，组成一个3节点，且C下面肯定还有节点。那么我们得要先找打真正的兄弟节点，或许你也可以直接在大脑种想象，C的左孩子是他的兄弟节点，但是为了在红黑2叉树上处理方便，我们可以把他转变下，把A进行左旋，那么B和D就成了真正的兄弟节点，然后同样套用之前的方式进行处理。
实现的JAVA代码
package com.lsz.im.test;
import lombok.Getter;
import lombok.Setter;
public class RBTree<K extends Comparable<K>, V> {
public static final boolean BLACK = true;
public static final boolean RED = false;
private Node<K, V> root = null;
@Getter
@Setter
public static class Node<K extends Comparable<K>, V> {
private K key;
private V value;
private boolean color = BLACK;
private Node<K, V> parent;
private Node<K, V> left;
private Node<K, V> right;
public Node(K key, V value, Node<K, V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
public Node() {
}
}
private void writeArray(Node currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
// 保证输入的树不为空
if (currNode == null) return;
// 先将当前节点保存到二维数组中
res[rowIndex][columnIndex] = String.valueOf(currNode.key + "(" + (currNode.color ? "黑" : "红") + ")");
// 计算当前位于树的第几层
int currLevel = ((rowIndex + 1) / 2);
// 若到了最后一层，则返回
if (currLevel == treeDepth) return;
// 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
int gap = treeDepth - currLevel - 1;
// 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
if (currNode.left != null) {
res[rowIndex + 1][columnIndex - gap] = "/";
writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
}
// 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
if (currNode.right != null) {
res[rowIndex + 1][columnIndex + gap] = "\\";
writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
}
}
public void show() {
if (root == null) System.out.println("EMPTY!");
// 得到树的深度
int treeDepth = getTreeDepth(root);
// 最后一行的宽度为2的（n - 1）次方乘3，再加1
// 作为整个二维数组的宽度
int arrayHeight = treeDepth * 2 - 1;
int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
// 用一个字符串数组来存储每个位置应显示的元素
String[][] res = new String[arrayHeight][arrayWidth];
// 对数组进行初始化，默认为一个空格
for (int i = 0; i < arrayHeight; i++) {
for (int j = 0; j < arrayWidth; j++) {
res[i][j] = " ";
}
}
// 从根节点开始，递归处理整个树
// res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
writeArray(root, 0, arrayWidth / 2, res, treeDepth);
// 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
for (String[] line : res) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < line.length; i++) {
sb.append(line[i]);
if (line[i].length() > 1 && i <= line.length - 1) {
i += line[i].length() > 4 ? 2 : line[i].length() - 1;
}
}
System.out.println(sb.toString());
}
}
private int getTreeDepth(Node root) {
return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
}
public boolean colorOf(Node<K, V> node) {
return node == null ? BLACK : node.color;
}
public Node<K, V> parentOf(Node<K, V> node) {
return node == null ? null : node.parent;
}
private Node<K, V> leftOf(Node<K, V> node) {
return (node == null) ? null : node.left;
}
private Node<K, V> rightOf(Node<K, V> node) {
return (node == null) ? null : node.right;
}
private void setColor(Node<K, V> node, boolean color) {
if (node != null) {
node.color = color;
}
}
/**
* <pre>
* tp tp
* / /
* a c
* / \ =>左旋 / \
* b c a e
* / \ / \
* d e b d
*
* </pre>
* <p>
* 左旋 必备条件 target 有右孩子
*
* @param a
*/
public void leftRotate(Node<K, V> a) {
if (a == null || a.right == null) {
return;
}
Node<K, V> c = a.right;
Node<K, V> d = c.left;
Node<K, V> targetParent = a.parent;
c.left = a;
a.parent = c;
a.right = d;
//考虑a的父节点
c.parent = targetParent;
if (targetParent == null) {
root = c;
} else if (targetParent.left == a) {
targetParent.left = c;
} else if (targetParent.right == a) {
targetParent.right = c;
}
}
/**
* 右旋 必备条件 target 有左孩子
*
* @param c
*/
public void rightRotate(Node<K, V> c) {
if (c == null || c.left == null) {
return;
}
Node<K, V> a = c.left;
Node<K, V> d = a.right;
Node<K, V> targetParent = c.parent;
a.right = c;
c.parent = a;
c.left = d;
a.parent = targetParent;
if (targetParent == null) {
root = a;
} else if (targetParent.left == c) {
targetParent.left = a;
} else if (targetParent.right == c) {
targetParent.right = a;
}
}
public V get(K key) {
Node<K, V> node = getNode(key);
return node == null ? null : node.value;
}
private Node<K, V> getNode(K key) {
Node<K, V> find = root;
while (find != null) {
int cmp = key.compareTo(find.key);
if (cmp > 0) {
find = find.right;
} else if (cmp < 0) {
find = find.left;
} else {
break;
}
}
return find;
}
/**
* 插入
*
* @param key
* @param value
* @return
*/
public V put(K key, V value) {
if (key == null) {
throw new UnsupportedOperationException("key 不能为空");
}
if (root == null) {
root = new Node<>(key, value, null);
}
//查找应该放到哪个节点下面 从跟开始找
Node<K, V> tmp = this.root;
Node<K, V> parent = null;
int cmp = 0;
while (tmp != null) {
parent = tmp;
cmp = key.compareTo(tmp.key);
if (cmp > 0) {
tmp = tmp.right;
} else if (cmp < 0) {
tmp = tmp.left;
} else {
V oldValue = tmp.getValue();
tmp.value = value;
return oldValue;
}
}
Node<K, V> newNode = new Node<>(key, value, parent);
if (cmp > 0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
fixAfterInsert(newNode);
return null;
}
/**
* 插入都是红色的<br>
* 调整插入后的红黑树,需要调整的基本条件是 插入的值父亲是红色<br>
* 1.插入到3节点6种情况的4种情况<br>
* 2.插入4节点的4种情况<br>
*
* @param newNode
*/
private void fixAfterInsert(Node<K, V> newNode) {
if (newNode == null) {
return;
}
if (newNode == root) {
root.color = BLACK;
return;
}
newNode.color = RED;
if (colorOf(parentOf(newNode)) == RED) {
if (parentOf(newNode) == leftOf(parentOf(parentOf(newNode)))) { //左倾情况
Node<K, V> uncle = rightOf(parentOf(parentOf(newNode)));
if (colorOf(uncle) == BLACK) { //3节点 parent.parent可能发送空指针异常，所以得封装
if (newNode == rightOf(parentOf(newNode))) {
//当前是处于右边 旋转成 左边情况减少处理
newNode = parentOf(newNode);
leftRotate(newNode);
}
setColor(parentOf(newNode), BLACK);
setColor(parentOf(parentOf(newNode)), RED);
rightRotate(parentOf(parentOf(newNode))); //右旋爷节点
} else { //4节点
//父亲和叔叔 红变黑 爷爷变红
setColor(parentOf(newNode), BLACK);
setColor(uncle, BLACK);
setColor(parentOf(parentOf(newNode)), RED); //爷爷变红了就转变成插入是爷爷红节点的情况 循环一遍
fixAfterInsert(parentOf(parentOf(newNode)));
}
} else { //右倾
Node<K, V> uncle = leftOf(parentOf(parentOf(newNode)));
if (colorOf(uncle) == BLACK) { //3节点
if (newNode == leftOf(parentOf(newNode))) {
newNode = parentOf(newNode);
rightRotate(newNode);
}
setColor(parentOf(newNode), BLACK);
setColor(parentOf(parentOf(newNode)), RED);
leftRotate(parentOf(parentOf(newNode)));
} else { //4节点
setColor(parentOf(newNode), BLACK);
setColor(uncle, BLACK);
setColor(parentOf(parentOf(newNode)), RED);
fixAfterInsert(parentOf(parentOf(newNode)));
}
}
}
}
/**
* 删除 <br>
* <p>
* 1.要删除的如果是有2个孩子，寻找他的后继。后继和要删除的互换值，再删除后继节点。后继必然是处于234的叶子上，
* 对应于红黑树的倒数1或倒数2层 <br>
* 2.要删除的处于倒数第一层，如果是红色节点不需要调整，如果是黑色需要调整 <br>
* 3.要删除的处于倒数第二层，属于3节点，所以该节点必然是黑节点，且下面是一个红色孩子，删除黑色节点，然后把下面的红色节点顶替上来，颜色变成黑色<br>
*
* @param key
*/
public V remove(K key) {
Node<K, V> node = getNode(key);
if (node == null)
return null;
V oldValue = node.value;
//删除
if (node.left != null && node.right != null) { //值交换，变成删除后继
Node<K, V> s = successor(node);
node.key = s.key;
node.value = s.value;
node = s;
}
Node<K, V> child = node.left == null ? node.right : node.left;
if (child == null) { //处理倒数第一
if (node.parent == null) {
root = null;
} else {
if (node.color == BLACK) {
fixAfterDelete(node);
}
if (node == node.parent.left) node.parent.left = null;
if (node == node.parent.right) node.parent.right = null;
node.parent = null;
}
} else { //处理倒数第二
child.parent = node.parent;
if (node.parent == null) root = child;
else if (node == node.parent.left)
node.parent.left = child;
else
node.parent.right = child;
node.parent = node.left = node.right = null;
if (node.color == BLACK)
fixAfterDelete(child);
else {
System.err.println("出现了删除2节点倒数第二层不是黑色情况！");
}
}
return oldValue;
}
private void fixAfterDelete(Node<K, V> node) {
if (node.color == RED || node == root) setColor(node, BLACK); //上黑下红，删除黑，红色顶替，变色,或者根节点
else { //找兄弟借
//右倾情况 删除的在左边
if (node == leftOf(parentOf(node))) {
Node<K, V> brother = rightOf(parentOf(node));
if (colorOf(brother) == RED) { //这种情况 红黑树的兄弟并不是234树对应的兄弟，左旋
setColor(brother, BLACK);
setColor(parentOf(node), RED);
leftRotate(parentOf(node));
brother = rightOf(parentOf(node)); //其实就是之前的红色节点的左孩子
}
//然后找兄弟节点，兄弟节点有3种。1.兄弟节点是2节点单独一个黑色，无法接 2.为3节点，有一个可以借 3.4节点有2个可以借
//总结来说，34节点都可以借得到，借的过程其实就是相互顶替过程，包括颜色。所以分成2大类，兄弟能借，兄弟没得借
if (noChild(brother)) { //兄弟没得借
//兄弟没得借，那么大家一起损失，问题就变成待删除是父节点的情况。
// 父节点2种 1父节点是红色，直接变黑就行了，相当于补了一个黑色。为黑，那么就需要再一次循环
//方法一开始就进行了判断为红色情况，所以可以统一处理 这里记住并没有实际删除，删除是在外层操作的，这里是假设删除。
//所以整体删除的其实只有一个
setColor(brother, RED);
fixAfterDelete(parentOf(node));
} else { //兄弟34节点，可以借
//相互顶替过程，要保证顺序合法，旋转可以保证顺序，但是无法保证颜色。
// 相互顶替含义包含2个意思就是待删除-父节点-兄弟节点-兄弟子节点 ，a.颜色相互顶替 b.节点相互顶替
//左旋是 兄弟节点的左子树会挂在父节点的右孩子上 如果兄弟节点没有右孩子，那么兄弟节点称为父节点之后就没有右子树，然而我们是需要顶替之后还要保证黑色节点和原来一致，
//原来的兄弟节点是黑色节点，那么兄弟节点顶替父节点后，父节点顶替待删除的，兄弟的子节点必须要顶替兄弟节点，不然黑色节点达不到原来的分布情况，因此3节点兄弟节点需要做一次旋转
//兄弟节点的右孩子必须保证有，这样旋转变色之后，树的左右2边颜色又会恢复到原来状态
if (colorOf(rightOf(brother)) == BLACK) {
setColor(brother, RED);
setColor(leftOf(brother), BLACK);
rightRotate(brother);
brother = rightOf(parentOf(node));
}
//34节点可以一起处理了 待删除-父节点-兄弟节点-兄弟右子节点
setColor(brother, colorOf(parentOf(node)));
setColor(parentOf(node), BLACK);
setColor(rightOf(brother), BLACK);
leftRotate(parentOf(node));
}
} else { //左倾情况，删除的再右边,镜像操作
Node<K, V> brother = leftOf(parentOf(node));
if (colorOf(brother) == RED) { //找真正的兄弟
setColor(brother, BLACK);
setColor(parentOf(node), RED);
rightRotate(parentOf(node));
brother = leftOf(parentOf(node));
}
if (noChild(node)) {
setColor(brother, RED);
fixAfterDelete(parentOf(node));
} else {
if (colorOf(leftOf(brother)) == BLACK) {
setColor(brother, RED);
setColor(rightOf(brother), BLACK);
leftRotate(brother);
brother = leftOf(parentOf(node));
}
setColor(brother, colorOf(parentOf(node)));
setColor(parentOf(node), BLACK);
setColor(leftOf(brother), BLACK);
rightRotate(parentOf(node));
}
}
}
}
private boolean noChild(Node node) {
return colorOf(leftOf(node)) == BLACK && colorOf(rightOf(node)) == BLACK;
}
Node<K, V> successor(Node<K, V> node) {
if (node == null) {
return null;
}
//右边的最小值(最左边)
if (node.right != null) {
Node<K, V> tmp = node.right;
while (tmp.left != null) {
tmp = tmp.left;
}
return tmp;
} else {
//往上找 后继，找第一个父子关系是左关系的父亲,在删除中这里走不到，因为如果没有左右节点的删除，可以直接删，不需要找后继
Node<K, V> cur = node;
Node<K, V> p = node.parent;
while (p != null && cur == p.right) {
cur = p;
p = p.parent;
}
return p;
}
}
}
测试代码
package com.lsz.im.test;
import lombok.extern.slf4j.Slf4j;
import java.util.Scanner;
// -XX:+UseG1GC
@Slf4j
public class Test {
private String[] a;
Test(){
a=new String[1024*5];
int l=a.length;
}
public static void main(String[] args) {
RBTree<Integer,String> tree=new RBTree<>();
String next = null;
Scanner scanner=new Scanner(System.in);
System.out.println("开始插入,请输入");
while(true){
next = scanner.next();
if(next.equals("stop")){
break;
}
tree.put(Integer.valueOf(next),next);
tree.show();
}
System.out.println("开始删除,请输入");
while (true){
next = scanner.next();
if(next.equals("quit")) break;
tree.remove(Integer.valueOf(next));
tree.show();
}
}
// public void sayA() throws InterruptedException {
// System.out.println(Thread.currentThread().getName()+"---> A");
// Thread.sleep(1000);
// }
//
// public void sayB() throws InterruptedException {
// System.out.println(Thread.currentThread().getName()+"---> B");
//
// Thread.sleep(500);
// }
}
上一篇： PIL.Image.open与cv2.imread格式问题
下一篇： 判断二叉树树是否是平衡二叉树