写这篇文章的目的
红黑树很重要，所以学一下，整理一下笔记
代码下载
Demooo/java-demoo/src/main/java/myredblacktree at master · cbeann/Demooo · GitHub
红黑树难点
红黑树性质
- 每一个节点要么是黑色，要么是红色的。
- 根节点是黑色。
- 叶子节点（Null）是黑色。
- 每一个红色节点的两个子节点一定都是黑色。不能有两个红色节点相连。
- 任意一个节点到每一个叶子节点的路径都包含相同的黑节点，俗称“黑高”（推论：如果一个节点存在黑子节点，那么该节点肯定有两个子节点）。
插入节点必为红色
假设插入的节点为红色，那么在不考虑空树的情况下，该插入节点的父节点可能为红色，也可能为黑色。如果父节点为黑色，插入后没有破坏红黑树的性质；如果父节点为红色，则破坏了红黑树性质（不能有两个红色节点相连）。
假设插入的节点为黑色，则插入后必破坏红黑树的性质（任意一个节点到每一个叶子节点的路径都包含相同的黑节点）
综上：插入节点必为红色
插入变色规则
插入后修复红黑树平衡的方法 情景1：红黑树为空树，插入节点将作为根，将根节点染色为黑色。 情景2：插入节点的key已经存在，则只需要替换value值即可。 情景3：插入节点的父节点为黑色，插入后不需要其他操作。（因为插入的的为红色，黑色节点没有变化，所以红黑树依然平衡，所以不需要处理） 情景4：插入节点的父节点为红色（非常复杂） 情景4-1：叔叔节点存在。并且叔叔为红色(父-叔 双红)。将爸爸和叔叔染色为黑色，将爷爷染色为红色，并且在以爷爷节点为当前节点，进行下一轮处理。 情景4-2：叔叔节点不存在或者为黑色。父节点为爷爷节点的左子树。 情景4-2-1：插入节点为其父节点的左子节点（LL情景）。将爸爸染色为黑色，将爷爷染色为红色，然后以爷爷节点右旋，就结束了。 情景4-2-2：插入节点为其父节点的右子节点（LR情景）。以爸爸节点进行一次左旋，得到LL双红的情景（4.2.1），然后指定爸爸节点为当前节点进行下一轮处理。 情景4-3：叔叔节点不存在，或者为黑色。父节点为爷爷节点的右子树 情景4-3-1：插入节点为其父节点的右子节点（RR情景）。将爸爸染色为黑色，将爷爷染色为红色，然后以爷爷节点左旋，就结束了。 情景4-3-2：插入节点为其父节点的左子节点（RL情景）。以爸爸节点进行一次右旋，得到RR双红的情景（4.3.1），然后指定爸爸节点为当前节点进行下一轮处理。
左旋右旋编码实现
以左旋为例，如下图和代码所示，虽然我的写的左旋代码很乱，但是只要知道修改了下图中红色标记的点的某几个指针（左子树、右子树、父节点），而且你也知道修改后的应该指向哪，那这个左旋就应该差不多了，编码的时候注意null，然后就实现了左旋代码。
/**
* 左旋
*
* @param x <br>
* 图片：https://www.processon.com/view/link/5ff15f05e0b34d19e4f880f1
*/
private void leftRotate(Node x) {
if (x == null) {
return;
}
// 记录父节点
Node parent = x.getParent();
// 记录X节点的左子树和右子树
Node xl = x.getLeft();
Node xr = x.getRight();
// ---> 修改父节点的指针
if (null != parent) {
if (x == parent.left) {
parent.left = xr;
} else {
parent.right = xr;
}
} else {
// parent=null表示为根
this.root = xr;
xr.parent = null;
}
// ---> 修改x节点的指针
// 修改左子树(不需要修改)
// 修改右子树
if (xr != null) {
x.right = xr.left;
}
// 修改父节点
x.parent = xr;
// ---> 修改xl节点的指针（不需要修改）
// ---> 修改xr节点的指针
if (xr != null) {
// 修改左子树
xr.left = x;
// 修改右子树(不需要修改)
// 修改父节点
if (null != parent) {
xr.parent = parent;
}
}
// ---> 修改xrl节点的指针
// 修改左子树(不需要修改)
// 修改右子树(不需要修改)
// 修改父节点
if (xr.left != null) {
xr.left.parent = x;
}
}代码
Node节点
代码语言：javascript复制package myredblacktree;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
/**
* @author chaird
* @create 2021-01-03 13:46 <br>
* 红黑树节点
*/
@Data
@AllArgsConstructor
@NoArgsConstructor
public class Node<K extends Comparable<K>, V> {
public Node(K key, V value) {
this.key = key;
this.value = value;
}
// 父节点
Node parent;
// 左子树
Node left;
// 右子树
Node right;
// 颜色，红色为true,黑色为false
Boolean color;
// key
K key;
// vale
V value;
@Override
public String toString() {
return "Node{" ", color=" color ", key=" key ", value=" value '}';
}
}红黑树实体类
代码语言：javascript复制package myredblacktree;
import lombok.Data;
/**
* @author chaird
* @create 2021-01-03 13:52<br>
* 红黑树
*/
@Data
public class RBTree<K extends Comparable<K>, V> {
// 根节点
private Node root;
// 定义红黑树常量
private static final boolean RED = true;
private static final boolean BLACK = false;
/**
* 当前节点是否是红色
*
* @param node
* @return
*/
private Boolean isRed(Node node) {
if (null != node) {
return node.getColor() == RED;
}
return false;
}
/**
* 当前节点是否是黑色
*
* @param node
* @return
*/
private Boolean isBlack(Node node) {
if (null != node) {
return node.getColor() == BLACK;
}
return false;
}
/**
* 设置节点为红色
*
* @param node
*/
private void setRed(Node node) {
if (null != node) {
node.setColor(RBTree.RED);
}
}
/**
* 设置节点为黑色
*
* @param node
*/
private void setBlack(Node node) {
if (null != node) {
node.setColor(RBTree.BLACK);
}
}
/**
* 左旋
*
* @param x <br>
* 图片：https://www.processon.com/view/link/5ff15f05e0b34d19e4f880f1
*/
private void leftRotate(Node x) {
if (x == null) {
return;
}
// 记录父节点
Node parent = x.getParent();
// 记录X节点的左子树和右子树
Node xl = x.getLeft();
Node xr = x.getRight();
// ---> 修改父节点的指针
if (null != parent) {
if (x == parent.left) {
parent.left = xr;
} else {
parent.right = xr;
}
} else {
// parent=null表示为根
this.root = xr;
xr.parent = null;
}
// ---> 修改x节点的指针
// 修改左子树(不需要修改)
// 修改右子树
if (xr != null) {
x.right = xr.left;
}
// 修改父节点
x.parent = xr;
// ---> 修改xl节点的指针（不需要修改）
// ---> 修改xr节点的指针
if (xr != null) {
// 修改左子树
xr.left = x;
// 修改右子树(不需要修改)
// 修改父节点
if (null != parent) {
xr.parent = parent;
}
}
// ---> 修改xrl节点的指针
// 修改左子树(不需要修改)
// 修改右子树(不需要修改)
// 修改父节点
if (xr.left != null) {
xr.left.parent = x;
}
}
/**
* 右旋
*
* @param x <br>
* 图片：https://www.processon.com/view/link/5ff1660807912977bede44d5
*/
private void rightRotate(Node x) {
if (null == x) {
return;
}
// 记录父节点
Node parent = x.getParent();
// 记录X节点的左子树和右子树
Node xl = x.getLeft();
Node xr = x.getRight();
// ---> 修改父节点的指针
if (null != parent) {
if (x == parent.left) {
parent.left = xl;
} else {
parent.right = xl;
}
} else {
// parent=null表示为根
this.root = xl;
xl.parent = null;
}
// ---> 修改X节点的指针
// 修改左子树
if (xl != null) {
x.left = xl.right;
}
// 修改右子树(不需要修改)
// 修改父节点
x.parent = xl;
// ---> 修改xl节点的指针
// 修改左子树(不需要修改)
// 修改右子树
xl.right = x;
// 修改父节点
xl.parent = parent;
// ---> 修改XR节点的指针(不需要修改)
// ---> 修改XLR节点的指针
// 修改左子树(不需要修改)
// 修改右子树(不需要修改)
// 修改父节点
if (xl.right != null) {
xl.parent = x;
}
}
public void insert(K key, V value) {
Node node = new Node(key, value);
// 新阶段一定是红色
node.setColor(RED);
insert(node);
}
private void insert(Node node) {
// 第一步：查找当前的node的父节点
Node parent = null;
Node x = this.root;
while (x != null) {
parent = x;
int cmp = node.getKey().compareTo(x.getKey());
if (cmp > 0) {
x = x.getRight();
} else if (cmp < 0) {
x = x.getLeft();
} else if (cmp == 0) {
x.setValue(node.getValue());
return;
}
}
node.setParent(parent);
// 判断node是parent的左子树还是右子树
if (parent != null) {
int cmp = node.getKey().compareTo(parent.getKey());
if (cmp > 0) {
parent.setRight(node);
} else {
parent.setLeft(node);
}
} else {
this.root = node;
}
// 需要调用红黑树平衡的方法
insertFixUp(node);
}
// 修复红黑树(复杂)
/**
* 插入后修复红黑树平衡的方法<br>
* 情景1：红黑树为空树，将根节点染色为黑色。 <br>
* 情景2：插入节点的key已经存在（不需要处理） <br>
* 情景3：插入节点的父节点为黑色（因为插入的的为红色，黑色节点没有变化，所以红黑树依然平衡，所以不需要处理） <br>
* 情景4：插入节点的父节点为红色（复杂） 情景4-1：叔叔节点存在。并且为红色(父-叔 双红)。将爸爸和叔叔染色为黑色，将爷爷染色为红色，并且在以爷爷节点为当前节点，进行下一轮处理
* 情景4-2：叔叔节点不存在，或者为黑色。父节点为爷爷节点的左子树 <br>
* 情景4-2-1：插入节点为其父节点的左子节点（LL情景）。将爸爸染色为黑色，将爷爷染色为红色，然后以爷爷节点右旋，就结束了
* 情景4-2-2：插入节点为其父节点的右子节点（LR情景）。以爸爸节点进行一次左旋，得到LL双红的情景（4.2.1），然后指定爸爸节点为当前节点进行下一轮处理
* 情景4-3：叔叔节点不存在，或者为黑色。父节点为爷爷节点的右子树 <br>
* 情景4-3-1：插入节点为其父节点的右子节点（RR情景）。将爸爸染色为黑色，将爷爷染色为红色，然后以爷爷节点左旋，就结束了
* 情景4-3-2：插入节点为其父节点的左子节点（RR情景）。以爸爸节点进行一次右旋，得到RR双红的情景（4.3.1），然后指定爸爸节点为当前节点进行下一轮处理
*
* @param node
*/
private void insertFixUp(Node node) {
// 情景1：红黑树为空树，将根节点染色为黑色。
if (this.root == node) {
setBlack(node);
}
// 情景2：插入节点的key已经存在（不需要处理） (走不到这里)
// 情景3：插入节点的父节点为黑色（因为插入的的为红色，黑色节点没有变化，所以红黑树依然平衡，所以不需要处理） <br>
if (node.getParent() != null && isBlack(node.getParent())) {
return;
}
// 情景4：插入节点的父节点为红色（复杂）
if (node.getParent() != null && isRed(node.getParent())) {
Node parent = node.getParent();
Node gParent = parent.getParent();
Node uncle = null;
if (parent == gParent.left) {
// 爸爸是爷爷的左子树
uncle = gParent.right;
} else {
// 爸爸是爷爷的右子树
uncle = gParent.left;
}
// 情景4-1：叔叔节点存在。并且为红色(父-叔 双红)。将爸爸和叔叔染色为黑色，将爷爷染色为红色，并且在以爷爷节点为当前节点，进行下一轮处理
if (null != uncle && isRed(uncle)) {
setBlack(parent);
setBlack(uncle);
setRed(gParent);
insertFixUp(gParent);
return;
}
// 情景4-2：叔叔节点不存在，或者为黑色。父节点为爷爷节点的左子树
if (null == uncle || isBlack(uncle)) {
if (parent == gParent.left) {
// 情景4-2-1：插入节点为其父节点的左子节点（LL情景）。将爸爸染色为黑色，将爷爷染色为红色，然后以爷爷节点右旋，就结束了
if (node == parent.left) {
setBlack(parent);
setRed(gParent);
rightRotate(gParent);
return;
} else {
leftRotate(parent);
insertFixUp(parent);
return;
}
}
}
// 情景4-3：叔叔节点不存在，或者为黑色。父节点为爷爷节点的右子树
if (null == uncle || isBlack(uncle)) {
if (parent == gParent.right) {
if (node == parent.right) {
setBlack(parent);
setRed(gParent);
leftRotate(gParent);
return;
} else {
rightRotate(parent);
insertFixUp(parent);
return;
}
}
}
}
}
}打印红黑树工具类（针对本文）
参考于：按照树形结构直观地打印出一棵二叉树(Java) - 点点爱梦 - 博客园
代码语言：javascript复制package myredblacktree;
/**
* @author chaird
* @create 2021-01-03 10:21
*/
public class TreeOperation {
/*
树的结构示例：
1
/
2 3
/ /
4 5 6 7
*/
// 用于获得树的层数
public static int getTreeDepth(Node root) {
return root == null ? 0 : (1 Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
}
private static void writeArray(
Node currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
// 保证输入的树不为空
if (currNode == null) return;
// 先将当前节点保存到二维数组中
// res[rowIndex][columnIndex] = String.valueOf(currNode.value);
//加颜色
res[rowIndex][columnIndex] =
String.valueOf(currNode.value "-" (currNode.color ? "红" : "黑") "");
// 计算当前位于树的第几层
int currLevel = ((rowIndex 1) / 2);
// 若到了最后一层，则返回
if (currLevel == treeDepth) return;
// 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
int gap = treeDepth - currLevel - 1;
// 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
if (currNode.left != null) {
res[rowIndex 1][columnIndex - gap] = "/";
writeArray(currNode.left, rowIndex 2, columnIndex - gap * 2, res, treeDepth);
}
// 对右儿子进行判断，若有右儿子，则记录相应的""与右儿子的值
if (currNode.right != null) {
res[rowIndex 1][columnIndex gap] = "\";
writeArray(currNode.right, rowIndex 2, columnIndex gap * 2, res, treeDepth);
}
}
public static void show(Node root) {
if (root == null) System.out.println("EMPTY!");
// 得到树的深度
int treeDepth = getTreeDepth(root);
// 最后一行的宽度为2的（n - 1）次方乘3，再加1
// 作为整个二维数组的宽度
int arrayHeight = treeDepth * 2 - 1;
int arrayWidth = (2 << (treeDepth - 2)) * 3 1;
// 用一个字符串数组来存储每个位置应显示的元素
String[][] res = new String[arrayHeight][arrayWidth];
// 对数组进行初始化，默认为一个空格
for (int i = 0; i < arrayHeight; i ) {
for (int j = 0; j < arrayWidth; j ) {
res[i][j] = " ";
}
}
// 从根节点开始，递归处理整个树
// res[0][(arrayWidth 1)/ 2] = (char)(root.val '0');
writeArray(root, 0, arrayWidth / 2, res, treeDepth);
// 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
for (String[] line : res) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < line.length; i ) {
sb.append(line[i]);
if (line[i].length() > 1 && i <= line.length - 1) {
i = line[i].length() > 4 ? 2 : line[i].length() - 1;
}
}
System.out.println(sb.toString());
}
}
}测试类
代码语言：javascript复制package myredblacktree;
/**
* @author chaird
* @create 2021-01-03 13:50
*/
public class Main {
public static void main(String[] args) {
RBTree<Integer, Object> tree = new RBTree();
tree.insert(1, 1);
tree.insert(2, 2);
tree.insert(3, 3);
tree.insert(4, 4);
tree.insert(5, 5);
tree.insert(6, 6);
tree.insert(7, 7);
tree.insert(8, 8);
TreeOperation.show(tree.getRoot());
}
}参考
视频资料：java语言手写红黑树，零基础教学，150分钟带你完全掌握红黑树！_哔哩哔哩_bilibili
- 从第45分钟以后开始看
- 视频里的代码我跟着敲，但是最后报错了，应该是我自己的问题，看的不仔细，然后理解了自己重新写，就是这篇博客
红黑树动态模拟：Red/Black Tree Visualization
打印一颗红黑树：按照树形结构直观地打印出一棵二叉树(Java) - 点点爱梦 - 博客园
