# 红黑树
搞定红黑树，要先搞定二叉树、平衡树、2-3-4树，最后在研究红黑树
# 二叉查找树（BST）
# 定义
树的概念（作图讲解） 二叉树：每个子节点只有两个节点的树 二叉查找树（二叉搜索树）：就是一颗二叉树，他的左节点比父节点要小，右节点比父节点要大。他的 高度决定的查找效率。
# 常见操作
查找（红黑树通用）：查找每个节点我们从根节点开始查找
查找值比当前值大，则搜索右子树
查找值等于当前值，停止查找，返回当前节点
查找值比当前值小，则搜索左子树
插入：要插入节点，必须先找到插入节点位置。依然是从根节点开始比较，小于根节点的话就和左子树比较，反之与右子树比较，直到左子树为空或者右子树为空，则插入到相应为空的位置。 遍历（红黑树通用）：根据一定顺序来访问整个树，常见的有前序遍历，中序遍历（用的较多），后序遍历（记住规则的前提需要明白遍历规则均相对于跟节点）
- 前序遍历：根节点-》左子树-》右子树 4 213 657
- 中序遍历：左子树-》根节点-》右子树 123 4 567
- 后续遍历：左子树-》右子树-》根节点 132 576 4
查找最小值（红黑树通用）：沿着根节点的左子树一路查找，直到最后一个不为空的节点，该节点就是当前这个树的最小节点 查找最大值（红黑树通用）：沿着根节点的右子树一路查找，直到最后一个不为空的节点，该节点就是当前这个树的最大节点 查找前驱节点（红黑树通用）：小于当前节点的最大值 查找后继节点（红黑树通用）：大于当前节点的最小值 **删除：**本质上是找前驱或者后继节点来替代
- 叶子节点直接删除（没有前驱或后继节点）
- 只有一个子节点的用子节点替代（本质上就是找的前驱节点或者是后继节点，左节点就是前驱节点，右节点就是后继节点）
- 有两个子节点的，需要找到替代节点（替代节点就是前驱节点或者后继节点）
删除操作和红黑树一样，只不过红黑树多了着色和旋转过程
# BST存在的问题
BST存在的问题是，树在插入的时候会导致倾斜，不同的插入顺序会导致数的高度不一样，而树的高度直接影响了树的查找效率。最坏的情况所有的节点都在一条斜线上，这样树的高度为N。 基于BST存在的问题，平衡查找二叉树（Balanced BST）产生了。平衡树的插入和删除的时候，会通过旋转操作将高度保持在LogN。其中两款具有代表性的平衡术分别为AVL树（高度平衡树，具备二叉搜索树的全部特性，而且左右子树高度差不超过1）和红黑树。
AVL树如何实现平衡的？
通过左旋或者右旋 面试题：有了AVL树为什么还要红黑树呢？ AVL树由于实现比较复杂，而且插入和删除性能差，在实际环境下的应用不如红黑树。 红黑树的实际应用非常广泛，如Java中的HashMap和TreeSet，Java 8中HashMap的实现因为用RBTree代替链表（链表长度>8时），性能有所提升。
# 2-3-4树
# 定义
2-3-4树是四阶的 B树(Balance Tree)，他属于一种多路查找树，它的结构有以下限制：
所有叶子节点都拥有相同的深度。
节点只能是 2-节点、3-节点、4-节点之一。
- 2-节点：包含 1 个元素的节点，有 2 个子节点；
- 3-节点：包含 2 个元素的节点，有 3 个子节点；
- 4-节点：包含 3 个元素的节点，有 4 个子节点；
- 所有节点必须至少包含1个元素
元素始终保持排序顺序，整体上保持二叉查找树的性质，即父节点大于左子节点，小于右子节点；而且节点有多个元素时，每个元素必须大于它左边的和它的左子树中元素。
2-3-4树的查询操作像普通的二叉搜索树一样，非常简单，但由于其节点元素数不确定，在一些编程语言中实现起来并不方便，实现一般使用它的等同——红黑树。
# 对应红黑树
2-3-4树的每一个节点都对应红黑树的一种结构，所以每一棵 2-3-4树也都对应一棵红黑树，下图是 2-3-4树不同节点与红黑树子树的对应。
红黑树和 2-3-4树的节点添加和删除都有一个基本规则：避免子树高度变化，因为无论是 2-3-4树还是红黑树，一旦子树高度有变动，势必会影响其他子树进行调整，所以我们在插入和删除节点时尽量通过子树内部调整来达到平衡，2-3-4树实现平衡是通过节点的旋转和节点元素数变化，红黑树是通过节点旋转和变色。
# 节点插入
2-3-4树中节点添加需要遵守以下规则：
- 插入都是向最下面一层插入；
- 升元：将插入节点由 2-节点升级成 3-节点，或由 3-节点升级成 4-节点；
- 向 4-节点插入元素后，需要将中间元素提到父节点升元，原节点变成两个 2-节点，再把元素插入2-节点中，如果父节点也是 4-节点，则递归向上层升元，至到根节点后将树高加1；
而将这些规则对应到红黑树里，就是：
新插入的节点颜色为红色，这样才可能不会对红黑树的高度产生影响。
2-节点对应红黑树中的单个黑色节点，插入时直接成功（对应 2-节点升元）。
3-节点对应红黑树中的黑+红子树，插入后将其修复成 红+黑+红子树（对应 3-节点升元）；
4-节点对应红黑树中的红+黑+红子树，插入后将其修复成红色祖父+黑色父叔+红色孩子子树，然后再把祖父节点当成新插入的红色节点递归向上层修复，直至修复成功或遇到 root 节点；
公式：红黑树+新增一个节点（红色）=对等的2-3-4树+新增一个节点
# 删除节点
2-3-4树的删除可以全部转换为叶子节点的删除，删除原则是先看能不能和下面的叶子节点合并，能合并的直接合并完后删除，不能合并的就要找个元素替换上去，最终都是要保持平衡。
合并==》删除
合并==》替换==》删除
合并==》无法替换==》再合并==》删除
红色节点一定全部都在多元素节点中
红黑树的删除要比插入要复杂一些，我们还是类比 2-3-4树来讲：
- 查找最近的叶子结点中的元素替代被删除元素，删除替代元素后，从替代元素所处叶子结点开始处理；
- 降元：4-结点变 3-结点，3-结点变 2-结点；
- 2-结点中只有一个元素，所以借兄弟结点中的元素来补充删除后的造成的空结点；
- 当兄弟结点中也没有多个元素可以补充时，尝试将父结点降元，失败时向上递归，至到子树降元成功或到 root 结点树高减1；
将这些规则对应到红黑树中即：
查找离当前结点最近的叶子结点作为替代结点（左子树的最右结点或右子树的最左结点都能保证替换后保证二叉查找树的结点的排序性质，叶子结点的替代结点是自身）替换掉被删除结点，从替代的叶子结点向上递归修复；
替代结点颜色为红色（对应 2-3-4树中 4-结点或 3-结点）时删除子结点直接成功；
替代结点为黑色（对应 2-3-4树中 2-结点）时，意味着替代结点所在的子树会降一层，需要依次检验以下三项，以恢复子树高度：
兄弟结点的子结点中有红色结点（兄弟结点对应 3-结点或 4-结点）能够“借用”，旋转过来后修正颜色；
父结点是红色结点（父结点对应 3-结点或 4-结点，可以降元）时，将父结点变黑色，自身和兄弟结点变红色后删除；
父结点和兄弟结点都是黑色时，将子树降一层后把父结点当作替代结点递归向上处理。
如上图，删除的要点是 找到替代结点，如果替代结点是黑色，递归向上依次判断侄子结点、父结点是否可以补充被删除的黑色，整体思想就是将删除一个黑色结点造成的影响局限在子树内处理。
# 红黑树
# 定义
红黑树是一种结点带有颜色属性的二叉查找树，但它在二叉查找树之外，还有以下5大性质：
节点是红色或黑色。
根是黑色。
所有叶子都是黑色（叶子是NIL节点，这类节点不可以忽视，否则代码会看不懂）。
每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（黑色平衡）。
下图就是一个典型的红黑树：
# 常见操作
变色：节点的颜色由黑变红或者由红变黑 左旋：以某个节点作为旋转点，其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变。 右旋：以某个节点作为旋转点，其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变。
新增：分情况讨论，主要是要找到插入位置，然后自平衡（左旋或者右旋）且插入节点是红色（如果是黑色的话，那么当前分支上就会多出一个黑色节点出来，从而破坏了黑色平衡），以下分析全部以左子树为例子，右子树的情况则相反。
如果插入的是第一个节点（根节点），红色变黑色
如果父节点为黑色，则直接插入，不需要变色
如果父节点为红色，叔叔节点也是红色（此种情况爷爷节点一定是黑色），则父节点和叔叔节点变黑色，爷爷节点变红色（如果爷爷节点是根节点，则再变成黑色），爷爷节点此时需要递归（把爷爷节点当做新插入的节点再次进行比较）
如果父节点是红色，没有叔叔节点或者叔叔节点是黑色（此时只能是NIL节点），则以爷爷节点为支点右旋，旋转之后原来的爷爷节点变红色，原来的父节点变黑色。
右子树的情况和左子树类似，请自行研究，不再赘述。
删除（重点）：
三个原则：自己能搞定的自己搞定；搞不定的找兄弟和父亲帮忙；父亲和兄弟都帮不了那有福同享，有难同当（父亲和兄弟自损）
- 自己能搞定的自己搞定
- 如果删除的节点对应于2-3-4树的3节点或者4节点，则直接删除，不用跟兄弟和父亲借
- 如果删除的是红色节点，则直接删；如果删除的是黑色节点，则红色节点上来替代，变黑即可
- 搞不定的找兄弟和父亲帮忙
- 前提是找到“真正“的兄弟节点
- 兄弟节点有的借（此时兄弟节点一定是黑色，如果是红色那说明这个节点不是真正的兄弟节点，需要回到上一步找真正的兄弟节点）
- 兄弟节点有两个子节点的情况（2个子节点肯定是红色，如果是黑色的话相当于此时兄弟节点对应2-3-4树是2节点，不可能有多余的元素可以借），此时需要旋转变色
- 兄弟节点只有一个子节点的情况，此时需要旋转变色
- 兄弟和父亲节点帮不了忙，于是开始递归自损
- 前提是找到“真正”的兄弟节点
- 兄弟节点没有多余的元素可借（此时兄弟节点一定为黑色2节点），此时兄弟节点所在分支也要自损一个黑色节点以此达到黑色平衡，最快的方式就是兄弟节点直接变红（相当于就是减少一个黑色节点），此时一父节点为root的子树又达到了平衡（两边都比之前少一个黑色）。但是以祖父节点为root的树依然是不平衡的，此时需要递归处理
# 优势和用途
红黑树由于在插入和删除结点时都会进行变色旋转等操作，在符合红黑树条件的情况下，即使一边子树全是黑色结点，另一边子树全是红黑相间，两子树的高度差也不会超过一半。一棵有 n 个结点的红黑树高度至多为 2log(n+1) ，查找效率最坏为 O(log(n)) 。 所以红黑树常被用于需求查找效率稳定的场景，如 Linux 中内核使用它管理内存区域对象、Java8 中HashMap ，TreeMap的实现等，所以了解红黑树也很有意义。
# TALK IS CHEAP
public class RBTree<K extends Comparable<K>, V>{
private static final boolean RED = false;
private static final boolean BLACK = true;
private RBNode root;
private RBNode leftOf(RBNode node) {
return node == null ? null : node.left;
}
private RBNode rightOf(RBNode node) {
return node == null ? null : node.right;
}
private RBNode parentOf(RBNode node) {
return node == null ? null : node.parent;
}
private boolean colorOf(RBNode node) {
return node == null ? BLACK : node.color;
}
private void setColor(RBNode node, boolean color) {
if (node == null) {
return;
}
node.color = color;
}
public RBNode getRoot() {
return root;
}
public void setRoot(RBNode root) {
this.root = root;
}
/**
* 前驱节点获取
*/
private RBNode predecessor(RBNode node) {
if (node == null) {
return null;
}
// 从左子树中找到最大的节点
if (node.left != null) {
RBNode p = node.left;
while (p.right != null) {
p = p.right;
}
return p;
} else {
// 左子树为空的场景,需要向上寻找，于拐点停止（该场景在红黑树删除场景不会出现,仅为实现前驱节点算法）
RBNode p = node.parent;
while (p != null && node == p.left) {
node = node.parent;
p = p.parent;
}
return p;
}
}
/**
* 后继节点获取
*/
private RBNode sucessor(RBNode node) {
if (node == null) {
return null;
}
// 从左子树中找到最大的节点
if (node.right != null) {
RBNode p = node.right;
while (p.left != null) {
p = p.left;
}
return p;
} else {
// 右子树为空的场景,需要向上寻找，于拐点停止（该场景在红黑树删除场景不会出现,仅为实现后继节点算法）
RBNode p = node.parent;
while (p != null && node == p.right) {
node = node.parent;
p = p.parent;
}
return p;
}
}
/**
* 删除操作：
* 1.删除叶子节点，直接删除
* 2.删除的节点只有一个子节点，则用子节点替代
* 3.删除的节点有两个子节点，需要找到该节点的前驱或者后继节点替代
* 4.删除用来替代的节点，替代节点删除只有两种场景
* 4.1本身是叶子节点，直接删除即可
* 4.2自己有一个子节点，需要将自己删除，让自身的子节点替代自己
*/
public V remove(K key) {
RBNode node = getNode(key);
if (node == null) {
return null;
}
V oldValue = (V) node.value;
deleteNode(node);
return oldValue;
}
private void deleteNode(RBNode node) {
// 有两个字节点
if (node.left != null && node.right != null) {
// 找到前驱或者后继节点
final RBNode sucessor = sucessor(node);
node.key = sucessor.key;
node.value = sucessor.value;
node = sucessor;
}
// 此时回归到1和2的场景
RBNode replacement = node.left != null ? node.left : node.right;
// 自己的子节点代替自己
if (replacement != null) {
replacement.parent = node.parent;
if (node.parent == null) {
root = replacement;
} else {
// 需要知道自己原来是父节点的左还是右孩子
if (node == node.parent.left) {
node.parent.left = replacement;
} else {
node.parent.right = replacement;
}
}
// 双向指向均完成后，将node置为游离态
node.left = node.right = node.parent = null;
// 调整平衡
if (node.color == BLACK) {
fixAfterRemove(replacement);
}
} else if (node.parent == null) {
// 存在自己本身就是根节点的场景
root = null;
} else {
// 先调整在删除
if (node.color == BLACK) {
fixAfterRemove(node);
}
// 自己就是叶子节点，自己没有子节点,直接删除自己
RBNode p = node.parent;
if (p.left == node) {
p.left = null;
} else {
p.right = null;
}
node.parent = null;
}
}
/**
* 情况一：对应2-3-4的3、4节点，自我修复即可，删除红色，直接删除，删除黑色，子节点代替，并变为黑色
* 情况二：对应2-3-4的2节点删除，找兄弟借，兄弟可以借(兄弟不是2节点)
* 情况三：对应2-3-4的2节点删除，找兄弟借，兄弟没得借（兄弟是2节点）
*
* @param node 替换节点
*/
private void fixAfterRemove(RBNode node) {
while (node != root && colorOf(node) == BLACK) {
// 左孩子的情况
if (node == leftOf(parentOf(node))) {
RBNode bro = rightOf(parentOf(node));
// 找兄弟借的概念指的是2-3-4树的兄弟节点，当此时的兄弟节点是红色时，不是红黑树真正要找的兄弟节点，需要处理
if (colorOf(bro) == RED) {
setColor(bro, BLACK);
setColor(parentOf(node), RED);
leftRotate(parentOf(node));
bro = rightOf(parentOf(node));
}
// 情况三
if (colorOf(leftOf(bro)) == BLACK && colorOf(rightOf(bro)) == BLACK) {
setColor(bro, RED);
node = parentOf(node);
} else {
// 情况二: 两类：兄弟节点分别为3节点和4节点
if (colorOf(rightOf(bro)) == BLACK) {
setColor(leftOf(bro), BLACK);
setColor(bro, RED);
rightRotate(bro);
bro = rightOf(parentOf(node));
}
setColor(bro, colorOf(parentOf(node)));
setColor(parentOf(node), BLACK);
setColor(rightOf(bro),BLACK);
leftRotate(parentOf(node));
}
} else {
// 右孩子的情况
RBNode bro = leftOf(parentOf(node));
// 找兄弟借的概念指的是2-3-4树的兄弟节点，当此时的兄弟节点是红色时，不是红黑树真正要找的兄弟节点，需要处理
if (colorOf(bro) == RED) {
setColor(bro, BLACK);
setColor(parentOf(node), RED);
rightRotate(parentOf(node));
bro = leftOf(parentOf(node));
}
// 情况三
if (colorOf(leftOf(bro)) == BLACK && colorOf(rightOf(bro)) == BLACK) {
setColor(bro, RED);
node = parentOf(node);
} else {
// 情况二: 两类：兄弟节点分别为3节点和4节点
if (colorOf(leftOf(bro)) == BLACK) {
setColor(rightOf(bro), BLACK);
setColor(bro, RED);
leftRotate(bro);
bro = leftOf(parentOf(node));
}
setColor(bro, colorOf(parentOf(node)));
setColor(parentOf(node), BLACK);
setColor(leftOf(bro), BLACK);
rightRotate(parentOf(node));
}
}
}
// 情况一、替代节点是红色，则直接染黑，补偿删除的黑色节点，这样红黑树依然保持平衡
setColor(node, BLACK);
}
/**
* 查找对应的节点
*/
private RBNode getNode(K key) {
RBNode node = this.root;
while (node != null) {
final int cmp = node.key.compareTo(key);
if (cmp < 0) {
node = node.right;
} else if (cmp > 0) {
node = node.left;
} else {
return node;
}
}
return null;
}
/**
* 1.先确定插入点，小的往左，大的往右
* 2.修复变色及旋转
* 2.1 第一个节点进入，直接为跟节点，黑色，无需修复，结束
* 2.2 第二个节点进入，2-3-4树： 2节点变3节点 红黑树：基于一个黑节点变为上黑下红，因此变红即可，结束
* 2.3 多节点下进入，2-3-4树：3节点变4节点 红黑树：有5种情况
* （不调整） （右旋，变色） （先左旋，后右旋，变色） （左旋，变色） （先右旋，后左旋，变色）
* 黑 黑 黑 黑 黑
* / \ / / \ \
* 红 红 红 红 红 红
* / \ \ /
* 红 红 红 红
* 2.4 多节点下进入，2-3-4树：4节点+1节点，裂变 红黑树：有上黑下两红变为新增一个红色在子结点上，出现连续的红色，变色为由上倒下的红黑红，但当前节点可能为整个树中的一部分，需要持续向上变色，保证没有连续的红色
* @param key 键
* @param value 值
*/
public void put(K key, V value) {
RBNode node = this.root;
// 新增的为第一个节点(2.1场景)
if (node == null) {
this.root = new RBNode(key, value == null ? key : value, null);
return;
}
int cmp;
// 每次记录下来父节点，构造新节点时需要使用
RBNode parent;
do {
parent = node;
cmp = key.compareTo((K) node.key);
if (cmp > 0) {
node = node.right;
} else if (cmp < 0) {
node = node.left;
} else {
node.value = value == null ? key : value;
}
} while (node != null);
// 当node == null时，说明找到了插入点，只需知道最后一次cmp的大小即可判断放在左边还是右边
final RBNode<K, Object> newNode = new RBNode<>(key, value == null ? key : value, parent);
if (cmp > 0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
// 调整：颜色和旋转
fixAfterPut(newNode);
}
/**
* 2.修复变色及旋转
* 2.1 第一个节点进入，直接为跟节点，黑色，无需修复，结束
* 2.2 第二个节点进入，2-3-4树： 2节点变3节点 红黑树：基于一个黑节点变为上黑下红，因此变红即可，结束
* 2.3 多节点下进入，2-3-4树：3节点变4节点 红黑树：有5种情况
* （不调整） （右旋，变色） （先左旋，后右旋，变色） （左旋，变色） （先右旋，后左旋，变色）
* 黑 黑 黑 黑 黑
* / \ / / \ \
* 红 红 红 红 红 红
* / \ \ /
* 红 红 红 红
* 2.3.1 2.3.2 2.3.3 2.3.4 2.3.5
* 2.4 多节点下进入，2-3-4树：4节点+1节点，裂变 红黑树：有上黑下两红变为新增一个红色在子结点上，出现连续的红色，变色为由上倒下的红黑红，但当前节点可能为整个树中的一部分，需要持续向上变色，保证没有连续的红色
* 重要！！！以上场景发现规律，新增节点的父节点为黑色时一定无需处理
*/
private void fixAfterPut(RBNode<K, Object> node) {
// 新增节点，为红色,若为2.2场景，则此时已结束
node.color = RED;
while (node != null && node != root && node.parent.color == RED) {
// 父亲为爷爷的左节点
if (parentOf(node) == leftOf(parentOf(parentOf(node)))) {
// 取出叔叔节点，判断是否存在2.4场景
RBNode uncle = rightOf(parentOf(parentOf(node)));
if (colorOf(uncle) == RED) {
// 2.4场景 直接向上变色
setColor(parentOf(node), BLACK);
setColor(uncle, BLACK);
setColor(parentOf(parentOf(node)), RED);
// node指向爷爷节点，使其向上修正颜色
node = parentOf(parentOf(node));
} else {
// 叔叔节点不为红色则只可能是2.3.2 2.3.3中的场景
// 2.3.3
if (node == rightOf(parentOf(node))) {
// 先基于父节点左旋 使其变为2.3.2
node = parentOf(node);
leftRotate(node);
}
// 2.3.2 基于爷爷节点右旋，父亲变黑，爷爷变红
setColor(parentOf(node), BLACK);
setColor(parentOf(parentOf(node)), RED);
rightRotate(parentOf(parentOf(node)));
}
} else { // 父亲为爷爷的右节点
// 取出叔叔节点，判断是否存在2.4场景
RBNode uncle = leftOf(parentOf(parentOf(node)));
if (colorOf(uncle) == RED) {
// 2.4场景 直接向上变色
setColor(parentOf(node), BLACK);
setColor(uncle, BLACK);
setColor(parentOf(parentOf(node)), RED);
// node指向爷爷节点，使其向上修正颜色
node = parentOf(parentOf(node));
} else {
// 叔叔节点不为红色则只可能是2.3.4 2.3.5中的场景
// 2.3.5
if (node == leftOf(parentOf(node))) {
// 先基于父节点右旋 使其变为2.3.4
node = parentOf(node);
rightRotate(node);
}
// 2.3.2 基于爷爷节点左旋，父亲变黑，爷爷变红
setColor(parentOf(node), BLACK);
setColor(parentOf(parentOf(node)), RED);
leftRotate(parentOf(parentOf(node)));
}
}
}
// 最终将跟节点变为黑色
this.root.color = BLACK;
}
/**
* 围绕P左旋
* p pr
* / \ / \
* pl pr => p rr
* / \ / \
* rl rr pl rl
*/
private void leftRotate(RBNode p) {
if (p == null) {
return;
}
// pr
RBNode pr = p.right;
// p的右节点指向pr的左节点，即p的right指向rl
p.right = pr.left;
// rl成为p的右节点后，同样需要将rl的父节点指向p
if (pr.left != null) {
pr.left.parent = p;
}
// 取出p的父节点，将pr的父节点指向p原来的父节点，然后将pr的左节点指向p，最后将p的父节点指向pr
// p的父节点
RBNode parent = p.parent;
// pr的父节点指向p原来的父节点
// 为null则说明p为跟节点，将pr指定为根节点即可，并将其parent置为null
if (parent == null) {
this.root = pr;
pr.parent = null;
} else {
// p的父节点不为空，则需先搞清楚p是parent的左节点还是右节点
pr.parent = parent;
// 如果是左节点，则将parent的左节点指向pr
if (parent.left == p) {
parent.left = pr;
} else {
parent.right = pr;
}
}
// pr的左节点指向p
pr.left = p;
// p的父节点指向pr
p.parent = pr;
}
/**
* 围绕P左旋
* p pl
* / \ / \
* pl pr => rl p
* / \ / \
* rl rr rr pr
*/
private void rightRotate(RBNode p) {
if (p == null) {
return;
}
// pl
RBNode pl = p.left;
// p的左节点指向pl的右节点，即p的left指向rr
p.left = pl.right;
// rr成为p的左节点后，同样需要将rr的父节点指向p
if (pl.right != null) {
pl.right.parent = p;
}
// 取出p的父节点，将pl的父节点指向p原来的父节点，然后将pl的右节点指向p，最后将p的父节点指向pl
// p的父节点
RBNode parent = p.parent;
// pr的父节点指向p原来的父节点
// 为null则说明p为跟节点，将pr指定为根节点即可，并将其parent置为null
if (parent == null) {
this.root = pl;
pl.parent = null;
} else {
// p的父节点不为空，则将pl的父节点指向p的父节点
pl.parent = parent;
// 先搞清楚pl是parent的左节点还是右节点
// 如果是左节点，则将parent的左节点指向pr
if (parent.left == p) {
parent.left = pl;
} else {
parent.right = pl;
}
}
// pl的右节点指向p
pl.right = p;
// p的父节点指向pl
p.parent = pl;
}
static class RBNode<K extends Comparable<K>, V> {
private RBNode parent;
private RBNode left;
private RBNode right;
private boolean color;
private K key;
private V value;
public boolean isColor() {
return color;
}
public void setColor(boolean color) {
this.color = color;
}
public RBNode getLeft() {
return left;
}
public void setLeft(RBNode left) {
this.left = left;
}
public RBNode getRight() {
return right;
}
public void setRight(RBNode right) {
this.right = right;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
public RBNode() {
}
public RBNode(K key, V value, RBNode parent) {
this.parent = parent;
this.key = key;
this.value = value;
this.color = BLACK;
}
public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V value) {
this.parent = parent;
this.left = left;
this.right = right;
this.color = color;
this.key = key;
this.value = value;
}
}
public RBNode getROOT() {
return root;
}
public void setROOT(RBNode ROOT) {
this.root = ROOT;
}
}
找的打印红黑树的工具类
public class TreeOperation {
/*
树的结构示例：
1
/ \
2 3
/ \ / \
4 5 6 7
*/
// 用于获得树的层数
public static int getTreeDepth(RBTree.RBNode root) {
return root == null ? 0 : (1 + Math.max(getTreeDepth(root.getLeft()), getTreeDepth(root.getRight())));
}
private static void writeArray(RBTree.RBNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
// 保证输入的树不为空
if (currNode == null) return;
// 0、默认无色
// res[rowIndex][columnIndex] = String.valueOf(currNode.getValue());
//1、颜色表示
if(currNode.isColor()){//黑色，加色后错位比较明显
res[rowIndex][columnIndex] = ("\033[30;3m" + currNode.getValue()+"\033[0m") ;
}else {
res[rowIndex][columnIndex] = ("\033[31;3m" + currNode.getValue()+"\033[0m") ;
}
//2、R,B表示
// res[rowIndex][columnIndex] = String.valueOf(currNode.getValue()+"-"+(currNode.isColor()?"B":"R")+"");
// 计算当前位于树的第几层
int currLevel = ((rowIndex + 1) / 2);
// 若到了最后一层，则返回
if (currLevel == treeDepth) return;
// 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
int gap = treeDepth - currLevel - 1;
// 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
if (currNode.getLeft() != null) {
res[rowIndex + 1][columnIndex - gap] = "/";
writeArray(currNode.getLeft(), rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
}
// 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
if (currNode.getRight() != null) {
res[rowIndex + 1][columnIndex + gap] = "\\";
writeArray(currNode.getRight(), rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
}
}
public static void show(RBTree.RBNode root) {
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());
}
}
}
最后来个测试类
public class RBTreeTest {
public static void main(String[] args) {
//新增节点
insertOpt();
//删除节点
// deleteOpt();
}
/**
* 插入操作
*/
public static void insertOpt() {
Scanner scanner = new Scanner(System.in);
RBTree<String, Object> rbt = new RBTree<>();
while (true) {
System.out.println("请输入你要插入的节点:");
String key = scanner.next();
System.out.println();
//这里代码最多支持3位数，3位以上的话红黑树显示太错位了，这里就不重构代码了,大家可自行重构
if (key.length() == 1) {
key = "00" + key;
} else if (key.length() == 2) {
key = "0" + key;
}
rbt.put(key, null);
TreeOperation.show(rbt.getROOT());
}
}
/**
* 删除操作
*/
public static void deleteOpt(){
RBTree<String,Object> rbt=new RBTree<>();
//测试1：预先造10个节点（1-10）
// String keyA=null;
// for (int i = 1; i <11 ; i++) {
// if((i+"").length()==1){
// keyA="00"+i;
// }else if((i+"").length()==2){
// keyA="0"+i;
// }
// rbt.put(keyA,null);
// }
//测试2：包含2位数和3位数的测试代码 1 2 3 4 5 66 77 88 99 100 101
rbt.put("001",null);
rbt.put("002",null);
rbt.put("003",null);
rbt.put("004",null);
rbt.put("005",null);
rbt.put("066",null);
rbt.put("077",null);
rbt.put("088",null);
rbt.put("099",null);
rbt.put("100",null);
rbt.put("101",null);
TreeOperation.show(rbt.getRoot());
//以下开始删除
Scanner scanner=new Scanner(System.in);
while (true){
System.out.println("请输入你要删除的节点:");
String key=scanner.next();
System.out.println();
//这里代码最多支持3位数，3位以上的话红黑树显示太错位了，这里就不重构代码了,大家可自行重构
if(key.length()==1){
key="00"+key;
}else if(key.length()==2){
key="0"+key;
}
//1 2 3 88 66 77 100 5 4 101
// rbt.remove(key);
TreeOperation.show(rbt.getRoot());
}
}
}