红黑树详解
一、介绍
作为一颗红黑树，它是一颗特殊的AVL树，也就是一颗特殊的平衡二叉树。
对于平衡二叉树而言，它的定义是，对于任何二叉树的任何一个节点，它的左子树和右子树的高度差不能大于1。
而为什么红黑树比较特殊，它除了满足平衡二叉树的特点之外，还有以下的几个特征
- 每一个节点都有一个状态，红色或者黑色
- 根节点是黑色
- 红黑树的叶子节点默认都是空引用的对象，默认都是黑色
- 红色节点的两个子节点都是黑色，也就是说红色节点不能相连
- 从任意节点，到叶子节点，其经过的路径上，黑色节点的个数都是一致的
AVL树是通过自旋转来完成的平衡
但是红黑树却不全是这样，它虽然有自旋，但主要是节点特性，加上任意节点到叶子节点经过的黑色节点数量来保证了树的子平衡。
出发点不同，则实现的方式完全不同
二、示例
首先，我们针对以上五个特性，先画一个红黑树
再次讲解一下特性
- 不是黑就是红，没什么好说的
- 根节点是黑的，也没什么好说的
- 叶子节点都是
null节点，这我认为是模拟出来的节点，仅作为第5点平衡计算使用 - 红色节点的子节点一定是黑的，也就是说不能出现红红相连的情况
- 重点讲讲第五点
从任意节点，到叶子节点，其经过的路径上，黑色节点的个数都是一致的
- 比如说
5这个节点，到达叶子节点一共有4种走法，每一种走法的黑色节点个数都是2个5->4->null，其中5、null为黑色节点5->6->null，其中5、null为黑色节点
- 比如说
10这个节点，到达叶子节点一共有6种走法，每一种走法的黑色节点个数都是3个10->5->4->null，其中10、5、null为黑色节点10->5->6->null，其中10、5、null为黑色节点10->15->null，其中10、15、null为黑色节点
三、新增节点
当有新的元素插入时，红黑树是如何保证自身平衡的呢？
如果说AVL树是靠左旋和右旋保证平衡的，那么红黑树是靠左旋、右旋和变色来保证平衡
- 左旋：和
AVL树一样进行向左旋转，保证高度差 - 右旋：和
AVL树一样进行向右旋转，保证高度差 - 变色：红色节点变成黑色节点，黑色节点变成红色节点
假设我们对上面示例的红黑树进行插入，可以分为以下这几种情况
1）当前红黑树是空树
这种没什么好说的，直接把插入的节点设置成根节点即可，注意是黑色节点
2）如果插入节点的key已存在
找到节点，更新替换掉即可
3）当插入节点的父节点是黑色节点
保证插入节点是红色节点，直接插入即可，无需要额外的处理
为什么要保证插入节点是红色的？
假设有下面这个红黑树，将插入一个值为13的节点，那么直接就成为在黑色节点的子节点即可
开始 | 结果 |
|---|---|
 |  |
那么插入的是黑色节点呢，那一定会破坏红黑树特性五，任一节点到根节点的路径上，其中黑色个数是一致的 那么如果是红色节点呢，就向上面的情况一样，说不定什么都不用处理 还有种情况就是，红色节点会遇到红色节点，出现红红相连的情况，违反了红黑树的特性四。 所以针对上面的情况，我们就默认新插入的节点就是红色的
4）当插入节点的父节点是红色节点时
根据特性二，根节点一定是黑色的，所以我们插入的节点一定有爷爷节点，包含祖宗三代。
由于插入节点是红色的，所以在本小节一定会出现红红相连的情况，根据不同的添加位置，我们有以下这几种情况
4.1）双红，且叔叔节点存在
看下面这个红黑色，当我们插入3节点后，出现双红的情况，也就是两个红色节点连接在了一起
开始 | 双红，且有叔叔节点 |
|---|---|
 |  |
