前言
红黑树是计算机科学内比较常用的一种数据结构，它使得对数据的搜索，插入和删除操作都能保持在O(㏒ n)的时间复杂度。然而，相比于一般的数据结构，红黑树的实现的难度有所增加。
二叉搜索树
按照二叉搜索树组织数据，使得对元素的查找非常快捷。比如上图中的二叉搜索树，如果查询值为48的节点，只需要遍历4个节点即可完成。理论上，一颗平衡的二叉搜索树的任意节点平均查找效率为树的高度h，即O(㏒ n)。但是如果二叉搜索树的失去平衡（元素全在一侧），搜索效率就退化为O(n)，因此二叉搜索树的平衡是搜索效率的关键所在。
为了维护树的平衡性，数据结构内出现了各种各样的树，比如AVL树通过维持任何节点的左右子树的高度差不大于1保持树的平衡，而红黑树使用颜色的概念维持树的平衡，使二叉搜索树的左右子树的高度差保持在固定的范围。相比于其他二叉搜索树，红黑树对二叉搜索树的平衡性维持有着自身的优势。
一、红黑树简介
R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。
红黑树是一棵二叉搜索树，它在每个结点上增加了一个存储位来表示结点的颜色，可以是RED 或 BLACK。通过对任何一条根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似平衡的。
红黑树的性质：
- (1)、每个节点或者是黑色，或者是红色。
- (2)、根节点是黑色。
- (3)、每个叶子节点（NIL）是黑色。【注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点】
- (4)、如果一个节点是红色的，则它的子节点必须是黑色的。
- (5)、从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
- (6)、一棵含有n个节点的红黑树的高度至多为2log(n+1)。
- (7)、红黑树的时间复杂度为: O(log n)。
注意：
- 特性(3)中的叶子节点，是只为空(NIL或null)的节点。
- 特性(5)确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。
红黑树示意图如下：
红黑树
红黑树的应用
红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(log n)，效率非常之高。
例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。
三、数据结构设计
和一般的数据结构设计类似，我们用抽象数据类型表示红黑树的节点，使用指针保存节点之间的相互关系。
作为红黑树节点，其基本属性有：节点的颜色、左子节点指针、右子节点指针、父节点指针、节点的值。
private static final boolean RED = false;
private static final boolean BLACK = true;
//节点类型
static class Node<K extends Comparable<K>, V> {
Node<K, V> parent; // 父结点
Node<K, V> left; // 左孩子
Node<K, V> right; // 右孩子
boolean color; // 颜色
K key;
V value;
public Node(K key, V value, Node<K, V> parent) {
this.parent = parent;
this.key = key;
this.value = value;
}
public String toString() {
return (this.color==RED?"[R]":"[B]") +key + "=" + value;
}
}
// 根节点
private Node<K, V> root;
// 树容量
private Integer size;
四、左旋和右旋
红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，都会用到旋转方法。
添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，也就不再是一颗红黑树了，而是一颗普通的树。
而通过旋转，可以使这颗树重新成为红黑树。简单点说，旋转的目的是让树保持红黑树的特性。
旋转包括两种：左旋 和 右旋。
4.1 左旋
对x进行左旋，意味着将x变成一个左节点
/**
* 向左旋转
* // 对节点node进行向左旋转操作
* // node x
* // / \ 左旋转 / \
* // T1 x ---------> node T3
* // / \ / \
* // T2 T3 T1 T2
* 左旋的时候：
* node-T1和 x-T3 不变
* node-x变为 node-T2
* 判断node节点是否有父节点
* 如果没有：
* x为root节点
* 如果有：
* x.parent = node.parent
* 还要设置 x为 node.parent的左右子节点
*
* 最后设置
* node-x 为 x-node
* @param node
* @return
*/
private void leftRotate(Node<K, V> node){
if(node != null){
Node<K, V> x = node.right;
// 将 x的左孩子 设为 node的右孩子
node.right = x.left;
// 如果 x 的左孩子非空，将 node 设为 x的左孩子的父亲
if(x.left != null){
x.left.parent = node;
}
//判断node是否有父节点
x.parent = node.parent;
if(node.parent == null){
// 如果 node的父亲 是空节点，则将x设为根节点
this.root = x;
}else if(node.parent.left == node){
// 如果 node是它父节点的左孩子，则将x设为 node 的父节点的左孩子
node.parent.left = x;
}else {
// 如果 node是它父节点的右孩子，则将x设为 node的父节点的右孩子
node.parent.right = x;
}
// 将 node 设为 x的左孩子
x.left = node;
// 将 node的父节点 设为 x
node.parent = x;
}
}
4.2 右旋
对Y进行右旋，意味着将Y变成一个右节点
/**
* 向右旋转
* // 对节点node进行向右旋转操作
* // node x
* // / \ 右旋转 / \
* // x T3 -------> T1 node
* // / \ / \
* // T1 T2 T2 T3
* 右旋的时候：
* node-T3 和 x-T1 不变
* x-T2变为 node-T2
* 判断node节点是否有父节点
* 如果没有：
* x为root节点
* 如果有：
* x.parent = node.parent
* 还要设置 x为 node.parent的左右子节点
*
* 最后设置
* node-x 为 x-node
* @param node
* @return
*/
private void rightRotate(Node<K, V> node){
if(node != null){
Node<K, V> x = node.left;
// 将 x的右孩子 设为 node的左孩子
node.left = x.right;
// 如果 x 的右孩子非空，将 node 设为 x的右孩子的父亲
if(x.right != null){
x.right.parent = node;
}
//判断node是否有父节点
x.parent = node.parent;
if(node.parent == null){
// 如果 node的父亲 是空节点，则将x设为根节点
this.root = x;
}else if(node.parent.left == node){
// 如果 node是它父节点的左孩子，则将x设为 p 的父节点的左孩子
node.parent.left = x;
}else {
// 如果 node是它父节点的右孩子，则将x设为 node的父节点的左孩子
node.parent.right = x;
}
// 将 node 设为 x的右孩子
x.right = node;
// 将 node的父节点 设为 x
node.parent = x;
}
}
仔细观察上面”左旋”和”右旋”的示意图。我们能清晰的发现，它们是对称的。无论是左旋还是右旋，被旋转的树，在旋转前是二叉查找树，并且旋转之后仍然是一颗二叉查找树。
五、插入
插入新节点后，可能会导致树不满足红黑树性质，这时就需要对树进行旋转操作和重新着色进行修复，使得它符合红黑树的定义。在插入新节点前，需要明确三个前提条件：
- 1、新插入的节点总是红色的；
- 2、如果新节点的父节点是黑色，则不需要进行修复；
- 3、如果新节点的父节点是红色，因为红黑树规定不能出现相邻的两个红色节点，需要进行修复。
插入修复时可能碰到的情况可分为的三种：
- 1、叔叔节点也为红色。
- 2、叔叔节点为空，且爷爷节点、父节点和新节点处于一条斜线上。
- 3、叔叔节点为空，且爷爷节点、父节点和新节点不处于一条斜线上。
每一种情况根据新节点的父节点是爷爷节点的左侧还是右侧可以分为两种情况，所以可以细分为6种情况。
第一种情况处理方法：
因为新节点、父节点、叔叔节点都是红色，爷爷节点是黑色，因此通过局部颜色调整，就可以使子树继续满足红黑树的性质。将父节点和叔叔节点置为黑色，爷爷节点置为红色。然后再以爷爷节点为新节点进行下一轮调整，直到满足红黑树性质为止。
第二种情况处理方法：
将新节点的父节点置为黑色，爷爷节点置为红色。如果父节点在爷爷节点左侧，则对父节点进行右旋操作。如果父节点在爷爷节点右侧，则对父节点进行左旋操作。
第三种情况处理方法：
将不在一条直线上的节点调整为直线，如果父节点在爷爷节点左侧，则对父节点进行左旋操作。如果父节点在爷爷节点右侧，则对父节点进行右旋操作。变成第二种情况，然后再进行旋转操作。
/**
* 新增节点(key,value)
* 红黑树节点的新增
* 1、普通的二叉树的插入
* 先查询到插入的位置
* 将K V 封装为node对象，插入到tree中
* 2、红黑树的平衡(调整 旋转+变色)
* @param key
* @param value
*/
public void put(K key, V value){
if(key == null){
throw new NullPointerException();
}
Node<K, V> temp = this.root;
if(temp == null){
//说明红黑树是空的，插入的节点就是root节点
this.root = new Node<>(key, value, null);
setColor(this.root, BLACK);
size = 1;
return;
}
//查找插入的位置
int cmp = 0;
//记录寻找节点的父节点
Node<K, V> parent = null;
while (temp != null){
//如果红黑树中不存在key, 则key添加到parent节点下面
parent = temp;
cmp = key.compareTo(temp.key);
if(cmp < 0){
temp = temp.left;
}else if (cmp > 0){
temp = temp.right;
}else {
//红黑树中存在key 直接替换value
temp.value = value;
return;
}
}
//循环完成，如果红黑树中不存在key, 则key添加到parent节点下面
Node<K, V> node = new Node<>(key, value, parent);
if(cmp < 0){
//如果key比 parent节点的key小，则插入到parent节点的左侧
parent.left = node;
}else {
//如果key比 parent节点的key大，则插入到parent节点的右侧
parent.right = node;
}
//做平衡处理，旋转+变色
fixAfterInsertion(node);
size++;
}
/**
* 红黑树平衡的调整处理 旋转+变色
* 1、2-3-4树, 2节点新增一个元素, 直接合并为3节点
* 红黑树：新增一个红色节点, 这个红色节点会添加在黑色节点下，不需要调整
* 2、2-3-4树, 3节点新增一个元素, 合并为一个4节点
* 红黑树：就会有6种情况, 2种(左中右)的不需要调整
* 根左左, 根右右 只旋转一次
* 根左右, 根右左旋转2次
* 3、2-3-4树, 4节点新增一个元素, 4节点中间元素升级为父节点，新增元素跟剩下节点合并
* 红黑树：新增节点是红色+爷爷节点是黑色，父节点和叔叔节点是红色
* 调整为：爷爷节点变为红色，父节点和叔叔节点变为黑色，如果爷爷节点为root节点，则调整为黑色
* @param node
*/
private void fixAfterInsertion(Node<K, V> node){
//插入的节点都为红色节点
setColor(node, RED);
while (node != null && node != root && parentOf(node).color == RED){
//node的父节点是node的爷爷节点的左子节点, 4种需要处理的情况
if(parentOf(node) == parentOf(parentOf(node)).left){
//满足条件的四种情况, 根据是否有叔叔节点，又一分为2处理
//获取当前节点的叔叔节点
Node<K, V> y = rightOf(parentOf(parentOf(node)));
if(colorOf(y) == RED){
//说明叔叔节点存在，满足条件3的情况
//爷爷节点变为红色，父节点和叔叔节点变为黑色
setColor(parentOf(node), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(node)), RED);
// 如果插入节点的爷爷节点为红色
// 将插入节点变为爷爷节点, 循环处理
node = parentOf(parentOf(node));
}else {
//叔叔节点不存在,满足条件2
if(node == rightOf(node)){
//插入节点是父节点的右侧节点，则先根据父节点做一次左旋操作
node = parentOf(node);
//左旋操作
leftRotate(node);
}
//父节点变为黑色节点
setColor(parentOf(node), BLACK);
//爷爷节点变为红色节点
setColor(parentOf(parentOf(node)), RED);
//根据爷爷节点做一次右旋操作
rightRotate(parentOf(parentOf(node)));
}
}else {
//node的父节点是node的爷爷节点的右子节点, 4种需要处理的情况,和上面刚好相反
//满足条件的四种情况, 根据是否有叔叔节点，又一分为2处理
//获取当前节点的叔叔节点
Node<K, V> y = leftOf(parentOf(parentOf(node)));
if(colorOf(y) == RED){
//说明叔叔节点存在，满足条件3的情况
//爷爷节点变为红色，父节点和叔叔节点变为黑色
setColor(parentOf(node), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(node)), RED);
// 如果插入节点的爷爷节点为红色
// 将插入节点变为爷爷节点, 循环处理
node = parentOf(parentOf(node));
}else {
//叔叔节点不存在,满足条件2
if (node == leftOf(node)) {
//插入节点是父节点的左侧节点，则先根据父节点做一次右旋操作
node = parentOf(node);
//右旋操作
rightRotate(node);
}
//父节点变为黑色节点
setColor(parentOf(node), BLACK);
//爷爷节点变为红色节点
setColor(parentOf(parentOf(node)), RED);
//根据爷爷节点做一次左旋操作
leftRotate(parentOf(parentOf(node)));
}
}
}
//根节点都为黑色节点
setColor(root, BLACK);
}
六、删除
因为删除RED节点不会破坏红黑树的任何约束，而删除BLACK节点会破坏规则4，因此只有删除节点是BLACK的时候，才会触发调整函数。删除修复操作是针对删除黑色节点才有的。
删除BLACK节点后的修复操作分为四种情况：
- 1、待删除的节点的兄弟节点是红色的节点。
- 2、待删除的节点的兄弟节点是黑色的节点，且兄弟节点的子节点都是黑色的。
- 3、待调整的节点的兄弟节点是黑色的节点，且兄弟节点的左子节点是红色的，右节点是黑色的(兄弟节点在右边)，如果兄弟节点在左边的话，就是兄弟节点的右子节点是红色的，左节点是黑色的。
- 4、待调整的节点的兄弟节点是黑色的节点，且右子节点是是红色的(兄弟节点在右边)，如果兄弟节点在左边，则就是对应的就是左节点是红色的。
每一种情况根据删除节点是父节点的左侧还是右侧可以分为两种情况，所以可以细分为8种情况。
第一种情况处理方法：
由于兄弟节点是红色节点的时候，无法借调黑节点，所以需要将兄弟节点提升到父节点。因为兄弟节点是红色的，无法借到一个黑节点来填补删除的黑节点。兄弟节点是红色，其子节点是黑色的，可以从它的子节点借调。提升操作需要对兄弟节点做一个左旋操作，如果是镜像结构的树只需要做对应的右旋操作即可。
第二种情况处理方法：
由于兄弟节点以及其子节点都是黑色的，可以消除一个黑色节点，这样就可以保证树的局部的颜色符合定义了。这个时候需要将父节点变成新的节点，继续向上调整，直到整颗树的颜色符合红黑树的定义为止。这种情况下之所以要将兄弟节点变红，是因为如果把兄弟节点借调过来，会导致兄弟的结构不符合红黑树的定义，这样的情况下只能是将兄弟节点也变成红色来达到颜色的平衡。当将兄弟节点也变红之后，达到了局部的平衡了，但是对于祖父节点来说是不符合定义4的。这样就需要回溯到父节点，接着进行修复操作。
第三种情况处理方法：
第三种情况是一个中间步骤，它的目的是将左边的红色节点借调过来，这样就可以转换成第四种情况进行处理。
第四种情况处理方法：
是真正的节点借调操作，通过将兄弟节点以及兄弟节点的右节点借调过来，并将兄弟节点的右子节点变成红色来达到借调两个黑节点的目的，这样的话，整棵树还是符合RBTree的定义的。这种情况的发生只有在待删除的节点的兄弟节点为黑，且子节点不全部为黑，才有可能借调到两个节点来做黑节点使用，从而保持整棵树都符合红黑树的定义。
/**
* 删除键为key的节点，并返回被删除的结点的值
* @param key
* @return
*/
public V remove(K key){
//先根据key找到对应的节点
Node<K, V> node = getNode(key);
if(node == null){
//key不存在
return null;
}
//把删除节点原来的值保存下来
V oldValue = node.value;
//删除节点的方法
deleteNode(node);
size--;
return oldValue;
}
/**
* 删除结点node
* 3种情况：
* 1、删除叶子节点，直接删除
* 2、删除节点有一个子节点，用子节点来替代
* 3、删除的节点有2个子节点，那么此时需要获取被删除节点的前驱或者后继节点来替代
* 可以转换为1、2的情况
* @param node
*/
private void deleteNode(Node<K, V> node){
//情况3：被删除节点有左、右子节点，转换为1、2的情况处理
if(leftOf(node) != null && rightOf(node) != null){
//找到颜删除节点的后继节点
Node<K, V> successor = successor(node);
//然后用后继节点的值, 覆盖掉要删除节点的信息
node.key = successor.key;
node.value = successor.value;
//然后要删除的节点就变成了后继节点
node = successor;
}
//获取要替换的节点
Node<K, V> replacement = node.left != null ? node.left : node.right;
if(replacement != null){
//情况2：删除有一个子节点的情况
//将删除节点的父节点设置为替换节点的父节点
replacement.parent = node.parent;
if(node.parent == null){
//删除节点的父节点为空，则替换节点设置为根节点
root = replacement;
}else if(node == leftOf(parentOf(node))){
//删除节点为其父节点的左子节点
parentOf(node).left = replacement;
}else {
//删除节点为其父节点的右子节点
parentOf(node).right = replacement;
}
//将node节点的左、右孩子和父指针都指向null, 等待gc
node.left = node.right = node.parent = null;
//替换完成后需要调整红黑树的平衡
if(node.color == BLACK){
//只有删除节点为黑节点才需要做平衡操作
fixAfterDeletion(replacement);
}
}else if(node.parent == null){
//要删除的是root节点
root = null;
}else {
//情况1：删除的是叶子结点, 直接删除
//先调整
if(node.color == BLACK){
//只有删除节点为黑节点才需要做平衡操作
fixAfterDeletion(node);
}
//在删除
if(node.parent != null){
if(node == leftOf(parentOf(node))){
parentOf(node).left = null;
}else {
parentOf(node).right = null;
}
node = null;
}
}
}
/**
* 删除节点后的调整处理
* 2-3-4树的删除操作
* 1、情况1：自己能搞定, 对应的叶子节点是3节点或者4节点
* 2、情况2：自己搞不定, 需要兄弟节点借, 但是兄弟节点不借, 找父亲节点借，父节点下来, 然后兄弟节点代替父亲节点
* 3、情况3：跟兄弟节点借, 兄弟节点也没有
* @param node
*/
private void fixAfterDeletion(Node<K,V> node) {
//情况2和3
while (node != null && colorOf(node) == BLACK){
//如果当前替换节点是父节点的左子节点
if(node == leftOf(parentOf(node))){
//查找兄弟节点
Node<K, V> rNode = rightOf(parentOf(node));
if(colorOf(rNode) == RED){
//不是真正的兄弟节点
setColor(rNode, BLACK);
setColor(parentOf(node), RED);
leftRotate(parentOf(node));
rNode = rightOf(parentOf(node));
}
if(colorOf(leftOf(rNode)) == BLACK && colorOf(rightOf(rNode)) == BLACK){
//情况3：跟兄弟节点借, 兄弟节点没得借
setColor(rNode, RED);
node = parentOf(node);
}else {
//情况2：跟兄弟节点借, 兄弟节点有得借
if(colorOf(rightOf(rNode)) == BLACK){
//不存在右孩子, 肯定存在左孩子
setColor(rNode, RED);
setColor(leftOf(rNode), BLACK);
rightRotate(rNode);
rNode = rightOf(parentOf(node));
}
setColor(rNode, colorOf(parentOf(node)));
setColor(parentOf(node), BLACK);
setColor(rightOf(rNode), BLACK);
leftRotate(parentOf(node));
node = root;
}
}else {//如果当前替换节点是父节点的右子节点
//查找兄弟节点
Node<K, V> rNode = leftOf(parentOf(node));
if(colorOf(rNode) == RED){
//不是真正的兄弟节点
setColor(rNode, BLACK);
setColor(parentOf(node), RED);
rightRotate(parentOf(node));
rNode = leftOf(parentOf(node));
}
if(colorOf(leftOf(rNode)) == BLACK && colorOf(rightOf(rNode)) == BLACK){
//情况3：跟兄弟节点借, 兄弟节点没得借
setColor(rNode, RED);
node = parentOf(node);
}else {
//情况2：跟兄弟节点借, 兄弟节点有得借
if(colorOf(leftOf(rNode)) == BLACK){
//不存在右孩子, 肯定存在左孩子
setColor(rNode, RED);
setColor(rightOf(rNode), BLACK);
leftRotate(rNode);
rNode = leftOf(parentOf(node));
}
setColor(rNode, colorOf(parentOf(node)));
setColor(parentOf(node), BLACK);
setColor(leftOf(rNode), BLACK);
rightRotate(parentOf(node));
node = root;
}
}
}
//情况1：替代的节点是红色, 则直接设置为黑色即可
setColor(node, BLACK);
}
七、完整代码
import java.util.LinkedList;
import java.util.Queue;
/**
* @Author: huangyibo
* @Date: 2022/3/2 0:01
* @Description: 红黑树
*/
public class RBTree<K extends Comparable<K>, V> {
private static final boolean RED = false;
private static final boolean BLACK = true;
//节点类型
static class Node<K extends Comparable<K>, V> {
Node<K, V> parent; // 父结点
Node<K, V> left; // 左孩子
Node<K, V> right; // 右孩子
boolean color; // 颜色
K key;
V value;
public Node(K key, V value, Node<K, V> parent) {
this.parent = parent;
this.key = key;
this.value = value;
}
public String toString() {
return (this.color==RED?"[R]":"[B]") +key + "=" + value;
}
}
// 根节点
private Node<K, V> root;
// 树容量
private Integer size;
public RBTree(){
root = null;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public int getSize() {
return size;
}
/**
* 前序遍历"红黑树"
*/
public void preOrder() {
preOrder(root);
}
/**
* 前序遍历"红黑树"
* @param node
*/
private void preOrder(Node<K, V> node) {
if(node != null) {
System.out.print(node.key+":"+node.value+" ,");
preOrder(node.left);
preOrder(node.right);
}
}
/**
* 中序遍历"红黑树"
*/
public void inOrder() {
inOrder(root);
}
/**
* 中序遍历"红黑树"
* @param node
*/
private void inOrder(Node<K, V> node) {
if(node != null) {
inOrder(node.left);
System.out.print(node.key+":"+node.value+" ,");
inOrder(node.right);
}
}
/**
* 后序遍历"红黑树"
*/
public void postOrder() {
postOrder(root);
}
/**
* 后序遍历"红黑树"
* @param node
*/
private void postOrder(Node<K, V> node) {
if(node != null) {
postOrder(node.left);
postOrder(node.right);
System.out.print(node.key+":"+node.value+" ,");
}
}
/**
* 红黑树的层序遍历
*/
public void layerErgodic(){
layerErgodic(root);
}
/**
* 红黑树的层序遍历
* 层序遍历, 从左到右一层一层遍历, 借助队列实现
* @param node
*/
public void layerErgodic(Node<K, V> node){
// LinkedList实现了Queue接口
Queue<Node<K, V>> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
Node<K, V> cur = queue.remove();
System.out.print(node.key+":"+node.value+" ,");
if(cur.left != null){
queue.add(cur.left);
}
if(cur.right != null){
queue.add(cur.right);
}
}
}
/**
* 查找最小结点的key
* @return
*/
public K minimum() {
Node<K, V> p = minimum(root);
if (p != null){
return p.key;
}
return null;
}
/**
* 查找最小结点：返回tree为根结点的红黑树的最小结点。
* @param tree
* @return
*/
private Node<K, V> minimum(Node<K, V> tree) {
if (tree == null) {
return null;
}
while(tree.left != null) {
tree = tree.left;
}
return tree;
}
/**
* 查找最大结点的key
* @return
*/
public K maximum() {
Node<K, V> p = maximum(root);
if (p != null) {
return p.key;
}
return null;
}
/**
* 查找最大结点：返回tree为根结点的红黑树的最大结点。
* @param tree
* @return
*/
private Node<K, V> maximum(Node<K, V> tree) {
if (tree == null) {
return null;
}
while(tree.right != null) {
tree = tree.right;
}
return tree;
}
/**
* 获取节点node的颜色
* @param node
* @return
*/
private boolean colorOf(Node<K, V> node) {
return node != null ? node.color : BLACK;
}
/**
* 获取节点node的父节点
* @param node
* @return
*/
private Node<K, V> parentOf(Node<K, V> node) {
return node != null ? node.parent : null;
}
/**
* 获取节点node的左子节点
* @param node
* @return
*/
private Node<K, V> leftOf(Node<K, V> node) {
return node != null ? node.left : null;
}
/**
* 获取节点node的右子节点
* @param node
* @return
*/
private Node<K, V> rightOf(Node<K, V> node) {
return node != null ? node.right : null;
}
/**
* 设置节点node的颜色
* @param node
* @param color
*/
private void setColor(Node<K, V> node, boolean color) {
if (node != null){
node.color = color;
}
}
/**
* 向左旋转
* // 对节点node进行向左旋转操作
* // node x
* // / \ 左旋转 / \
* // T1 x ---------> node T3
* // / \ / \
* // T2 T3 T1 T2
* 左旋的时候：
* node-T1和 x-T3 不变
* node-x变为 node-T2
* 判断node节点是否有父节点
* 如果没有：
* x为root节点
* 如果有：
* x.parent = node.parent
* 还要设置 x为 node.parent的左右子节点
*
* 最后设置
* node-x 为 x-node
* @param node
* @return
*/
private void leftRotate(Node<K, V> node){
if(node != null){
Node<K, V> x = node.right;
// 将 x的左孩子 设为 node的右孩子
node.right = x.left;
// 如果 x 的左孩子非空，将 node 设为 x的左孩子的父亲
if(x.left != null){
x.left.parent = node;
}
//判断node是否有父节点
x.parent = node.parent;
if(node.parent == null){
// 如果 node的父亲 是空节点，则将x设为根节点
this.root = x;
}else if(node.parent.left == node){
// 如果 node是它父节点的左孩子，则将x设为 node 的父节点的左孩子
node.parent.left = x;
}else {
// 如果 node是它父节点的右孩子，则将x设为 node的父节点的右孩子
node.parent.right = x;
}
// 将 node 设为 x的左孩子
x.left = node;
// 将 node的父节点 设为 x
node.parent = x;
}
}
/**
* 向右旋转
* // 对节点node进行向右旋转操作
* // node x
* // / \ 右旋转 / \
* // x T3 -------> T1 node
* // / \ / \
* // T1 T2 T2 T3
* 右旋的时候：
* node-T3 和 x-T1 不变
* x-T2变为 node-T2
* 判断node节点是否有父节点
* 如果没有：
* x为root节点
* 如果有：
* x.parent = node.parent
* 还要设置 x为 node.parent的左右子节点
*
* 最后设置
* node-x 为 x-node
* @param node
* @return
*/
private void rightRotate(Node<K, V> node){
if(node != null){
Node<K, V> x = node.left;
// 将 x的右孩子 设为 node的左孩子
node.left = x.right;
// 如果 x 的右孩子非空，将 node 设为 x的右孩子的父亲
if(x.right != null){
x.right.parent = node;
}
//判断node是否有父节点
x.parent = node.parent;
if(node.parent == null){
// 如果 node的父亲 是空节点，则将x设为根节点
this.root = x;
}else if(node.parent.left == node){
// 如果 node是它父节点的左孩子，则将x设为 p 的父节点的左孩子
node.parent.left = x;
}else {
// 如果 node是它父节点的右孩子，则将x设为 node的父节点的左孩子
node.parent.right = x;
}
// 将 node 设为 x的右孩子
x.right = node;
// 将 node的父节点 设为 x
node.parent = x;
}
}
/**
* 新增节点(key,value)
* 红黑树节点的新增
* 1、普通的二叉树的插入
* 先查询到插入的位置
* 将K V 封装为node对象，插入到tree中
* 2、红黑树的平衡(调整 旋转+变色)
* @param key
* @param value
*/
public void put(K key, V value){
if(key == null){
throw new NullPointerException();
}
Node<K, V> temp = this.root;
if(temp == null){
//说明红黑树是空的，插入的节点就是root节点
this.root = new Node<>(key, value, null);
setColor(this.root, BLACK);
size = 1;
return;
}
//查找插入的位置
int cmp = 0;
//记录寻找节点的父节点
Node<K, V> parent = null;
while (temp != null){
//如果红黑树中不存在key, 则key添加到parent节点下面
parent = temp;
cmp = key.compareTo(temp.key);
if(cmp < 0){
temp = temp.left;
}else if (cmp > 0){
temp = temp.right;
}else {
//红黑树中存在key 直接替换value
temp.value = value;
return;
}
}
//循环完成，如果红黑树中不存在key, 则key添加到parent节点下面
Node<K, V> node = new Node<>(key, value, parent);
if(cmp < 0){
//如果key比 parent节点的key小，则插入到parent节点的左侧
parent.left = node;
}else {
//如果key比 parent节点的key大，则插入到parent节点的右侧
parent.right = node;
}
//做平衡处理，旋转+变色
fixAfterInsertion(node);
size++;
}
/**
* 红黑树平衡的调整处理 旋转+变色
* 1、2-3-4树, 2节点新增一个元素, 直接合并为3节点
* 红黑树：新增一个红色节点, 这个红色节点会添加在黑色节点下，不需要调整
* 2、2-3-4树, 3节点新增一个元素, 合并为一个4节点
* 红黑树：就会有6种情况, 2种(左中右)的不需要调整
* 根左左, 根右右 只旋转一次
* 根左右, 根右左旋转2次
* 3、2-3-4树, 4节点新增一个元素, 4节点中间元素升级为父节点，新增元素跟剩下节点合并
* 红黑树：新增节点是红色+爷爷节点是黑色，父节点和叔叔节点是红色
* 调整为：爷爷节点变为红色，父节点和叔叔节点变为黑色，如果爷爷节点为root节点，则调整为黑色
* @param node
*/
private void fixAfterInsertion(Node<K, V> node){
//插入的节点都为红色节点
setColor(node, RED);
while (node != null && node != root && parentOf(node).color == RED){
//node的父节点是node的爷爷节点的左子节点, 4种需要处理的情况
if(parentOf(node) == parentOf(parentOf(node)).left){
//满足条件的四种情况, 根据是否有叔叔节点，又一分为2处理
//获取当前节点的叔叔节点
Node<K, V> y = rightOf(parentOf(parentOf(node)));
if(colorOf(y) == RED){
//说明叔叔节点存在，满足条件3的情况
//爷爷节点变为红色，父节点和叔叔节点变为黑色
setColor(parentOf(node), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(node)), RED);
// 如果插入节点的爷爷节点为红色
// 将插入节点变为爷爷节点, 循环处理
node = parentOf(parentOf(node));
}else {
//叔叔节点不存在,满足条件2
if(node == rightOf(node)){
//插入节点是父节点的右侧节点，则先根据父节点做一次左旋操作
node = parentOf(node);
//左旋操作
leftRotate(node);
}
//父节点变为黑色节点
setColor(parentOf(node), BLACK);
//爷爷节点变为红色节点
setColor(parentOf(parentOf(node)), RED);
//根据爷爷节点做一次右旋操作
rightRotate(parentOf(parentOf(node)));
}
}else {
//node的父节点是node的爷爷节点的右子节点, 4种需要处理的情况,和上面刚好相反
//满足条件的四种情况, 根据是否有叔叔节点，又一分为2处理
//获取当前节点的叔叔节点
Node<K, V> y = leftOf(parentOf(parentOf(node)));
if(colorOf(y) == RED){
//说明叔叔节点存在，满足条件3的情况
//爷爷节点变为红色，父节点和叔叔节点变为黑色
setColor(parentOf(node), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(node)), RED);
// 如果插入节点的爷爷节点为红色
// 将插入节点变为爷爷节点, 循环处理
node = parentOf(parentOf(node));
}else {
//叔叔节点不存在,满足条件2
if (node == leftOf(node)) {
//插入节点是父节点的左侧节点，则先根据父节点做一次右旋操作
node = parentOf(node);
//右旋操作
rightRotate(node);
}
//父节点变为黑色节点
setColor(parentOf(node), BLACK);
//爷爷节点变为红色节点
setColor(parentOf(parentOf(node)), RED);
//根据爷爷节点做一次左旋操作
leftRotate(parentOf(parentOf(node)));
}
}
}
//根节点都为黑色节点
setColor(root, BLACK);
}
/**
* 查找node的前驱节点
* @param node
* @return
*/
private Node<K, V> predecessor(Node<K, V> node){
if(node == null){
return null;
}
//node节点的左子节点不为空
if(node.left != null){
Node<K, V> temp = node.left;
//temp的右子节点不为空，一直循环
while (temp.right != null){
temp = temp.right;
}
return temp;
}else {
//如果node为叶子节点，那么找比node小的最大节点
//这种情况在删除中是不存在的，因为删除叶子节点，直接删除即可
//但是在寻找前驱或者后继节点还是存在的
Node<K, V> p = node.parent;
Node<K, V> temp = node;
while (p != null && temp == p.left){
temp = p;
p = p.parent;
}
return p;
}
}
/**
* 查找node的后继节点
* @param node
* @return
*/
private Node<K, V> successor(Node<K, V> node){
if(node == null){
return null;
}
//node节点的右子节点不为空
if(node.right != null){
Node<K, V> temp = node.right;
//temp的左子节点不为空，一直循环
while (temp.left != null){
temp = temp.left;
}
return temp;
}else {
//如果node为叶子节点，那么找比node大的最小节点
//这种情况在删除中是不存在的，因为删除叶子节点，直接删除即可
//但是在寻找前驱或者后继节点还是存在的
Node<K, V> p = node.parent;
Node<K, V> temp = node;
while (p != null && temp == p.right){
temp = p;
p = p.parent;
}
return p;
}
}
/**
* 根据key获取对应的节点
* @param key
* @return
*/
private Node<K, V> getNode(K key){
if(key == null){
throw new NullPointerException();
}
Node<K, V> node = this.root;
while (node != null){
int cmp = key.compareTo(node.key);
if(cmp < 0){
node = node.left;
}else if(cmp > 0){
node = node.right;
}else {
return node;
}
}
return null;
}
/**
* 获取键为key的节点的值，不存在返回空
* @param key
* @return
*/
public V get(K key) {
Node<K, V> node = getNode(key);
return (node == null ? null : node.value);
}
/**
* 删除键为key的节点，并返回被删除的结点的值
* @param key
* @return
*/
public V remove(K key){
//先根据key找到对应的节点
Node<K, V> node = getNode(key);
if(node == null){
//key不存在
return null;
}
//把删除节点原来的值保存下来
V oldValue = node.value;
//删除节点的方法
deleteNode(node);
size--;
return oldValue;
}
/**
* 删除结点node
* 3种情况：
* 1、删除叶子节点，直接删除
* 2、删除节点有一个子节点，用子节点来替代
* 3、删除的节点有2个子节点，那么此时需要获取被删除节点的前驱或者后继节点来替代
* 可以转换为1、2的情况
* @param node
*/
private void deleteNode(Node<K, V> node){
//情况3：被删除节点有左、右子节点，转换为1、2的情况处理
if(leftOf(node) != null && rightOf(node) != null){
//找到颜删除节点的后继节点
Node<K, V> successor = successor(node);
//然后用后继节点的值, 覆盖掉要删除节点的信息
node.key = successor.key;
node.value = successor.value;
//然后要删除的节点就变成了后继节点
node = successor;
}
//获取要替换的节点
Node<K, V> replacement = node.left != null ? node.left : node.right;
if(replacement != null){
//情况2：删除有一个子节点的情况
//将删除节点的父节点设置为替换节点的父节点
replacement.parent = node.parent;
if(node.parent == null){
//删除节点的父节点为空，则替换节点设置为根节点
root = replacement;
}else if(node == leftOf(parentOf(node))){
//删除节点为其父节点的左子节点
parentOf(node).left = replacement;
}else {
//删除节点为其父节点的右子节点
parentOf(node).right = replacement;
}
//将node节点的左、右孩子和父指针都指向null, 等待gc
node.left = node.right = node.parent = null;
//替换完成后需要调整红黑树的平衡
if(node.color == BLACK){
//只有删除节点为黑节点才需要做平衡操作
fixAfterDeletion(replacement);
}
}else if(node.parent == null){
//要删除的是root节点
root = null;
}else {
//情况1：删除的是叶子结点, 直接删除
//先调整
if(node.color == BLACK){
//只有删除节点为黑节点才需要做平衡操作
fixAfterDeletion(node);
}
//在删除
if(node.parent != null){
if(node == leftOf(parentOf(node))){
parentOf(node).left = null;
}else {
parentOf(node).right = null;
}
node = null;
}
}
}
/**
* 删除节点后的调整处理
* 2-3-4树的删除操作
* 1、情况1：自己能搞定, 对应的叶子节点是3节点或者4节点
* 2、情况2：自己搞不定, 需要兄弟节点借, 但是兄弟节点不借, 找父亲节点借，父节点下来, 然后兄弟节点代替父亲节点
* 3、情况3：跟兄弟节点借, 兄弟节点也没有
* @param node
*/
private void fixAfterDeletion(Node<K,V> node) {
//情况2和3
while (node != null && colorOf(node) == BLACK){
//如果当前替换节点是父节点的左子节点
if(node == leftOf(parentOf(node))){
//查找兄弟节点
Node<K, V> rNode = rightOf(parentOf(node));
if(colorOf(rNode) == RED){
//不是真正的兄弟节点
setColor(rNode, BLACK);
setColor(parentOf(node), RED);
leftRotate(parentOf(node));
rNode = rightOf(parentOf(node));
}
if(colorOf(leftOf(rNode)) == BLACK && colorOf(rightOf(rNode)) == BLACK){
//情况3：跟兄弟节点借, 兄弟节点没得借
setColor(rNode, RED);
node = parentOf(node);
}else {
//情况2：跟兄弟节点借, 兄弟节点有得借
if(colorOf(rightOf(rNode)) == BLACK){
//不存在右孩子, 肯定存在左孩子
setColor(rNode, RED);
setColor(leftOf(rNode), BLACK);
rightRotate(rNode);
rNode = rightOf(parentOf(node));
}
setColor(rNode, colorOf(parentOf(node)));
setColor(parentOf(node), BLACK);
setColor(rightOf(rNode), BLACK);
leftRotate(parentOf(node));
node = root;
}
}else {//如果当前替换节点是父节点的右子节点
//查找兄弟节点
Node<K, V> rNode = leftOf(parentOf(node));
if(colorOf(rNode) == RED){
//不是真正的兄弟节点
setColor(rNode, BLACK);
setColor(parentOf(node), RED);
rightRotate(parentOf(node));
rNode = leftOf(parentOf(node));
}
if(colorOf(leftOf(rNode)) == BLACK && colorOf(rightOf(rNode)) == BLACK){
//情况3：跟兄弟节点借, 兄弟节点没得借
setColor(rNode, RED);
node = parentOf(node);
}else {
//情况2：跟兄弟节点借, 兄弟节点有得借
if(colorOf(leftOf(rNode)) == BLACK){
//不存在右孩子, 肯定存在左孩子
setColor(rNode, RED);
setColor(rightOf(rNode), BLACK);
leftRotate(rNode);
rNode = leftOf(parentOf(node));
}
setColor(rNode, colorOf(parentOf(node)));
setColor(parentOf(node), BLACK);
setColor(leftOf(rNode), BLACK);
rightRotate(parentOf(node));
node = root;
}
}
}
//情况1：替代的节点是红色, 则直接设置为黑色即可
setColor(node, BLACK);
}
/**
* 销毁红黑树, 递归调用销毁红黑树的节点
* @param node
*/
private void destroy(Node<K, V> node) {
//递归结束条件
if (node == null){
return ;
}
//递归调用，销毁当前节点的左子树
if (node.left != null){
destroy(node.left);
}
//递归调用，销毁当前节点的右子树
if (node.right != null){
destroy(node.right);
}
node = null;
}
/**
* 销毁红黑树
*/
public void clear() {
destroy(root);
root = null;
}
/**
* 计算整个树的最大深度
* @return
*/
public int maxDepth() {
return maxDepth(root);
}
/**
* 计算指定树node的最大深度
* @param node
* @return
*/
private int maxDepth(Node<K, V> node) {
if(node == null) {
return 0;
}
//1.计算左子树的最大深度；
int maxL = maxDepth(node.left);
//2.计算右子树的最大深度；
int maxR = maxDepth(node.right);
return (Math.max(maxL, maxR)) + 1;
}
}
测试
public class RBTreeTest {
public static void main(String[] args) {
//红黑树构建与插入
RBTree<Integer, String> bt = new RBTree<>();
bt.put(0, "0");
bt.put(1, "1");
bt.put(2, "2");
bt.put(3, "3");
bt.put(4, "4");
bt.put(5, "5");
bt.put(6, "6");
bt.put(7, "7");
bt.put(8, "8");
bt.put(9, "9");
bt.put(10, "10");
System.out.println(bt.getSize());
System.out.println(bt.remove(2));
System.out.println(bt.remove(7));
System.out.println(bt.remove(8));
System.out.println(bt.remove(9));
System.out.println(bt.getSize());
System.out.println("初始化后的大小：" + bt.getSize());
System.out.println("初始化后的最小值：" + bt.get(bt.minimum()) +
" 初始化后的最大值：" + bt.get(bt.maximum()));
//删除测试
//bt.delete(7);
System.out.println("删除后的大小：" + bt.getSize() + " " + bt.get(7));
System.out.print("删除后的最小值与最大值：");
System.out.println(bt.get(bt.minimum()) + " " + bt.get(bt.maximum()));
//红黑树的深度
System.out.println("红黑树的深度：" + bt.maxDepth());
//遍历
System.out.print("层次遍历：");
bt.layerErgodic();
System.out.println();
System.out.print("前序遍历：");
bt.preOrder();
System.out.println();
System.out.print("后序遍历：");
bt.postOrder();
System.out.println();
System.out.print("中序遍历：");
bt.inOrder();
}
}
八、红黑树与AVL树的比较
先从复杂度分析说起，任意节点的黑深度（Black Depth）是指当前节点到NIL（树尾端）途径的黑色节点个数。根据约束条件的第（4）、（5）条，可以推出对于任意高度的节点，它的黑深度都满足：Black Depth ≥ height / 2。也就是说，对于任意包含n个节点的红黑树而言，它的根节点高度h ≤ 2log2（n+1）。常规BST操作比如查找、插入、删除等，时间复杂度为O（h），即取决于树的高度h。当树失衡时，时间复杂度将有可能恶化到O（n），即h = n。所以，当我们能保证树的高度始终保持在O（logn）时，便能保证所有操作的时间复杂度都能保持在O（logn）以内。
红黑树的平衡性并不如AVL树，它维持的只是一种大致上的平衡，并不严格保证左右子树的高度差不超过1。这导致在相同节点数的情况下，红黑树的高度可能更高，也就是说，平均查找次数会高于相同情况下的AVL树。在插入时，红黑树和AVL树都能在至多两次旋转内恢复平衡。在删除时，由于红黑树只追求大致上的平衡，因此红黑树能在至多三次旋转内恢复平衡，而追求绝对平衡的AVL树，则至多需要O（logn）次旋转。AVL树在插入与删除时，将向上回溯确定是否需要旋转，这个回溯的时间成本最差可能为O（logn），而红黑树每次向上回溯的步长为2，回溯成本降低。因此，面对频繁的插入和删除，红黑树更为合适；面对低频修改、大量查询时，AVL树将更为合适。
参考：
https://blog.csdn.net/u012428012/article/details/79090702
https://www.cnblogs.com/fanzhidongyzby/p/3187912.html
https://www.cnblogs.com/zhuwbox/p/3634895.html
https://blog.csdn.net/weixin_39084521/article/details/90553337
https://www.cnblogs.com/skywang12345/p/3624343.html
https://www.cnblogs.com/skywang12345/p/3245399.html
网友评论