【最详细图文讲解】❤ 彻底搞懂你 @红黑树
前提摘要：本文承接上文HashMap的红黑树的分析，这个部分单独讲这个红黑树的数据结构，使用自己写的Java代码以及图来演示红黑树平衡和变色的过程，不然直接看源码即使我写了注释你也看不懂（我就是这样踩坑学习的时候直接看源码，直接把我看晕了，所以不要纠结一定要看懂源码，你只要知道特性，自己可以实现才是真的get到了，这个时候在看源码可能就轻松了）。。
我看了很多文章，大多都是写完红黑树的插入操作，但是对于关于的红黑树的删除却很少讲的很详细的，然后红黑树的删除操作才是最复杂的地方。为了把复杂的东西讲的简单化不太容易，喵喵酱本人的理解写出来和你们读出来理解可能不太相同，代码逻辑是不变的，可以和代码一起理解，主要是为想要搞懂红黑树的小伙伴们一个思路哈。如果看完那你觉得博主真的在很认真写东西，呕心沥血的那种，就多多点赞收藏和加关注吧，俺真的需要你们的支持😭😭😭，不然肝不动了(๑′ᴗ‵๑)Ｉ Lᵒᵛᵉᵧₒᵤ❤。
认识红黑树
认识红黑树之前，必须认识区别二叉搜索树和平衡二叉树
二叉搜索树
二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树，它具有以下性质：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 左右子树也分别必须是二叉搜索树。
- 不会有重复的节点值。 例如：
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
二叉搜索树其缺点主要是其性能严重依赖于数据插入和删除的顺序。写如下所示： 插入顺序：3,2,4,5,6,7,8,23
3
/ \
2 4
\
5
\
6
\
7
\
8
\
23
在最坏的情况下，如果插入的数据已经排序，那么二叉搜索树会退化成一个链表，这种情况下所有操作的时间复杂度会变成线性的O(n)。为了解决这个问题，可以通过平衡二叉树(AVL树) 来保证树的平衡性，从而保证最坏情况下操作的时间复杂度为O(log n)。
平衡二叉树
二叉平衡树，通常指的是AVL树（Adelson-Velsky和Landis树），是一种特殊的二叉搜索树。AVL树得名于其发明者G. M. Adelson-Velsky和E. M. Landis，它是一种自平衡二叉搜索树。在AVL树中，任何节点的两个子树的高度最大差别为一，这意味着AVL树是高度平衡的。由于这样的平衡条件，AVL树确保了在插入、删除和查找操作中最坏情况下的时间复杂度都是O(log n)，其中n为树中节点的数量。 为了维护这个平衡条件，AVL树可能会在插入或删除节点后进行一些平衡操作，包括：
- 单旋转（左旋或右旋）
- 双旋转（左右旋或右左旋）
AVL树的平衡条件可以确保其性能，这个条件定义为每个节点的平衡因子（Balance Factor），它是该节点的左子树的高度减去右子树的高度。AVL树要求每个节点的平衡因子只能是1、0或-1,以下是一个简单的AVL树的例子，用“节点值(平衡因子)”表示每个节点：
(1)
4(0)
/ \
2(0) 6(0)
/ \ / \
1(0)3(0) 5(0)7(0)
(2)
5(0)
/ \
2(0) 6(-1)
/ \ \
1(0)3(0) 7(0)
（3）
5(1)
/ \
2(0) 6(0)
/ \
3(0)
平衡二叉树在每次插入和删除的时候会，校验一遍二叉树，如果有任何节点的平衡因子不为-1、0或1，相应的旋转操作将会被执行来恢复平衡状态。
红黑树
红黑树是一种自平衡的二叉搜索树，它在1972年由鲁道夫·贝尔发明。在二叉搜索树中，查找、插入和删除操作的时间复杂度在最坏的情况下可能会退化成线性时间（O(n)），如果树不平衡，即它可能变得非常偏斜。红黑树通过维持几个额外的属性来确保树大致保持平衡，这样操作的时间复杂度能够在最坏的情况下保持在O(log n)。 红黑树维持了以下性质：
- 节点颜色：每个节点要么是红色的，要么是黑色的。
- 根节点属性：红黑树的根节点是黑色的。
- 叶子节点属性：所有的叶子节点（叶子节点是指树结束的空（null）节点）都是黑色的。
- 红色节点属性：如果一个节点是红色的，那么它的两个子节点都是黑色的。换句话说，红色节点不能相邻，即所谓的“不能有两个连续的红色节点”。
- 黑色高度属性：从任一节点到其每个叶子节点的所有路径上的黑色节点数量相同。
例如：
7(黑)
/ \
3(红) 18(红)
/ \ / \
2(黑)4(黑)14(黑)
/
12(红)
当执行插入或删除操作时，如果违反了以上性质，红黑树就会通过旋转和重新着色等一系列操作来修复和维护上述性质，从而达到平衡。
红黑树与AVL树区别
红黑树（Red-Black Tree）和平衡二叉树（特指AVL树）都是自平衡的二叉搜索树数据结构，但它们如下的一些主要区别：
-
平衡条件 AVL树要求树中每个节点的左右子树高度差不能超过1。这个值称为平衡因子，可以是-1、0或1。红黑树按照颜色和特定的属性来维持平衡。
-
旋转操作 AVL树在插入和删除时为了保持平衡可能需要进行多达O(log n)次的旋转操作。红黑树的旋转操作通常较少，插入最多需要两次旋转，删除最多需要三次旋转。
-
查找性能 由于AVL树是更加严格平衡的，它提供更快的查找操作，对于查找密集型的应用更加适合
-
插入和删除性能 红黑树的插入和删除操作比AVL树更快，因为它们需要的旋转操作更少，因此对于插入和删除操作频繁的应用场合更合适，
-
内存占用 AVL树的节点通常存储额外信息（平衡因子），而红黑树的节点需要存储颜色信息（java中是boolean 一个字节）。通常来说，红黑树的内存占用率稍低。
红黑树的应用非常广泛，尤其是在那些需要快速查找操作的数据结构中，例如在Java的TreeMap 和 TreeSet 是Java中利用搜索树实现的 Map 和 Set，它们的底层是红黑树，而红黑树是一棵近似平衡的二叉搜索树。
红黑树的插入操作
首先如果是根节点root，直接设置黑色（red = false）,之后的每个节点默认为红色。如果此时的插入的节点的父节点为根节点，或者插入的节点的父节点为黑色，就非常幸运，不用任何变换。
然后就是父节点当前是红色的情况了。父节点当前是红色可以分为2两种情况，即父节点的父节点只有一个节点，父节点的父节点只有两个个节点，
后面简化说明把x指代当前插入的节点，xp为x的父节点，xpp为当前的xp的父节点。
父节点xp是红色，xpp的子节点只有xp是红色
这种情况如图所示：
此时又分可以分为4种情况：
- RL型：xp是xpp的右子节点，x是xp的左子节点
- RR型：xp是xpp的右子节点，x是xp的右子节点
- LL型：xp是xpp的左子节点，x是xp的左子节点
- RR型：xp是xpp的左子节点，x是xp的右子节点
RL型的旋转+变色：
LR型的旋转+变色和RL差不多：
RR型的变色+旋转：
LL型的变色+旋转和RR差不多：
父节点xp是红色，xpp的子节点有xppl和xppr两个子节点
此时这种情况可以如图所示：
这种情况将只进行变色操作，也可以叫颜色上溢过程
图中举例的情况，根节点和根节点的左右子节点都是黑色，但是此时依然满足红黑树特性：
- 节点颜色：每个节点要么是红色的，要么是黑色的。
- 根节点属性：红黑树的根节点是黑色的。
- 叶子节点属性：所有的叶子节点（叶子节点是指树结束的空（null）节点）都是黑色的。
- 红色节点属性：如果一个节点是红色的，那么它的两个子节点都是黑色的。换句话说，红色节点不能相邻，即所谓的“不能有两个连续的红色节点”。
- 黑色高度属性：从任一节点到其每个叶子节点的所有路径上的黑色节点数量相同。
即所有叶子结点到根节点的黑色节点数都是4。
红黑树的插入操作代码
public class RedBlackTree<K, V> {
private static final boolean RED = false;
private static final boolean BLACK = true;
static class Node<K, V> {
K key;
V value;
boolean color = BLACK;
Node<K, V> left;
Node<K, V> right;
Node<K, V> parent;
Node(K key, V value, Node<K, V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
private transient Node<K, V> root;
private Node<K, V> rotateLeft(Node<K, V> node) {
if (node == null || node.right == null) return node;
Node<K, V> r = node.right;
// 将r的左子树设为node的右子树
// 如果r的左子树不为空，将node设为r左子树的父亲
node.right = r.left;
if (r.left != null) r.left.parent = node;
// 将node的父亲设为r的父亲
r.parent = node.parent;
//如果node的父亲是null节点，则将r设为树的根节点
if (node.parent == null) root = r;
else if (node.parent.left == node) node.parent.left = r;// 如果node是它父节点的左子节点，则将r设为node的父节点的左子节点
else node.parent.right = r;// 如果node是它父节点的右子节点，则将r设为node的父节点的右子节点
r.left = node; // 将node设为r的左子节点
node.parent = r; // 将node的父节点设为r
return r;
}
private Node<K, V> rotateRight(Node<K, V> node) {
if (node == null || node.left == null) return node;
Node<K, V> l = node.left;
// 将l的右子树设为node的左子树
// 如果l的右子树不为空，将mode设为l右子树的父亲
node.left = l.right;
if (l.right != null) l.right.parent = node;
// 将node的父亲设为l的父亲
l.parent = node.parent;
if (node.parent == null) root = l;// 如果node的父亲是null节点，则将l设为树的根节点
else if (node.parent.right == node) node.parent.right = l;// 如果node是它父节点的右子节点，则将l设为node的父节点的右子节点
else node.parent.left = l;// 如果node是它父节点的左子节点，则将l设为node的父节点的左子节点
l.right = node; // 将node设为“l的右子节点”
node.parent = l; // 将“node的父节点”设为“l”
return l;
}
private void fixAfterInsertion(Node<K, V> x) {
x.color = RED;
while (x != null && x != root && x.parent.color == RED) {
//若“父节点xp”是“祖父节点xpp的左孩子”
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//祖父节点xpp的右孩子，即父节点的兄弟节点
Node<K, V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {//while颜色上溢(父节点xp是红色，xpp的子节点有xppl和xppr两个子节点 也是红色)
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
//父节点的兄弟节点不是红色，即（为黑色或为空 null节点也算一个子节点）
if (x == rightOf(parentOf(x))) {//LR型
x = parentOf(x);
rotateLeft(x);
}
//LL型
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
//祖父节点xpp的左孩子，
Node<K, V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {//即父节点的兄弟节点也是红色 while颜色上溢 （同上）
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {//RL型
x = parentOf(x);
rotateRight(x);
}
//RR型
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK; //根节点强制黑色
}
// 插入操作
public void insert(K key, V value) {
Node<K, V> t = root;
if (t == null) {
root = new Node<>(key, value, null);
fixAfterInsertion(root);
return;
}
int cmp;
Node<K, V> parent;
// 下面的比较操作假设我们可以比较K类型的键，实际上，我们可能需要提供一个Comparator来完成比较
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else {
t.value = value;
return;
}
} while (t != null);
Node<K, V> e = new Node<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
}
private static <K, V> boolean colorOf(Node<K, V> p) {
return (p == null ? BLACK : p.color);
}
private static <K, V> Node<K, V> parentOf(Node<K, V> p) {
return (p == null ? null : p.parent);
}
private static <K, V> Node<K, V> leftOf(Node<K, V> p) {
return (p == null) ? null : p.left;
}
private static <K, V> Node<K, V> rightOf(Node<K, V> p) {
return (p == null) ? null : p.right;
}
private static <K, V> void setColor(Node<K, V> p, boolean c) {
if (p != null) p.color = c;
}
}
红黑树的删除操作
删除操作比较复杂，特别是左旋和右旋，删除替换，以及变色的过程。首先我们搞明白两个点。
理解左旋和右旋
首先左旋我们举例说明：
- 左旋： 在执行左旋X节点时，节点X的右子节点(XR)将会变成自己X节点的父节点，而XR的的左子节点，将会变成X的右子节点。
- 右旋： 在执行右旋X节点时，节点X的左子节点(XL)将会变成自己X节点的父节点，而XL的的右子节点，将会变成X的左子节点。
左旋和右旋在上面添加方法中有详细的注释说明，代码部分不再累述
理解替换和删除
当被删除的节点，左右子节点都不为空，那么可以先执行与自己的后继节点直接替换。如果只有一个左子节点或者右子节点，那么和子节点替换。最终删除替换节点。如果没有子节点，则直接删除。
如图所示，如果要删除 23 节点，左右子节点不为空，寻找后继节点，后继节点为右节点的最末尾的左子节点。那么后继节点为 24。 此时可以将24替换为23 也就是根节点，然后转为删除 24 这个节点。 如果要删除 20 这个节点，左右子节点不为空，寻找后继节点。后继节点为 21。先执行与20 替换，最后删除节点转为 21节点。 如果要删除 27节点，由于只有左子节点，直接使用子节点子节点替换，删除节点转为24。
删除操作
在执行完节点替换，确定最终需要删除的节点的时候，此时红黑树的删除操作有两种情况：
删除红节点
执行完节点替换以后，删除红节点很简单，直接删除。不需要做变换修正平衡。
删除黑色节点
删除黑色节点分为以下几种情况
- 删除黑色节点为根节点，说明是空树了，直接删除
- 如果删除黑色节点没有子节点，那么先修正红黑树，然后将节点删除：
-
情况一：删除节点的兄弟节点为红色（此时父节点为黑色）
此时兄弟节点有两个子节点为黑色（如果只有一个黑色子节点，违背红黑树不考虑），对兄弟节点变成黑色，父节点变成红色，对父节点右旋。然后此时待删除节点的兄弟节点为黑色，并且兄弟节点的两个子节点为黑色（null节点），直接情况二处理，如下情况二。
-
情况二：删除节点的兄弟节点子节点都为黑色（包括null节点）
-
情况三：删除节点的兄弟节点为黑色（此时父节点可以为红色或者黑色），兄弟节点有一个右子节点为红色，左子节点为黑（包括null节点），执行对兄弟节点左旋，变色，然后执行父节点的右旋变色。
-
情况四：删除节点的兄弟节点为黑色（此时父节点可以为红色或者黑色），兄弟节点有一个左子节点为红色，右子节点为黑（包括null节点），执行父节点右旋，然后变色。
情况三和情况四如图（图中省略右子树）父节点可以为红色的情况，要删掉节点21，他的父节点为红色，兄弟节点为黑色，并且兄弟节点有子节点的情况（图中删除节点为右节点，如果为左边节点，同理操作。）：
如果兄弟节点有两个子节点为红色，类似有一个左子节点为红色情况，直接执行父节点右旋，然后变色。
如果父节点可以为黑色的情况，操作同理，如图所示。 
上面图中的例子都是删除节点为右边节点，左边节点操作 除了变换操作相反操作，其他都是相同的。
-
- 如果删除黑色节点有子节点，那么先删除，将删除节点的子节点对应做修正。
图中示例，删除23节点，后继节点 24，24节点为删除节点，但是有子节点25，24节点先删除，然后节点25占位，继续对25节点修正，后面不再删除，对节点 25修正，即父节点28 左旋，变色。
删除操作代码实现
public class RedBlackTree {
/**
* 查找给定节点的后继节点，即中序遍历中的下一个节点。
*
* @param t 要查找其后继节点的节点。
* @return 给定节点的后继节点，如果不存在则返回 null。
*/
private Node<K, V> successor(Node<K, V> t) {
if (t == null) {// 如果传入的节点为空，则没有后继节点，直接返回 null
return null;
} else if (t.right != null) {// 如果给定节点有右子树，则后继节点在右子树中
// 从右子节点开始往左下寻找，直到找到最左边的节点，它将是后继节点
Node<K, V> p = t.right;
while (p.left != null) {
// 继续沿左子节点向下
p = p.left;
}
return p; // 找到后继节点并返回它
} else {// 如果给定节点没有右子树，则向上查找其祖先节点，直至找到一个是其祖先的左子节点的节点
// 初始设置当前节点为给定节点，父节点为给定节点的父节点
Node<K, V> p = t.parent;
Node<K, V> ch = t;
// 向上遍历父节点直到找到不是其父节点右子节点的节点
// 这意味着我们在中序遍历中向上遍历并找到了一个左转的地方，那个父节点即为后继节点
while (p != null && ch == p.right) {
ch = p; // 把父节点赋值给当前节点
p = p.parent; // 把祖父节点赋值给父节点，向上遍历
}
return p; // 找到后继节点并返回它
}
}
/**
* 删除节点后修复红黑树的性质。
*
* @param x 是删除节点或移动到树内部的子节点，它可能违背了红黑树的性质。
*/
private void fixAfterDeletion(Node<K, V> x) {
// 只要x不是新的根，也不是红色（一个红色节点在这里意味着树仍然是平衡的，不需要处理）
// 黑色并且不是根节点需要循环修复。
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) { // 如果x是左子节点。
// 设置兄弟节点w。
Node<K, V> w = rightOf(parentOf(x));
// 第一种情况：x的兄弟节点w是红色的。
if (colorOf(w) == RED) {
setColor(w, BLACK); // 将兄弟节点设为黑色。
setColor(parentOf(x), RED); // 将x的父节点设为红色。
rotateLeft(parentOf(x)); // 对x的父节点执行左旋。
w = rightOf(parentOf(x)); // 重新设置x的兄弟节点。
}
// 第二种情况：x的兄弟节点w是黑色的，并且w的两个子节点都是黑色的。
if (colorOf(leftOf(w)) == BLACK &&
colorOf(rightOf(w)) == BLACK) {
setColor(w, RED); // 将兄弟节点设为红色。
x = parentOf(x); // 把x向上移动到它的父节点。
} else {
// 第三种情况：x的兄弟节点w是黑色的，w的左子节点是红色，右子节点是黑色。
if (colorOf(rightOf(w)) == BLACK) {
setColor(leftOf(w), BLACK); // 将w的左子节点设为黑色。
setColor(w, RED); // 将w设为红色。
rotateRight(w); // 对w执行右旋。
w = rightOf(parentOf(x)); // 重新设置x的兄弟节点。
}
// 第四种情况：x的兄弟节点w是黑色的，并且w的右子节点是红色的，左子节点是任意颜色。
setColor(w, colorOf(parentOf(x))); // 将w的颜色设置为x父节点的颜色。
setColor(parentOf(x), BLACK); // 将x的父节点设为黑色。
setColor(rightOf(w), BLACK); // 将w的右子节点设为黑色。
rotateLeft(parentOf(x)); // 对x的父节点执行左旋。
x = root; // 完成操作，设置x为根，结束循环。
}
} else { // 如果x是右子节点
// 设置兄弟节点w为x的左兄弟。
Node<K, V> w = leftOf(parentOf(x));
// 第一种情况：x的兄弟节点w是红色的。
if (colorOf(w) == RED) {
setColor(w, BLACK); // 将w设为黑色
setColor(parentOf(x), RED); // 将x的父节点设为红色
rotateRight(parentOf(x));// 对x的父节点进行右旋
w = leftOf(parentOf(x)); // 重新设置x的兄弟节点
}
// 第二种情况：x的兄弟节点w是黑色的，并且w的两个子节点都是黑色的。
if (colorOf(rightOf(w)) == BLACK &&
colorOf(leftOf(w)) == BLACK) {
setColor(w, RED); // 将w设为红色
x = parentOf(x); // 把x向上移动到它的父节点
} else {
// 第三种情况：x的兄弟节点w是黑色的，w的右子节点是红色，左子节点是黑色。
if (colorOf(leftOf(w)) == BLACK) {
setColor(rightOf(w), BLACK); // 将w的右子节点设置为黑色
setColor(w, RED); // 将w设为红色
rotateLeft(w); // 对w进行左旋
w = leftOf(parentOf(x)); // 重新设置x的兄弟节点
}
// 第四种情况：x的兄弟节点w是黑色的，并且w的左子节点是红色的，右子节点是任意颜色。
setColor(w, colorOf(parentOf(x))); // 将w的颜色设置为x父节点的颜色
setColor(parentOf(x), BLACK); // 将x的父节点设置为黑色
setColor(leftOf(w), BLACK); // 将w的左子节点设置为黑色
rotateRight(parentOf(x)); // 对x的父节点进行右旋
x = root; // 完成操作，设置x为根，结束循环
}
}
}
// 最后，我们将x节点设为黑色以恢复红黑树的性质。
setColor(x, BLACK);
}
/**
* 删除红黑树中的指定节点。
*
* @param p 要删除的节点。
*/
private void deleteNode(Node<K, V> p) {
// 删除操作实际上分成了两个阶段：
// 1. 如果节点p最多有一个子节点，直接删除；
// 2. 如果节点p有两个子节点，找到它的后继，交换两者的位置，然后删除p（此时p最多有一个子节点）。
// 如果p有两个子节点，找出它的后继节点并交换。
if (p.left != null && p.right != null) {
Node<K, V> s = successor(p);
// 交换p与它后继节点中的关键信息，相当于将后继节点的值搬到了当前节点，
// 而实际上稍后会删除的是物理上的后继节点。
p.key = s.key;
p.value = s.value;
p = s; // 现在p指向了后继节点，可以继续删除操作。
}
// 现在p最多只有一个子节点。
// 用replacement指向p的非空子节点, 如果两个子节点都是空的，replacement也将是null。
Node<K, V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// 如果p有一个子节点，直接用其子节点来替换p。
replacement.parent = p.parent;
if (p.parent == null) {
// 如果p是根节点，直接用replacement成为新的根。
root = replacement;
} else if (p == p.parent.left) {
// 如果p是一个左子节点，将父节点的对应指针指向replacement。
p.parent.left = replacement;
} else {
// p是一个右子节点，同样操作。
p.parent.right = replacement;
}
// 删除p,将p的左右子节点指向null, 以便清除连接并确保无法通过其他路径访问。
p.left = p.right = p.parent = null;
// 如果被删除的节点是黑色的，我们需要修复可能出现的红黑树属性破坏的情况。
// replacement必须是红色，所以我们只改变它的颜色为黑色来补充失去的黑色节点。
if (p.color == BLACK) {
fixAfterDeletion(replacement);
}
} else if (p.parent == null) {
// 所有的情况都处理了，但如果p是root，并且它没有子节点，这意味着树现在是空的。
root = null;
} else {
// 这种情况下，p没有子节点并且不是根节点（即本身是一个子节点）；
// 如果p是黑色，我们需要修复因为节点删除导致的潜在破坏。
if (p.color == BLACK) {
fixAfterDeletion(p);
}
//如果是红色，不做处理，直接删除
// 现在我们可以删除p；如果p是左子节点，则相应地清除父节点中的指针。
if (p.parent != null) {
if (p == p.parent.left) {
p.parent.left = null;
} else if (p == p.parent.right) {
p.parent.right = null;
}
p.parent = null; // 清除p的父链接。
}
}
}
public void deleteNode(K key) {
Node<K, V> p = root;
// 下面的比较操作假设我们可以比较K类型的键，实际上我们可能需要提供一个Comparator来完成比较
Comparable<? super K> k = (Comparable<? super K>) key;
int cmp;
while (p != null) {
cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
break;
}
if (p == null)
return; // 没有找到要删除的节点
deleteNode(p);
}
}
最后
本文主要讲了红黑树的插入操作和删除操作，对于其他方法，比如查找，遍历（中序，后序，前序）这个和搜索二叉树差不多，我相信大多数都知道我就不写了。学习是一个快乐的过程，每次豁然开朗的感觉，你的灵魂都在发光，也许这也是生命的重要意义之一吧（喵喵酱有感而发O(∩_∩)O哈哈~）
转载自:https://juejin.cn/post/7352140828662824960