一、概述
红黑树是一种自平衡二叉查找树，最早由一位名叫Rudolf Bayer的德国计算机科学家于1972年发明。然而，最初的树形结构不是现在的红黑树，而是一种称为B树的结构，它是一种多叉树，可用于在磁盘上存储大量数据。
在1980年代早期，计算机科学家Leonard Adleman和Daniel Sleator推广了红黑树，并证明了它的自平衡性和高效性。从那时起，红黑树成为了最流行的自平衡二叉查找树之一，并被广泛应用于许多领域，如编译器、操作系统、数据库等。
红黑树的名字来源于红色节点和黑色节点的交替出现，它们的颜色是用来维护树的平衡性的关键。它们的颜色具有特殊的意义：
- 黑色节点代表普通节点，
- 红色节点代表一个新添加的节点，
它们必须满足一些特定的规则才能维持树的平衡性。
红黑树也是一种自平衡的二叉搜索树，较之 AVL，插入和删除时旋转次数更少
二、红黑树的特性
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 所有叶子节点（NIL节点）都是黑色。这些叶子节点通常表示空节点或没有实际存储值的节点。
- 红色节点不能相连：如果一个节点是红色，它的两个子节点必须是黑色。
- 黑色完美平衡：从任何节点到其所有后代叶子节点的简单路径上，必须包含相同数量的黑色节点。这个属性确保了红黑树的平衡性，避免了树变得过高。
三、实现红黑树
3.1 节点定义
public class RedBlackTree {
/**
* 根节点
*/
private Node root;
/**
* 颜色枚举
*/
enum Color {
RED, BLACK;
}
private static class Node {
int key;
Object value;
Node left;
Node right;
// 父节点
Node parent;
// 颜色 默认为红色
Color color = Color.RED;
/**
* 判断节点是否是左孩子
*
* @return
*/
boolean isLeftChild() {
return parent != null && this == parent.left;
}
/**
* 获取当前节点的叔叔：爸爸的兄弟（前提必须有爷爷存在）
*
* @return
*/
Node getUncle() {
if (parent == null || parent.parent == null) {
return null;
}
// 如果当前节点的父亲是属于左孩子,那么爷爷的右孩子就是叔叔
if (parent == parent.parent.left) {
return parent.parent.right;
} else {
return parent.parent.left;
}
}
/**
* 获取当前节点的兄弟
*
* @return
*/
Node getBrother() {
if (parent == null) {
return null;
}
// 当前节点是属于左孩子，那么父亲的右孩子就是兄弟
if (this.isLeftChild()) {
return parent.right;
} else {
return parent.left;
}
}
}
}
判断节点颜色:
/**
* 判断节点是否是红色
*
* @param node
* @return
*/
boolean isRed(Node node) {
return node != null && node.color == Color.RED;
}
/**
* 判断节点是否是黑色
* @param node
* @return
*/
boolean isBlack(Node node) {
return !isRed(node);
//return node == null || node.color == Color.BLACK;
}
3.2 左右旋代码
这里的思路与AVL树的相同，只是多了parent属性要维护，所以对每一个移动了的节点，都需要更新parent属性。（关于AVL树旋转的详细逻辑可以看我上一篇文章）
右旋：
/**
* 右旋：
* 1.旋转本身的逻辑：失衡节点左孩子上位 ，处理失衡节点的后事
* 2.处理 待处理后事节点，上位节点，失衡节点 的父亲
* 3.处理旋转节点父亲的孩子
* @param node 失衡的节点
*/
private void rightRotate(Node node) {
// 失衡的节点 node
// 失衡节点的左孩子：要上位的节点
Node upNode = node.left;
// 待处理的上位节点的后代：上位节点的右孩子
Node toChangeParent = upNode.right;
// 1.正常的右旋处理：
// 1.1上位
upNode.right = node;
// 1.2处理后事
node.left = toChangeParent;
// 2.更新相关移动节点的父亲
// 2.1 更新上位节点后代的父亲 为 要失衡的节点
if (toChangeParent != null) {
toChangeParent.parent = node;
}
// 2.2 更新上位节点的父亲：为 失衡节点的父亲
upNode.parent = node.parent;
// 2.3 更新失衡节点的父亲
node.parent = upNode;
// 3.处理上位节点父亲的孩子（因为是双向的，步骤二只处理了节点的父亲，针对父亲还要更新父亲的孩子）
// 判断旋转节点原本是属于左还是还是右孩子
if (node.parent == null) {
// 只需要把上位节点更新为根节点
root = upNode;
}
// 旋转节点原本是属于左孩子
else if (node.parent.left == node) {
node.parent.left = upNode;
}
// 旋转节点原本是属于右孩子
else {
node.parent.right = upNode;
}
}
左旋：
/**
* 左旋：
* 1.旋转本身的逻辑：失衡节点右孩子上位 ，处理失衡节点的后事
* 2.处理 待处理后事节点，上位节点，失衡节点 的父亲
* 3.处理失衡节点父亲的孩子
* @param node 失衡的节点
*/
private void leftRotate(Node node) {
// 失衡节点node
// 上位节点:失衡节点的右孩子
Node upNode = node.right;
// 待处理后事的节点：上位节点的左孩子
Node toChangeParent = upNode.left;
// 1.正常的左旋处理
// 1.1 节点上位
upNode.left = node;
// 1.2 处理后事: 后代toChangeParent父亲更换为原本的失衡节点
node.right = toChangeParent;
// 2. 更新相关移动节点的父亲
// 2.1 上位节点后代toChangeParent的父亲 更新为：失衡的节点
if (toChangeParent != null) {
toChangeParent.parent = node;
}
// 2.2 更新上位节点的父亲 为 失衡节点的父亲
upNode.parent = node.parent;
// 2.3 更新失衡节点的父亲 为 上位节点
node.parent = upNode;
// 3.处理失衡节点的父亲的孩子
// 如果失衡节点原本是根节点
if (node.parent == null) {
root = upNode;
}
// 失衡节点原本是属于左孩子
else if (node.parent.left == node) {
node.parent.left = upNode;
} else {
node.parent.right = upNode;
}
}
3.3 插入
假设插入的节点为红色，一共包含以下四种情况：
1.插入节点为根节点
将根节点变黑
2.插入节点的父亲为黑色
树的红黑性质不变，无需调整
3.插入节点的父亲和叔叔都为红色
此种情况只需要变色：
- 父亲变为黑色（此时违反了黑色平衡），为了保证黑色平衡，连带的叔叔也变为黑色。
- 此时当前路径多了一个黑色，其他路径没有多的黑色，所以需要在当前路径中再减少黑色：爷爷变成红色。
- 爷爷变成红色，可能又会接着触发红红相邻，因此对将爷爷进行递归调整，最后根节点需要变黑
在下图的情况下插入1：
插入1.png
树的变色过程：
第一轮：对于插入节点来说：父亲和叔叔变黑，爷爷变红；
第二轮：对于爷爷来说：爷爷的父亲和爷爷的叔叔变黑，爷爷的爷爷变红；（与第一步相同，直接递归）
最后爷爷的爷爷是根节点，所以变黑
红黑树插入.gif
总结：父亲和叔叔变黑，爷爷变红，递归变化直到根节点，最后根节点变为黑色
4.插入节点的父亲为红色，叔叔为黑色
此种情况需要变色+旋转：
-
①父亲为左孩子，插入节点也是左孩子，此时即 LL 不平衡
- 让父亲变黑，为了保证这颗子树黑色不变，将爷爷变成红，但叔叔子树少了一个黑色
-
爷爷右旋，补齐一个黑色给叔叔，父亲旋转上去取代爷爷，由于它是黑色，不会再次触发红红相邻
image.png
-
②父亲为左孩子，插入节点是右孩子，此时即 LR 不平衡
-
父亲左旋，变成 LL 情况，按 1. 来后续处理
image.png
-
-
③父亲为右孩子，插入节点也是右孩子，此时即 RR 不平衡
- 让父亲变黑，为了保证这颗子树黑色不变，将爷爷变成红，但叔叔子树少了一个黑色
-
爷爷左旋，补齐一个黑色给叔叔，父亲旋转上去取代爷爷，由于它是黑色，不会再次触发红红相邻
image.png
-
④父亲为右孩子，插入节点是左孩子，此时即 RL 不平衡
-
父亲右旋，变成 RR 情况，按 3. 来后续处理
image.png
-
插入方法：寻找位置插入：
/**
* 插入/更新节点
* @param key
* @param value
*/
public void put(int key,Object value) {
// 找到插入的位置
Node pointer = root;
// 插入位置的父亲
Node parent = null;
while (pointer != null) {
parent = pointer;
if (key < pointer.key) {
// 往左找
pointer = pointer.left;
} else if (key > pointer.key) {
// 往右找
pointer = pointer.right;
} else {
// 找到了 直接更新值
pointer.value = value;
return;
}
}
// 没有找到，当前指针pointer指向的是要插入的位置
Node added = new Node(key, value);
// 树为空，新增节点作为根节点
if (parent == null) {
root = added;
} else if (key < parent.key) {
// 新增节点作为左孩子
parent.left = added;
// 设置新增节点的父亲
added.parent = parent;
} else {
// 新增节点作为右孩子
parent.right = added;
added.parent = parent;
}
// 插入结束后，不平衡的情况下需要对树进行旋转和变色
fixRedRed(added);
}
在插入了节点之后，树失衡，对树进行旋转变色方法：
/**
* 当出现两个相邻红色节点的时候对树的调整
* 1.插入的是根节点直接变黑
* 2.插入节点的父亲就是黑色，无需做任何操作
* 3.插入节点的父亲是红色，本身也是红色，触发红红相连
* - 叔叔是红色：父亲和叔叔一起变红，爷爷变黑；递归直到根节点
* - 叔叔是黑色：此种情况，因为变色时叔叔跟父亲颜色不同，所以变色做不到平衡，需要旋转
* - 父亲是左孩子，插入节点也是左孩子 LL
* - 父亲是左孩子，插入节点是右孩子 LR
* - 父亲是右孩子，插入节点是右孩子 RR
* - 父亲是右孩子，插入节点是左孩子 RL
*/
public void fixRedRed(Node node) {
// 1.插入的是根节点直接变黑
if (node == root) {
node.color = Color.BLACK;
return;
}
// 2.插入节点的父亲就是黑色，无需做任何操作
else if (isBlack(node.parent)) {
return;
}
//3. 父亲和叔叔都是红色
// 代码执行到这里 父亲一定是红色
// 父亲
Node parent = node.parent;
// 叔叔
Node uncle = node.getUncle();
// 爷爷
Node grandpa = parent.parent;
// 叔叔是红色（此时父亲是红色）：
if (isRed(uncle)) {
// 父亲和叔叔变黑 （路径多了黑，所以爷爷要变红）
parent.color = Color.BLACK;
uncle.color = Color.BLACK;
// 爷爷变红 （又可能触发红红相连）
grandpa.color = Color.RED;
// 递归执行
fixRedRed(grandpa);
}
// 叔叔是黑色（此时父亲是红色）叔叔和父亲颜色不同，通过变色做不到平衡，需要旋转
// 父亲是左孩子，插入节点也是左孩子 LL不平衡
if (parent.isLeftChild() && node.isLeftChild()) {
// 1.变色：父亲变黑，爷爷变红
parent.color = Color.BLACK;
grandpa.color = Color.RED;
// 2.右旋：爷爷右旋
rightRotate(grandpa);
}
// 父亲是左孩子，插入节点是右孩子 LR不平衡
else if (parent.isLeftChild() && !node.isLeftChild()) {
// 1.父亲左旋 变成了LL
leftRotate(parent);
// LL:变色+旋转
// 变色：父亲变黑（在父亲左旋之后，此时父亲是插入的节点），爷爷变红
node.color = Color.BLACK;
grandpa.color = Color.RED;
rightRotate(grandpa);
}
// 父亲是右孩子，插入节点也是右孩子 RR不平衡
else if (!parent.isLeftChild() && !node.isLeftChild()) {
// 1.变色：父亲变黑，爷爷变红
parent.color = Color.BLACK;
grandpa.color = Color.RED;
// 2.爷爷左旋
leftRotate(grandpa);
}
// 父亲是右孩子，插入节点是左孩子，RL不平衡
else {
// 父亲右旋，变成RR场景 此时父亲变成了node
rightRotate(parent);
// 1.变色：父亲变黑，爷爷变红
node.color = Color.BLACK;
grandpa.color = Color.RED;
// 2.旋转：爷爷左旋
leftRotate(grandpa);
}
}
平衡的过程就是变色+旋转
3.4 删除
1.删除节点没有孩子
- 删除的节点就是根节点：直接删除
- 删除的节点不是根节点：直接把删除节点的父亲的孩子置空，删除节点的父亲也置空（有助于垃圾回收）
2.删除节点有一个孩子
- 删除的节点是根节点：
- 这个孩子一定是红色（如果是黑色的话就不平衡了）。
- 剩余节点和根节点的 key，value交换，再把根节点孩子设置为null，颜色保持黑色不变
- 这个孩子一定是红色（如果是黑色的话就不平衡了）。
- 删除的节点不是根节点：让删除节点的父亲指向删剩下的节点（向下的指针），删剩下的父亲指向删除节点的父亲（向上的指针）；本身删除节点的左右孩子和父亲置空（垃圾回收）
3.删除节点有两个孩子
想办法把两个孩子转变成情况二的一个孩子：
交换删除节点和后继节点的 key，value，这样就转变成了情况二，递归删除后继节点，直到该节点没有孩子或只剩一个孩子。
失衡情况：
删黑色节点需要考虑平衡，删红色不需要：
- 红色是叶子节点，不会失衡
- 红色是非叶子节点，他会有两个孩子，针对两个孩子的情况，都会被转换为只有一个孩子的情况，通过交换，进入上面的删除情况二中。
失衡情况一：
删的黑色节点，剩下的是一个红色节点：
- 删了黑色之后，把剩下的这个红节点变黑（缺少的黑色通过红孩子变黑补齐了）
失衡情况二：
删的是黑色节点，剩下的也是一个黑色节点（或者是null）: 当该节点删除了这个黑色之后，整条路径上对比其他路径就少了一个黑色。
-
2.1 删除节点的兄弟为红色，此时两个侄子一定是黑色（此种情况转为后续两种处理）
image.png
-
2.2 删除节点的兄弟为黑色，侄子都是黑：
-
有红色父亲的时候：把兄弟变红（平衡删掉的黑色节点），把父亲变黑（平衡该子树与其他子树对比少的黑色）
image.png -
没有红色父亲的时候：以父亲作为起点，触发黑黑的方法，把父亲的兄弟变成红色；
依次递归处理到根节点，那么每一条路径都把一个黑色变成了红色，实现黑色平衡（当然如果父亲已经是红色了，可以直接变父亲的颜色为黑色（就是上面一种情况）
image.png
-
-
2.3 删除节点的兄弟为黑色，侄子至少有一个红：
-
兄弟是左孩子，左侄子是红色：LL
image.png
-
变色逻辑：
1.通过旋转过来的3变成黑色补齐该路径上少的黑色
2.针对上位节点2，变成原本父亲的颜色，因为这条路径上本身是平衡的，所以上来的要变成原本父亲的颜色
3.针对红色的侄子1，变成黑色，因为原本该路径上，被删除节点的兄弟被当成了父亲，所以原本作为这个路径的黑色兄弟就走了，少了一个黑色，所以让红色侄子变黑。
-
兄弟是左孩子，右侄子是红色：LR
这里代码层面可以做简化，直接对比图中1和6，最后侄子上位变成了父亲的颜色，原本的父亲变成黑色
image.png- 兄弟是右孩子，右侄子是红色：RR（此种场景和LL类似）
- 兄弟是右孩子，左侄子是红色：RL（此种场景和LR类似）
-
针对左右侄子都是红色的场景，走LL或者RR都是行得通的
image.png
代码：
/**
* 删除节点
* @param deleted
*/
public void doRemove(Node deleted) {
// 删除节点的后继节点
Node replace = findReplace(deleted);
//分三种大情况：没有孩子 一个孩子 两个孩子
// 被删除节点的父亲
Node deletedParent = deleted.parent;
// 一、没有孩子
if (replace == null) {
// 1.1 删除的节点是根节点
if (deleted == root) {
root = null;
}
// 1.2 删除的节点不是根节点
else {
// 变色（注意这里要先变色 再删除）
if (isBlack(deleted)) { // 被删除的是黑色 因为没有孩子（孩子为黑色），所以也属于下面的删除的是黑，剩下的孩子也是黑
// 旋转 + 变色
fixBlackBlack(deleted);
} else { // 被删除的是红色 不需要做处理
// do nothing
}
// 删除操作
// 删除节点属于左孩子
if (deleted.isLeftChild()) {
deletedParent.left = null;
} else { // 删除节点属于右孩子
deletedParent.right = null;
}
deleted.parent = null;
}
return;
}
// 二、有一个孩子
if (deleted.left == null || deleted.right == null) {
// 2.1 删除的节点是根节点 这个唯一的孩子一定是红色：根节点和孩子互换，删除孩子
if (deleted == root) {
// delete和replace交换
deleted.key = replace.key;
deleted.value = replace.value;
deleted.left = null;
deleted.right = null;
}
// 2.2 不是根节点
else {
// 删除操作
// 看被删除的节点是左孩子还是右孩子
if (deleted.isLeftChild()) {
deletedParent.left = replace;
} else {
deletedParent.right = replace;
}
replace.parent = deletedParent;
// 被删除的节点孩子还父亲置空
deleted.parent = null;
deleted.left = null;
deleted.right = null;
// 变色操作
// 删除的是黑色 ，删剩下的也是黑色
if (isBlack(deleted) && isBlack(replace)) {
// 旋转 + 变色
fixBlackBlack(replace);
} else { // 删除的是黑色，剩下的是红色：
// 少了一个黑色，把剩下的红色变黑即可
replace.color = Color.BLACK;
}
}
return;
}
// 三、有两个孩子
/**
* 这种情况转为只有一个孩子的情况：
* 将要删除的节点和后继节点的键值交换，那么要删除的节点就变成了后继节点，此时一直递归调用，直到只有一个孩子的情况，进入情况二的分支
*/
// 交换key
int tempKey = deleted.key;
deleted.key = replace.key;
replace.key = tempKey;
// 交换value
Object tempVal = deleted.value;
deleted.value = replace.value;
replace.value = tempVal;
// 要删的就变成了replace 递归直到进入条件二
doRemove(replace);
}
被删除的节点是黑色，删剩下的也是黑色场景的旋转和变色：
/**
* 被删除的节点是黑色，删剩下的也是黑色（整体这个路径上少了一个黑色，失衡）
* - 情况一.被删节点的兄弟是红色，此时侄子一定是黑色：左旋+变色 转为下面两种情况
* - 情况二.被删节点的兄弟是黑色，侄子（这俩的孩子）都是黑：
* - 情况三.被删节点的兄弟是黑色，侄子（这俩的孩子）中至少一个红：
* @param node
*/
private void fixBlackBlack(Node node) {
if (node == root) {
//此时处理结束
return;
}
// 节点的兄弟
Node brother = node.getBrother();
// 节点的父亲
Node parent = node.parent;
// 情况一.被删节点的兄弟是红色，此时侄子一定是黑色：左旋+变色
if (isRed(brother)) {
if (node.isLeftChild()) {
// node属于左节点 父亲左旋
// 1.1 父亲左旋
leftRotate(parent);
} else {
rightRotate(parent);
}
// 1.2 调整平衡
brother.color = Color.BLACK;
parent.color = Color.RED;
// 此时把兄弟变成了黑色了 就符合了情况二和情况三，再次调用方法进行二和三情况的处理
fixBlackBlack(node);
return;
}
// 情况二：删除节点的兄弟为黑色，侄子都是黑：
assert brother != null;
if (isBlack(brother.left) && isBlack(brother.right)) {
// 2.1兄弟变红
brother.color = Color.RED;
// 如果此时父亲是红，则让父亲变黑就维持了平衡了
if (isRed(parent)) {
parent.color = Color.BLACK;
}
// 如果父亲是黑，触发黑黑调整：让兄弟变红;依次递归，让每一条路径都有一个兄弟变红，就都少了一个黑色，实现黑色平衡
else {
fixBlackBlack(parent);
}
} else {
// 情况三：删除的节点兄弟是黑色，侄子至少一个红色（一个红色或者两个都是红色）
/**
* 兄弟是左孩子，左侄子是红色：LL ：父亲右旋+变色
* 兄弟是左孩子，右侄子是红色：LR
* 兄弟是右孩子，右侄子是红色：RR
* 兄弟是右孩子，左侄子是红色：RL
*/
// LL: 兄弟是左孩子，左侄子是红色
if (brother.isLeftChild() && isRed(brother.left)) {
// 父亲右旋
rightRotate(parent);
/**
* 变色逻辑：
* 1.通过旋转过来的节点变成黑色补齐该路径上少的黑色
* 2.针对上位节点，变成原本父亲的颜色，因为这条路径上本身是平衡的，所以上来的要变成原本父亲的颜色
* 3.针对红色的侄子，变成黑色，因为原本该路径上，被删除节点的兄弟被当成了父亲，所以原本作为这个路径的黑色兄弟就走了，少了一个黑色，所以让红色侄子变黑。
*/
// 代码变色从后往前，因为从前往后会导致还变色的颜色丢失了
// 侄子变黑
brother.left.color = Color.BLACK;
//上位节点（兄弟节点）变成原来父亲的颜色
brother.color = parent.color;
// 原本父亲节点旋转下去了 变成黑色
parent.color = Color.BLACK;
}
// LR：兄弟是左孩子，右侄子是红色
else if (brother.isLeftChild() && isRed(brother.right)) {
/**
* 这里的代码可以做简化，旋转之前和之后分别做一次变色即可
*/
// 侄子上位，变成父亲的颜色（这里要先变色，因为侄子是要旋下去的，就找不到右孩子了）
brother.right.color = parent.color;
// 兄弟左旋
leftRotate(brother);
// 父亲右旋
rightRotate(parent);
// 父亲最后退位，颜色变黑，补齐删除的黑色
parent.color = Color.BLACK;
}
// RR
else if (!brother.isLeftChild() && !isRed(brother.left)) {
// 父亲左旋
leftRotate(parent);
// 侄子变黑
brother.right.color = Color.BLACK;
//上位节点（兄弟节点）变成原来父亲的颜色
brother.color = parent.color;
// 原本父亲节点旋转下去了 变成黑色
parent.color = Color.BLACK;
}
// RL
else {
// 侄子上位，变成父亲的颜色（这里要先变色，因为侄子是要旋下去的，就找不到右孩子了）
brother.left.color = parent.color;
// 兄弟右旋
rightRotate(brother);
// 父亲左旋
leftRotate(parent);
// 父亲最后退位，颜色变黑，补齐删除的黑色
parent.color = Color.BLACK;
}
}
}
四、总结
复杂度分析
| 操作 | 普通二叉搜索树 | AVL树 | 红黑树 |
|---|---|---|---|
| 查询 | 平均O(logn)，最坏O(n) | O(logn) | O(logn) |
| 插入/更新 | 平均O(logn)，最坏O(n) | O(logn) | O(logn) |
| 删除 | 平均O(logn)，最坏O(n) | O(logn) | O(logn) |
二叉搜索树
二叉搜索树的插入、删除、查询的时间复杂度与树的高度相关，因此在最坏情况下，时间复杂度为O(n)，而且容易退化成链表，查找效率低，不平衡。
AVL树
AVL树是一种严格平衡的二叉搜索树，其左右子树的高度差不超过1。因此，它能够在logn的平均时间内完成插入、删除、查询操作，但是在维护平衡的过程中，需要频繁地进行旋转操作，导致插入删除效率较低。
红黑树
红黑树是一种近似平衡的二叉搜索树，它在保持高度平衡的同时，又能够保持较高的插入删除效率。红黑树通过节点着色和旋转操作来维护平衡。红黑树在维护平衡的过程中，能够进行较少的节点旋转操作，因此插入删除效率较高，并且查询效率也较高。
综上所述，红黑树具有较高的综合性能，是一种广泛应用的数据结构。
补充：这篇文章对旋转部分没有描述的很详细，在我上一篇AVL树的实现里有很详细的介绍旋转的逻辑，可以参考。