由于违反特性四，我们需要做一定的处理
- 首先需要变色
- 将父节点和叔叔节点变成黑色
- 爷爷节点变成红色
- 如果爷爷节点又出现了双红的情况，那再根据情况对应再进行处理即可
步骤 | 图解 |
|---|---|
双红的情况 |  |
变色， 将父节点和叔叔节点变成黑色， 爷爷节点变成红色 |  |
由于爷爷是根节点，这里需要变回黑色 |  |
完成，又是一颗红黑树
4.2）左左红，且叔叔节点不存在
看下面这个红黑色，当我们插入3节点后，出现左左红的情况，也就是父节点是左节点，自己插入的位置也是左边。
并且注意它3节点没有叔叔节点
开始 | 左左红，且没有叔叔节点 |
|---|---|
 |  |
由于违反特性四，我们需要做一定的处理
- 首先需要变色
- 将父节点变成黑色
- 爷爷节点变成红色
- 将爷爷节点进行右旋
- 如果爷爷节点又出现了双红的情况，那再根据情况对应再进行处理即可
左旋，右旋在
AVL树有详细的讲解， 二叉树详解 | 半月无霜 (banmoon.top)
步骤 | 图解 |
|---|---|
左左红，且没有叔叔节点 |  |
先变色， 将父节点变成黑色， 将爷爷节点变成红色 |  |
再进行右旋 |  |
完成，又是一颗红黑树
4.3）左右红，且叔叔节点不存在
看下面这个红黑色，当我们插入6节点后，出现左右红的情况，也就是父节点是左节点，自己插入的位置却是右边
开始 | 左右红，且叔叔节点不存在 |
|---|---|
 |  |
红红相连，我们采用下面步骤进行处理
- 对父节点进行左旋
- 左旋完成后，你会发现左右红的情况，会变成左左红的情况，后面的步骤就是应对左左红的情况
- 变色
- 父节点变成黑色
- 爷爷节点变成红色
- 将爷爷节点进行右旋
- 如果爷爷节点又出现了双红的情况，那再根据情况对应再进行处理即可
步骤 | 图解 |
|---|---|
左右红，且叔叔节点不存在 |  |
对父节点进行左旋 出现左左红的情况 |  |
变色， 将父节点变成黑色， 将爷爷节点变成红色 |  |
再进行右旋 |  |
完成，又是一颗红黑树
4.4）右右红，且叔叔节点不存在
看下面这个红黑色，当我们插入11节点后，出现右右红的情况，也就是父节点是右节点，自己插入的位置也是右边
开始 | 右右红，且叔叔节点不存在 |
|---|---|
 |  |
红红相连，我们采用下面步骤进行处理
- 变色
- 父节点变成黑色
- 爷爷节点变成红色
- 将爷爷节点进行左旋
- 如果爷爷节点又出现了双红的情况，那再根据情况对应再进行处理即可
步骤 | 图解 |
|---|---|
右右红，且叔叔节点不存在 |  |
变色， 将父节点变成黑色， 将爷爷节点变成红色 |  |
再进行右旋 |  |
完成，又是一颗红黑树
4.5）右左红，且叔叔节点不存在
看下面这个红黑色，当我们插入11节点后，出现右右红的情况，也就是父节点是右节点，自己插入的位置也是右边
开始 | 右左红，且叔叔节点不存在 |
|---|---|
 |  |
