文章目录
红黑树代码只实现了插入和删除，查找与二叉查找树相同。直接运行RBTreeTest即可测试红黑树。
红黑树代码
public class RBTree<T extends Comparable<T>> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node<T> root;
public Node<T> getRoot() {
return root;
}
public void insert(T key) {
// 根节点，直接插入
if (root == null) {
root = new Node<>(key);
} else {
// 当前循环节点
Node<T> x = root;
// 最后一个循环的节点
Node<T> p = x;
while (x != null) {
p = x;
int tmp = key.compareTo(x.key);
// key比x大，插入到右子树
if (tmp > 0) {
x = x.right;
} else if (tmp < 0) {
// key比x小，插入到左子树
x = x.left;
} else {
// 相等节点进行替换，只不过目前没有不需要设置值，直接返回
return;
}
}
// p为待插入节点的父节点
Node<T> node = new Node<>(key);
if (key.compareTo(p.key) > 0) {
p.right = node;
} else {
p.left = node;
}
node.parent = p;
// 进行插入平衡
insertBalance(node);
}
// 根节点染黑
setBlack(root);
}
private void insertBalance(Node<T> x) {
for (; ; ) {
// 情景1：x节点为root，直接返回
if (parentOf(x) == null) {
root = x;
return;
}
// 情景2：父节点是黑色 ==> 不用处理
if (isBlack(parentOf(x))) {
return;
}
// 情景3：父节点是红色，叔节点是红色 ==> 父节点和叔节点变成黑色，祖父节点变红，x指向祖父节点
if (isRed(uncleOf(x))) {
setBlack(parentOf(x));
setBlack(uncleOf(x));
setRed(gParentOf(x));
x = gParentOf(x);
}
// 情景4：父节点红色，叔节点黑色
else {
// p是祖父节点的左子节点
if (parentOf(x) == gParentOf(x).left) {
// 情景4.1：x是p的右子节点
if (x == parentOf(x).right) {
// 以p为节点进行左旋，并且x指向p
rotateLeft(x = parentOf(x));
}
// 情景4.2：x是p的左子节点 => p变黑，x祖父变红，祖父右旋
setBlack(parentOf(x));
setRed(gParentOf(x));
rotateRight(gParentOf(x));
} else {
// p是祖父节点的右子节点
// 情景4.1：x是p的左子节点
if (x == parentOf(x).left) {
// 以p为节点进行右旋，并且x指向p
rotateRight(x = parentOf(x));
}
// 情景4.2：x是p的右子节点 => p变黑，x祖父变红，祖父左旋
setBlack(parentOf(x));
setRed(gParentOf(x));
rotateLeft(gParentOf(x));
}
}
}
}
public void delete(T key) {
// 指向待删除节点
Node<T> x = root;
while (x != null) {
int tmp = key.compareTo(x.key);
if (tmp > 0) {
// 继续寻找右子树
x = x.right;
}
// 继续寻找左子树
else if (tmp < 0) {
x = x.left;
}
// 寻找到节点
else {
// 如果x节点存在2个节点，则寻找前驱节点替换x节点，并且删除前驱节点
if (x.left != null && x.right != null) {
Node<T> predecessor = predecessor(x.left);
// 前驱节点替换x节点
x.key = predecessor.key;
// 删除前驱节点
x = predecessor;
}
break;
}
}
// 如果未找到删除节点，返回
if (x == null) {
return;
}
// 待删除节点只会存在3中情景：
// 1、x存在一个子节点，此时肯定是x黑色，子节点红，此时只需要用子节点替换x并且染黑即可，不需要再平衡
// 2、x不存在子节点，并且是红色，此时直接删除x节点，不需要再平衡
// 3、x不存在节点，并且是黑色，此时删除x节点会影响黑高，需要进行再平衡
// 执行到这一步，x最多存在一个子节点
// 如果x存在一个子节点，使用子节点替换x
if (x.left != null || x.right != null) {
Node<T> p = x.left == null ? x.right : x.left;
// 使用子节点替换x，p颜色染成x颜色
p.parent = x.parent;
p.color = x.color;
if (parentOf(x) == null) {
root = p;
} else if (x == parentOf(x).left) {
parentOf(x).left = p;
} else {
parentOf(x).right = p;
}
// 释放x
x.left = x.right = x.parent = null;
} else {
// 如果x是黑色，先进行平衡，再删除x节点
if (isBlack(x)) {
deleteBalance(x);
}
// 删除x节点
if (parentOf(x) == null) {
root = null;
} else if (x == parentOf(x).left) {
parentOf(x).left = null;
} else {
parentOf(x).right = null;
}
x.left = x.right = x.parent = null;
}
// 根节点染黑
setBlack(root);
}
private void deleteBalance(Node<T> x) {
while (x != null) {
// 情景1：x是根节点，直接返回
if (parentOf(x) == null) {
return;
}
Node<T> s, sl, sr, p;
// 情景2：s是红色 ==> s黑，p红，p左旋或者右旋
if (isRed(s = siblingOf(x))) {
setBlack(s);
setRed(p = parentOf(x));
if (x == p.left) {
rotateLeft(p);
} else {
rotateRight(p);
}
}
// 执行到这一步，x和s肯定都是黑色
// 情景3：s黑色，sl和sr黑色，p黑 ==> s染红，x指向p继续平衡
if (isBlack(p = parentOf(x)) && isBlack(s = siblingOf(x)) &&
isBlack(leftOf(s)) && isBlack(rightOf(s))) {
setRed(s);
x = p;
}
// 情景4：s黑，sl黑sr黑色，p红 ==> s红，p黑
else if (isRed(p = parentOf(x)) && isBlack(s = siblingOf(x)) &&
isBlack(leftOf(s)) && isBlack(rightOf(s))) {
setRed(s);
setBlack(p);
return;
} else {
// 能执行到这一步，x和s肯定黑色，p可以是任意颜色，sl和sr不全是黑色
// x是父节点的左节点
if (x == parentOf(x).left) {
// 情景5：sl红，sr黑 ==> sl黑，s红，s右旋
s = siblingOf(x);
if (isRed(sl = leftOf(s)) && isBlack(rightOf(s))) {
setBlack(sl);
setRed(s);
rotateRight(s);
}
// 情景6：sr红 ==> s与p颜色互换，sr黑，p左旋
setColor(s = siblingOf(x), (p = parentOf(x)).color);
setBlack(p);
setBlack(rightOf(s));
rotateLeft(p);
return;
} else {
// x是父节点的右节点
// 情景5：sr红，sl黑 ==> sr黑，s红，s左旋
s = siblingOf(x);
if (isRed(sr = rightOf(s)) && isBlack(leftOf(s))) {
setBlack(sr);
setRed(s);
rotateLeft(s);
}
// 情景6：sl红 ==> s与p颜色互换，sl黑，p右旋
setColor(s = siblingOf(x), (p = parentOf(x)).color);
setBlack(p);
setBlack(leftOf(s));
rotateRight(p);
return;
}
}
}
}
/**
* 为了方便与动画对比，使用前继节点
*
* @param x
* @return
*/
private Node<T> predecessor(Node<T> x) {
if (x == null) {
return null;
}
while (x.right != null) {
x = x.right;
}
return x;
}
/**
* 左旋
* x r
* / \ / \
* a r => x rr
* / \ / \
* rl rr a rl
*
* @param x 待旋转节点
*/
private void rotateLeft(Node<T> x) {
Node<T> r = x.right;
// 第1步：x与rl建立关联
x.right = r.left;
if (r.left != null) {
r.left.parent = x;
}
// 第2步：r父节点与x父节点建立关联
r.parent = x.parent;
if (x.parent == null) {
root = r;
} else if (x == x.parent.left) {
parentOf(x).left = r;
} else {
parentOf(x).right = r;
}
// 第3步：x与r建立关联
x.parent = r;
r.left = x;
}
/**
* 右旋
* x l
* / \ / \
* l a => ll x
* / \ / \
* ll lr lr a
*
* @param x 待旋转节点
*/
private void rotateRight(Node<T> x) {
Node<T> l = x.left;
// 第1步：x与lr建立关联
x.left = l.right;
if (l.right != null) {
l.right.parent = x;
}
// 第2步：l父节点与x父节点建立关联
l.parent = x.parent;
if (x.parent == null) {
root = l;
} else if (x == x.parent.left) {
parentOf(x).left = l;
} else {
parentOf(x).right = l;
}
// 第3步：x与l建立关联
x.parent = l;
l.right = x;
}
private boolean isRed(Node<T> x) {
return x != null && RED == x.color;
}
/**
* 判断节点是否为黑色，注意：空节点也算作是黑色
*
* @param x 节点
* @return 是否黑色
*/
private boolean isBlack(Node<T> x) {
return x == null || BLACK == x.color;
}
private void setColor(Node<T> x, boolean color) {
if (x != null) {
x.color = color;
}
}
private void setRed(Node<T> x) {
if (x != null) {
x.color = RED;
}
}
private void setBlack(Node<T> x) {
if (x != null) {
x.color = BLACK;
}
}
private Node<T> leftOf(Node<T> x) {
return x == null ? null : x.left;
}
private Node<T> rightOf(Node<T> x) {
return x == null ? null : x.right;
}
private Node<T> siblingOf(Node<T> x) {
if (parentOf(x) == null) {
return null;
}
if (x == parentOf(x).left) {
return parentOf(x).right;
} else {
return parentOf(x).left;
}
}
private Node<T> uncleOf(Node<T> x) {
if (gParentOf(x) == null) {
return null;
}
if (parentOf(x) == gParentOf(x).left) {
return gParentOf(x).right;
} else {
return gParentOf(x).left;
}
}
private Node<T> gParentOf(Node<T> x) {
return parentOf(parentOf(x));
}
private Node<T> parentOf(Node<T> x) {
return x == null ? null : x.parent;
}
static class Node<T extends Comparable<T>> {
T key;
boolean color;
Node<T> parent;
Node<T> left;
Node<T> right;
public Node(T key) {
this.key = key;
color = RED;
}
}
}
红黑树打印代码
public class TreeOperation {
/*
树的结构示例：
1
/ \
2 3
/ \ / \
4 5 6 7
*/
// 用于获得树的层数
public static int getTreeDepth(RBTree.Node root) {
return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
}
private static void writeArray(RBTree.Node currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
// 保证输入的树不为空
if (currNode == null) return;
// 0、默认无色
// res[rowIndex][columnIndex] = String.valueOf(currNode.getValue());
//1、颜色表示
if (!currNode.color) {//黑色，加色后错位比较明显
res[rowIndex][columnIndex] = ("\033[30;3m" + currNode.key + "\033[0m");
} else {
res[rowIndex][columnIndex] = ("\033[31;3m" + currNode.key + "\033[0m");
}
//2、R,B表示
// res[rowIndex][columnIndex] = String.valueOf(currNode.getValue()+"-"+(currNode.isColor()?"B":"R")+"");
// 计算当前位于树的第几层
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(RBTree.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());
}
}
}
红黑树测试代码
public class RBTreeTest {
public static void main(String[] args) {
//新增节点
// insertOpt();
//删除节点
deleteOpt();
}
/**
* 插入操作
*/
public static void insertOpt() {
Scanner scanner = new Scanner(System.in);
RBTree<Integer> rbt = new RBTree<>();
while (true) {
System.out.println("请输入你要插入的节点:");
String key = scanner.next();
System.out.println();
rbt.insert(Integer.parseInt(key));
TreeOperation.show(rbt.getRoot());
}
}
/**
* 删除操作
*/
public static void deleteOpt() {
RBTree<Integer> rbt = new RBTree<>();
//预先造10个节点（1-10）
for (int i = 1; i <= 15; i++) {
rbt.insert(i);
}
TreeOperation.show(rbt.getRoot());
//以下开始删除
Scanner scanner = new Scanner(System.in);
while (true) {
System.out.println("请输入你要删除的节点:");
String key = scanner.next();
System.out.println();
rbt.delete(Integer.parseInt(key));
TreeOperation.show(rbt.getRoot());
}
}
}