作为一颗红黑树,它是一颗特殊的AVL树
,也就是一颗特殊的平衡二叉树。
对于平衡二叉树而言,它的定义是,对于任何二叉树的任何一个节点,它的左子树和右子树的高度差不能大于1。
而为什么红黑树比较特殊,它除了满足平衡二叉树的特点之外,还有以下的几个特征
AVL树
是通过自旋转来完成的平衡
但是红黑树却不全是这样,它虽然有自旋,但主要是节点特性,加上任意节点到叶子节点经过的黑色节点数量来保证了树的子平衡。
出发点不同,则实现的方式完全不同
首先,我们针对以上五个特性,先画一个红黑树
再次讲解一下特性
null
节点,这我认为是模拟出来的节点,仅作为第5
点平衡计算使用从任意节点,到叶子节点,其经过的路径上,黑色节点的个数都是一致的
5
这个节点,到达叶子节点一共有4
种走法,每一种走法的黑色节点个数都是2
个1. `5->4->null`,其中`5`、`null`为黑色节点
2. `5->6->null`,其中`5`、`null`为黑色节点比如说
1. `10->5->4->null`,其中`10`、`5`、`null`为黑色节点
2. `10->5->6->null`,其中`10`、`5`、`null`为黑色节点
3. `10->15->null`,其中`10`、`15`、`null`为黑色节点
当有新的元素插入时,红黑树是如何保证自身平衡的呢?
如果说AVL树
是靠左旋和右旋保证平衡的,那么红黑树是靠左旋、右旋和变色来保证平衡
AVL树
一样进行向左旋转,保证高度差AVL树
一样进行向右旋转,保证高度差假设我们对上面示例的红黑树进行插入,可以分为以下这几种情况
这种没什么好说的,直接把插入的节点设置成根节点即可,注意是黑色节点
找到节点,更新替换掉即可
保证插入节点是红色节点,直接插入即可,无需要额外的处理
为什么要保证插入节点是红色的? 假设有下面这个红黑树,将插入一个值为
13
的节点,那么直接就成为在黑色节点的子节点即可 开始 结果
那么插入的是黑色节点呢,那一定会破坏红黑树特性五,任一节点到根节点的路径上,其中黑色个数是一致的
那么如果是红色节点呢,就向上面的情况一样,说不定什么都不用处理
还有种情况就是,红色节点会遇到红色节点,出现红红相连的情况,违反了红黑树的特性四。
所以针对上面的情况,我们就默认新插入的节点就是红色的
根据特性二,根节点一定是黑色的,所以我们插入的节点一定有爷爷节点,包含祖宗三代。
由于插入节点是红色的,所以在本小节一定会出现红红相连的情况,根据不同的添加位置,我们有以下这几种情况
看下面这个红黑色,当我们插入3
节点后,出现双红的情况,也就是两个红色节点连接在了一起
开始 | 双红,且有叔叔节点 |
---|---|
| |
由于违反特性四,我们需要做一定的处理
1. 将父节点和叔叔节点变成黑色
2. 爷爷节点变成红色如果爷爷节点又出现了双红的情况,那再根据情况对应再进行处理即可
步骤 | 图解 |
---|---|
双红的情况 | |
变色,将父节点和叔叔节点变成黑色,爷爷节点变成红色 | |
由于爷爷是根节点,这里需要变回黑色 | |
完成,又是一颗红黑树
看下面这个红黑色,当我们插入3
节点后,出现左左红的情况,也就是父节点是左节点,自己插入的位置也是左边。
并且注意它3
节点没有叔叔节点
开始 | 左左红,且没有叔叔节点 |
---|---|
| |
由于违反特性四,我们需要做一定的处理
1. 将父节点变成黑色
2. 爷爷节点变成红色将爷爷节点进行
左旋,右旋在
AVL树
有详细的讲解, 二叉树详解 | 半月无霜 (banmoon.top)
步骤 | 图解 |
---|---|
左左红,且没有叔叔节点 | |
先变色,将父节点变成黑色,将爷爷节点变成红色 | |
再进行右旋 | |
完成,又是一颗红黑树
看下面这个红黑色,当我们插入6
节点后,出现左右红的情况,也就是父节点是左节点,自己插入的位置却是右边
开始 | 左右红,且叔叔节点不存在 |
---|---|
| |
红红相连,我们采用下面步骤进行处理
1. 左旋完成后,你会发现左右红的情况,会变成左左红的情况,后面的步骤就是应对左左红的情况变色
1. 父节点变成黑色
2. 爷爷节点变成红色将爷爷节点进行
步骤 | 图解 |
---|---|
左右红,且叔叔节点不存在 | |
对父节点进行左旋出现左左红的情况 | |
变色,将父节点变成黑色,将爷爷节点变成红色 | |
再进行右旋 | |
完成,又是一颗红黑树
看下面这个红黑色,当我们插入11
节点后,出现右右红的情况,也就是父节点是右节点,自己插入的位置也是右边
开始 | 右右红,且叔叔节点不存在 |
---|---|
| |
红红相连,我们采用下面步骤进行处理
1. 父节点变成黑色
2. 爷爷节点变成红色将爷爷节点进行
步骤 | 图解 |
---|---|
右右红,且叔叔节点不存在 | |
变色,将父节点变成黑色,将爷爷节点变成红色 | |
再进行右旋 | |
完成,又是一颗红黑树
看下面这个红黑色,当我们插入11
节点后,出现右右红的情况,也就是父节点是右节点,自己插入的位置也是右边
开始 | 右左红,且叔叔节点不存在 |
---|---|
| |
红红相连,我们采用下面步骤进行处理
1. 父节点变成黑色
2. 爷爷节点变成红色将爷爷节点进行
步骤 | 图解 |
---|---|
右左红,且叔叔节点不存在 | |
先对父节点进行右旋出现右右红的情况 | |
变色,将父节点变成黑色,将爷爷节点变成红色 | |
再进行左旋 | |
完成,又是一颗红黑树
这里面只有最基本的代码
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();
}
}
}
/**
* 左旋 <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;
}
}
这里插入节点,采用了这种模式,如果节点**key
**相等,则进行节点的替换
大家可可以根据自己的策略需要来理解红黑树
/**
* 插入
* @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);
}
}
}
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);
}
}
}
}
红黑树确实有点难理解,但只要了解其特性,就可以完美手撕红黑树!
上面的代码不是很全,因为差了删除节点的操作,但情况都是一样的。
简单叙述一下
1. 如果它有左节点的话,左节点上位,来到删除节点的位置,来代替他接着就是判断是不是双红的情况了
我是半月,你我一同共勉!!!