红红相连，我们采用下面步骤进行处理
- 变色
- 父节点变成黑色
- 爷爷节点变成红色
- 将爷爷节点进行左旋
- 如果爷爷节点又出现了双红的情况，那再根据情况对应再进行处理即可
步骤 | 图解 |
|---|---|
右左红，且叔叔节点不存在 |  |
先对父节点进行右旋 出现右右红的情况 |  |
变色， 将父节点变成黑色， 将爷爷节点变成红色 |  |
再进行左旋 |  |
完成，又是一颗红黑树
四、编码
1）基础
这里面只有最基本的代码
代码语言：java复制package com.banmoon.datastructure;
import lombok.Data;
import static java.util.Objects.nonNull;
/**
* 红黑树
*
* @param <K> 键
* @param <V> 值
*/
public class BRTree<K, V> {
/**
* 红黑树颜色-红
*/
public static final Boolean RED = true;
/**
* 红黑树颜色-黑
*/
public static final Boolean BLACK = false;
/**
* 根节点
*/
public BRTreeNode<K, V> root;
public BRTree(K key, V value) {
root = new BRTreeNode<>(key, value, BLACK);
}
/**
* 中序遍历
*/
public void middleShow() {
if (nonNull(root)) {
root.middleShow();
}
}
@Data
public static class BRTreeNode<K, V> {
/**
* 键
*/
private K key;
/**
* 值
*/
private V value;
/**
* 颜色
*/
private Boolean color;
/**
* 父节点
*/
private BRTreeNode<K, V> parent;
/**
* 左子节点
*/
private BRTreeNode<K, V> left;
/**
* 右子节点
*/
private BRTreeNode<K, V> right;
public BRTreeNode(K key, V value) {
this(key, value, RED);
}
public BRTreeNode(K key, V value, Boolean color) {
this.key = key;
this.value = value;
this.color = color;
}
/**
* 中序遍历
*/
public void middleShow() {
if (nonNull(left))
left.middleShow();
System.out.println("key：" key "，value：" value);
if (nonNull(right))
right.middleShow();
}
}
}2）左旋、右旋
代码语言：java复制 /**
* 左旋 <br />
* 1、将右子树的父节点 -> 当前节点的父节点 <br />
* 2、将当前节点的父节点 -> 右子树的左节点 | 右儿子变爸爸，爸爸变左儿子 <br />
* 3、原先右节点的左子树 -> 改为当前节点的右节点 <br />
*/
private void leftRotate(BRTreeNode<K, V> node) {
BRTreeNode<K, V> right = node.right;
BRTreeNode<K, V> parent = node.parent;
BRTreeNode<K, V> leftByRight = right.left;
// 1、将右子树的父节点 -> 当前节点的父节点
if (nonNull(parent)) {
right.parent = parent;
parent.right = right;
} else {
right.parent = null;
this.root = right;
}
// 2、将当前节点的父节点 -> 左子树的左节点 | 左儿子变爸爸，爸爸变右儿子
right.left = node;
node.parent = right;
// 3、原先右节点的左子树 -> 改为当前节点的右节点
node.right = leftByRight;
if (nonNull(leftByRight)) {
leftByRight.parent = node;
}
}
/**
* 右旋 <br />
* 1、将左子树的父节点 -> 当前节点的父节点 <br />
* 2、将当前节点的父节点 -> 左子树的右节点 | 左儿子变爸爸，爸爸变右儿子 <br />
* 3、原先左节点的右子树 -> 改为当前节点的左节点 <br />
*
* @param node 当前红黑树
*/
private void rightRotate(BRTreeNode<K, V> node) {
BRTreeNode<K, V> left = node.left;
BRTreeNode<K, V> parent = node.parent;
BRTreeNode<K, V> rightByLeft = left.right;
// 1、将左子树的父节点 -> 当前节点的父节点
if (nonNull(parent)) {
left.parent = parent;
parent.left = left;
} else {
left.parent = null;
this.root = left;
}
// 2、将当前节点的父节点 -> 左子树的右节点 | 左儿子变爸爸，爸爸变右儿子
left.right = node;
node.parent = left;
// 3、原先左子树的右子树 -> 改为当前节点的左节点
node.left = rightByLeft;
if (nonNull(rightByLeft)) {
rightByLeft.parent = node;
}
}3）插入节点
这里插入节点，采用了这种模式，如果节点**key**相等，则进行节点的替换
大家可可以根据自己的策略需要来理解红黑树
代码语言：java复制 /**
* 插入
* @param key 键
* @param value 值
* @return 旧值
*/
public V add(K key, V value) {
if (Objects.isNull(this.root)) {
this.root = new BRTreeNode<>(key, value);
this.root.toggleColor();
return null;
} else {
return Optional.ofNullable(root.insert(new BRTreeNode<>(key, value), this))
.map(BRTreeNode::getValue)
.orElse(null);
}
}
@Data
public static class BRTreeNode<K extends Comparable<K>, V> {
/**
* 插入
* @param node 插入的节点
* @return 旧节点
*/
public BRTreeNode<K, V> insert(BRTreeNode<K, V> node, BRTree<K, V> tree) {
K thisKey = this.key;
K insertKey = node.getKey();
int compare = thisKey.compareTo(insertKey);
// 当key值相等，则说明要进行替换
if (compare == 0) {
node.parent = this.parent;
if (Objects.isNull(this.parent)) {
tree.root = node;
}
if (nonNull(this.left)) {
this.left.parent = node;
node.setLeft(this.left);
}
if (nonNull(this.right)) {
this.right.parent = node;
node.setRight(this.right);
}
// 颜色需要变得和当前节点一样
node.setColor(this.color);
return this;
}
// 当前key比较大，需要放置左边
else if (compare > 0) {
if (nonNull(this.left)) {
this.left.insert(node, tree);
} else {
this.left = node;
node.parent = this;
node.balanceTree(true, tree);
}
}
// 当前key比较小，需要放置右边
else {
if (nonNull(this.right)) {
this.right.insert(node, tree);
} else {
this.right = node;
node.parent = this;
node.balanceTree(false, tree);
}
}
return null;
}
/**
* 变色
*/
public void toggleColor() {
this.color = !this.color;
}
/**
* 平衡tree<br />
* 1、双红，且叔叔节点存在; 将父节点和叔叔节点变成黑色，爷爷节点变成红色; 后续处理 <br />
* 2、左左红，且叔叔节点不存在 <br />
* 3、左右红，且叔叔节点不存在 <br />
* 4、右右红，且叔叔节点不存在 <br />
* 5、右左红，且叔叔节点不存在 <br />
*
* @param left 当前节点是不是左子节点
* @param tree 当前红黑树
*/
public void balanceTree(boolean left, BRTree<K, V> tree) {
// 双红
boolean doubleRed = RED.equals(this.parent.getColor());
// 叔叔节点是否存在
BRTreeNode<K, V> grandParentNode = this.parent.parent;
BRTreeNode<K, V> uncleNode = null;
boolean existsUncle = nonNull(grandParentNode) && nonNull(uncleNode = left ? grandParentNode.getRight() : grandParentNode.getLeft());
// 双红，且叔叔节点存在
if (doubleRed && existsUncle) {
this.toggleTreeColor(uncleNode, tree);
} else if (doubleRed) {
boolean parentLeft = grandParentNode.getLeft() == this.parent;
// 左左红
if (parentLeft && left) {
leftLeftRed(tree);
}
// 左右红
else if (parentLeft) {
// 先左旋，变成左左红的情况
tree.leftRotate(this.parent);
this.left.leftLeftRed(tree);
}
// 右右红
else if (!left) {
rightRightRed(tree);
}
// 右左红
else {
// 先右旋，变成右右红的情况
tree.rightRotate(this.parent);
this.right.rightRightRed(tree);
}
}
}
/**
* 变色 <br />
* 1、将父节点和叔叔节点变成黑色 <br />
* 2、爷爷节点变成红色 <br />
* 3、递归后续处理 <br />
*
* @param uncleNode 叔叔节点
* @param tree 当前的红黑树
*/
private void toggleTreeColor(BRTreeNode<K, V> uncleNode, BRTree<K, V> tree) {
this.parent.toggleColor();
uncleNode.toggleColor();
BRTreeNode<K, V> grandParentNode = this.parent.parent;
grandParentNode.toggleColor();
// 查看爷爷节点是不是根节点
if (Objects.isNull(grandParentNode.parent)) {
// 需要重新变为黑色
grandParentNode.toggleColor();
} else {
// 递归处理后续
grandParentNode.balanceTree(grandParentNode.parent.getLeft() == grandParentNode, tree);
}
}
/**
* 左左红 <br />
* 1、将父节点变成黑色，爷爷节点变成红色 <br />
* 2、将爷爷节点进行右旋 <br />
* 3、递归后续处理 <br />
*/
private void leftLeftRed(BRTree<K, V> tree) {
// 将父节点变成黑色，爷爷节点变成红色
this.parent.toggleColor();
BRTreeNode<K, V> grandParentNode = this.parent.parent;
grandParentNode.toggleColor();
// 将爷爷节点进行右旋
tree.rightRotate(grandParentNode);
// 递归后续处理
if (nonNull(grandParentNode.parent)) {
grandParentNode.balanceTree(grandParentNode.parent.getLeft() == grandParentNode, tree);
}
}
/**
* 右右红 <br />
* 1、变色，父节点变成黑色，爷爷节点变成红色 <br />
* 2、将爷爷节点进行左旋 <br />
* 3、递归后续处理 <br />
*
* @param tree 当前红黑树
*/
private void rightRightRed(BRTree<K, V> tree) {
// 将父节点变成黑色，爷爷节点变成红色
this.parent.toggleColor();
BRTreeNode<K, V> grandParentNode = this.parent.parent;
grandParentNode.toggleColor();
// 将爷爷节点进行左旋
tree.leftRotate(grandParentNode);
// 递归后续处理
if (nonNull(grandParentNode.parent)) {
grandParentNode.balanceTree(grandParentNode.parent.getLeft() == grandParentNode, tree);
}
}
}五、完整代码
代码语言：java复制package com.banmoon.datastructure.RedBlackTree;
import lombok.Data;
import java.util.Objects;
import java.util.Optional;
import static java.util.Objects.nonNull;
/**
* 红黑树
*
* @param <K> 键
* @param <V> 值
*/
public class BRTree<K extends Comparable<K>, V> {
/**
* 红黑树颜色-红
*/
public static final Boolean RED = true;
/**
* 红黑树颜色-黑
*/
public static final Boolean BLACK = false;
/**
* 根节点
*/
public BRTreeNode<K, V> root;
public BRTree(K key, V value) {
root = new BRTreeNode<>(key, value, BLACK);
}
/**
* 中序遍历
*/
public String middleShow() {
if (nonNull(root)) {
return root.middleShow();
}
return null;
}
/**
* 左旋 <br />
* 1、将右子树的父节点 -> 当前节点的父节点 <br />
* 2、将当前节点的父节点 -> 右子树的左节点 | 右儿子变爸爸，爸爸变左儿子 <br />
* 3、原先右节点的左子树 -> 改为当前节点的右节点 <br />
*/
private void leftRotate(BRTreeNode<K, V> node) {
BRTreeNode<K, V> right = node.right;
BRTreeNode<K, V> parent = node.parent;
BRTreeNode<K, V> leftByRight = right.left;
// 1、将右子树的父节点 -> 当前节点的父节点
if (nonNull(parent)) {
right.parent = parent;
parent.right = right;
} else {
right.parent = null;
this.root = right;
}
// 2、将当前节点的父节点 -> 左子树的左节点 | 左儿子变爸爸，爸爸变右儿子
right.left = node;
node.parent = right;
// 3、原先右节点的左子树 -> 改为当前节点的右节点
node.right = leftByRight;
if (nonNull(leftByRight)) {
leftByRight.parent = node;
}
}
/**
* 右旋 <br />
* 1、将左子树的父节点 -> 当前节点的父节点 <br />
* 2、将当前节点的父节点 -> 左子树的右节点 | 左儿子变爸爸，爸爸变右儿子 <br />
* 3、原先左节点的右子树 -> 改为当前节点的左节点 <br />
*
* @param node 当前红黑树
*/
private void rightRotate(BRTreeNode<K, V> node) {
BRTreeNode<K, V> left = node.left;
BRTreeNode<K, V> parent = node.parent;
BRTreeNode<K, V> rightByLeft = left.right;
// 1、将左子树的父节点 -> 当前节点的父节点
if (nonNull(parent)) {
left.parent = parent;
parent.left = left;
} else {
left.parent = null;
this.root = left;
}
// 2、将当前节点的父节点 -> 左子树的右节点 | 左儿子变爸爸，爸爸变右儿子
left.right = node;
node.parent = left;
// 3、原先左子树的右子树 -> 改为当前节点的左节点
node.left = rightByLeft;
if (nonNull(rightByLeft)) {
rightByLeft.parent = node;
}
}
/**
* 插入
* @param key 键
* @param value 值
* @return 旧值
*/
public V add(K key, V value) {
if (Objects.isNull(this.root)) {
this.root = new BRTreeNode<>(key, value);
this.root.toggleColor();
return null;
} else {
return Optional.ofNullable(root.insert(new BRTreeNode<>(key, value), this))
.map(BRTreeNode::getValue)
.orElse(null);
}
}
@Data
public static class BRTreeNode<K extends Comparable<K>, V> {
/**
* 键
*/
private K key;
/**
* 值
*/
private V value;
/**
* 颜色
*/
private Boolean color;
/**
* 父节点
*/
private BRTreeNode<K, V> parent;
/**
* 左子节点
*/
private BRTreeNode<K, V> left;
/**
* 右子节点
*/
private BRTreeNode<K, V> right;
public BRTreeNode(K key, V value) {
this(key, value, RED);
}
public BRTreeNode(K key, V value, Boolean color) {
this.key = key;
this.value = value;
this.color = color;
}
/**
* 中序遍历
*/
public String middleShow() {
StringBuilder sb = new StringBuilder();
if (nonNull(left))
sb.append(left.middleShow());
// System.out.println("key：" key "，value：" value);
System.out.println(String.format("value: %s, 颜色: %s", value, color ? "红" : "黑"));
sb.append(value " ");
if (nonNull(right))
sb.append(right.middleShow());
return sb.toString();
}
/**
* 插入
* @param node 插入的节点
* @return 旧节点
*/
public BRTreeNode<K, V> insert(BRTreeNode<K, V> node, BRTree<K, V> tree) {
K thisKey = this.key;
K insertKey = node.getKey();
int compare = thisKey.compareTo(insertKey);
// 当key值相等，则说明要进行替换
if (compare == 0) {
node.parent = this.parent;
if (Objects.isNull(this.parent)) {
tree.root = node;
}
if (nonNull(this.left)) {
this.left.parent = node;
node.setLeft(this.left);
}
if (nonNull(this.right)) {
this.right.parent = node;
node.setRight(this.right);
}
// 颜色需要变得和当前节点一样
node.setColor(this.color);
return this;
}
// 当前key比较大，需要放置左边
else if (compare > 0) {
if (nonNull(this.left)) {
this.left.insert(node, tree);
} else {
this.left = node;
node.parent = this;
node.balanceTree(true, tree);
}
}
// 当前key比较小，需要放置右边
else {
if (nonNull(this.right)) {
this.right.insert(node, tree);
} else {
this.right = node;
node.parent = this;
node.balanceTree(false, tree);
}
}
return null;
}
/**
* 变色
*/
public void toggleColor() {
this.color = !this.color;
}
/**
* 平衡tree<br />
* 1、双红，且叔叔节点存在; 将父节点和叔叔节点变成黑色，爷爷节点变成红色; 后续处理 <br />
* 2、左左红，且叔叔节点不存在 <br />
* 3、左右红，且叔叔节点不存在 <br />
* 4、右右红，且叔叔节点不存在 <br />
* 5、右左红，且叔叔节点不存在 <br />
*
* @param left 当前节点是不是左子节点
* @param tree 当前红黑树
*/
public void balanceTree(boolean left, BRTree<K, V> tree) {
// 双红
boolean doubleRed = RED.equals(this.parent.getColor());
// 叔叔节点是否存在
BRTreeNode<K, V> grandParentNode = this.parent.parent;
BRTreeNode<K, V> uncleNode = null;
boolean existsUncle = nonNull(grandParentNode) && nonNull(uncleNode = left ? grandParentNode.getRight() : grandParentNode.getLeft());
// 双红，且叔叔节点存在
if (doubleRed && existsUncle) {
this.toggleTreeColor(uncleNode, tree);
} else if (doubleRed) {
boolean parentLeft = grandParentNode.getLeft() == this.parent;
// 左左红
if (parentLeft && left) {
leftLeftRed(tree);
}
// 左右红
else if (parentLeft) {
// 先左旋，变成左左红的情况
tree.leftRotate(this.parent);
this.left.leftLeftRed(tree);
}
// 右右红
else if (!left) {
rightRightRed(tree);
}
// 右左红
else {
// 先右旋，变成右右红的情况
tree.rightRotate(this.parent);
this.right.rightRightRed(tree);
}
}
}
/**
* 变色 <br />
* 1、将父节点和叔叔节点变成黑色 <br />
* 2、爷爷节点变成红色 <br />
* 3、递归后续处理 <br />
*
* @param uncleNode 叔叔节点
* @param tree 当前的红黑树
*/
private void toggleTreeColor(BRTreeNode<K, V> uncleNode, BRTree<K, V> tree) {
this.parent.toggleColor();
uncleNode.toggleColor();
BRTreeNode<K, V> grandParentNode = this.parent.parent;
grandParentNode.toggleColor();
// 查看爷爷节点是不是根节点
if (Objects.isNull(grandParentNode.parent)) {
// 需要重新变为黑色
grandParentNode.toggleColor();
} else {
// 递归处理后续
grandParentNode.balanceTree(grandParentNode.parent.getLeft() == grandParentNode, tree);
}
}
/**
* 左左红 <br />
* 1、将父节点变成黑色，爷爷节点变成红色 <br />
* 2、将爷爷节点进行右旋 <br />
* 3、递归后续处理 <br />
*/
private void leftLeftRed(BRTree<K, V> tree) {
// 将父节点变成黑色，爷爷节点变成红色
this.parent.toggleColor();
BRTreeNode<K, V> grandParentNode = this.parent.parent;
grandParentNode.toggleColor();
// 将爷爷节点进行右旋
tree.rightRotate(grandParentNode);
// 递归后续处理
if (nonNull(grandParentNode.parent)) {
grandParentNode.balanceTree(grandParentNode.parent.getLeft() == grandParentNode, tree);
}
}
/**
* 右右红 <br />
* 1、变色，父节点变成黑色，爷爷节点变成红色 <br />
* 2、将爷爷节点进行左旋 <br />
* 3、递归后续处理 <br />
*
* @param tree 当前红黑树
*/
private void rightRightRed(BRTree<K, V> tree) {
// 将父节点变成黑色，爷爷节点变成红色
this.parent.toggleColor();
BRTreeNode<K, V> grandParentNode = this.parent.parent;
grandParentNode.toggleColor();
// 将爷爷节点进行左旋
tree.leftRotate(grandParentNode);
// 递归后续处理
if (nonNull(grandParentNode.parent)) {
grandParentNode.balanceTree(grandParentNode.parent.getLeft() == grandParentNode, tree);
}
}
}
}六、最后
红黑树确实有点难理解，但只要了解其特性，就可以完美手撕红黑树！
上面的代码不是很全，因为差了删除节点的操作，但情况都是一样的。
简单叙述一下
- 删除一个节点
- 如果它有左节点的话，左节点上位，来到删除节点的位置，来代替他
- 接着就是判断是不是双红的情况了
- 如果是双红，走上面那个平衡的方法就好了
我是半月，你我一同共勉！！！
