Java之红黑树
1、简介
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但 对之进行平衡的代价较低， 其平均统计性能要强于 AVL 。
由于每一棵红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。
2、红黑树的特点
红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。 在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
- 性质一:每个节点要么是黑色，要么是红色
- 性质二:根节点是黑色
- 性质三:每个叶子节点（NIL即NULL）
- 性质四:每个红色节点的两个子节点一定是黑色
- 性质五:任意一节点到两个子节点的路径都包含相同的黑节点，俗称黑高
如下图:
3、插入和删除造成不平衡的修复方法
当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。
为了保持红黑树的性质，我们可以对相关结点做一系列的调整，通过对树进行旋转（例如左旋和右旋操作），即修改树中某些结点的颜色及指针结构，以达到对红黑树进行插入、删除结点等操作时，红黑树依然能保持它特有的性质（五点性质）。
3.1 变色
所谓变色当然是红黑互换颜色，当然根节点还是黑色。
3.2 右旋
下图我们可以发下在右子树有两个红色节点相连，这不符合上面提过的性质5，我们需要对它变色右旋。
第一步：先让L和LL变成相反的颜色，第二步以L的位置为旋转点让root的左孩子变成LL，L变成RL的右孩子，如果LLR有右孩子，LL的右孩子变成L的左孩子。此时，已恢复红黑树的平衡了。
右旋代码如下：
/**
*右旋方法
*右旋示意图
*
* P P
* | |
* y x
* / -------> /
* x ry lx y
* / /
* lx ly ly ry
*
* 1.将y的左子节点指向x的右子节点，并更新x的右子节点的父亲节点为y
* 2.当y的父节点不为空时，更新x的父节点为y的父节点，更新y的父节点指定子节点为x
* 3.更新y的父节点为x,更新x的右子节点为y
*/
private void rightRotate(RBNode y){
RBNode x=y.left;
//1.将y的左子节点指向x的右子节点，并更新x的右子节点的父亲节点为y
y.left=x.right;
if(x.right!=null){
x.right.parent=y;
}
//2.当y的父节点不为空时，更新x的父节点为y的父节点，更新y的父节点指定子节点为x
if(y.parent!=null){
x.parent=y.parent;
if(y == y.parent.left){//判断是否为父节点左孩子
y.parent.left=x;
}else{
y.parent.right=x;
}
}else{//y为根节点
this.root=x;
this.root.parent=null;
}
//3.更新y的父节点为x,更新x的右子节点为y
y.parent=x;
x.right=y;
}
3.3 左旋
可以看到下图RR双红，首先我们还是先将LR和其父节点L变色，然后左旋恢复红黑树平衡
第一步变色
第二步左旋 让root的左孩子变为LR 同时L变成LR的左孩子，如果LR有左孩子，需变为L右孩子。
代码实现如下:
/**
* 左旋方法
* 左旋示意图 左旋x结点
* p p
* | |
* x ----> y
* / /
* lx y x ry
* / /
* ly ry lx ly
*
*/
private void leftRotate(RBNode x){
RBNode y=x.right;
//1.将x的右子结点指向y的左子结点（ly）,将y的左子节点父节点更新为x
x.right=y.left;
if(y.left!=null){
y.left.parent=x;
}
//2.当x的父节点不为null时,更新y的父节点为x的父节点指定子树（当时x子树的位置） 指定为y
if(x.parent != null){
y.parent=x.parent;
if(x==x.parent.left){
x.parent.left=y;
}else{
x.parent.right=y;
}
}else{
this.root=y;
this.root.parent=null;
}
//3.将x的父节点更新为y,将y的左子结点更新为x
x.parent=y;
y.left=x;
}
4、完整实现红黑树
/**
* TODO
*
* @author DELL
* @version 1.0
* @since 2022-04-24 10:06:39
* 性质一:每个节点要么是黑色，要么是红色
* 性质二:根节点是黑色
* 性质三:每个叶子节点（NIL即NULL）
* 性质四:每个红色节点的两个子节点一定是黑色
* 性质五:任意一节点到两个叶子节点的路径都包含相同的黑节点，俗称黑高
*
* 变色：结点的颜色由红变黑或由黑变红
* 左旋：以某个结点作为作为支点（旋转节点），其左子结点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的右子节点，右子节点保持不变
* 右旋：以某个结点作为作为支点（旋转节点），其右子结点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的左子节点，左子节点保持不变
*
* 创建RBtree,定义颜色
* 创建RBNode
* 辅助定义方法:parentOf(node),isRed(node),setRed(node),setBlack(node),inOrderPrint()
* 左旋方法定义:leftRotate(node)
* 右旋方法定义:rightRotate(node)
* 公开插入接口定义方法定义:insert(K key,V value)
* 内部插入接口方法定义:insert(RBNode node)
* 修正插入导致红黑树失衡的方法定义：insertFixUp(RBNode node)
*/
public class NewRBTree<K extends Comparable<K>,V>{
private final boolean RED=true;
private final boolean BLACK=false;
private Node<K, V> root;
class Node<K extends Comparable<K>,V>{
private K key;
private V value;
private boolean color;
private Node<K, V> parent;
private Node<K, V> left;
private Node<K, V> right;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
public boolean isColor() {
return color;
}
public void setColor(boolean color) {
this.color = color;
}
public Node getLeft() {
return this.left;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public Node<K, V> getParent() {
return parent;
}
public Node<K, V> getRight() {
return right;
}
}
/**
* 左旋方法
* 左旋示意图 左旋x结点
* p p
* | |
* x ----> y
* / /
* lx y x ry
* / /
* ly ry lx ly
*
*/
private void leftRotate(Node<K, V> x){
Node<K, V> y=x.right;
x.right=y.left;
if(x.parent!=null){
y.parent=x.parent;
if(x==x.parent.left){
x.parent.left=y;
}else{
x.parent.right=y;
}
}else{
this.root=y;
y.parent=null;
}
x.parent=y;
y.left=x;
}
/**
*右旋方法
*右旋示意图
*
* P P
* | |
* y x
* / -------> /
* x ry lx y
* / /
* lx ly ly ry
*/
private void RightRotate(Node<K, V> y){
// 1.将x的右子节点指向y的左子节点，并更新y的左子节点的父亲节点为x
Node<K, V> x=y.left;
y.left=x.right;
// 2.当y的父节点不为空时，更新y的父节点为x的父节点
if(y.parent!=null){
x.parent=y.parent;
//判断y是其父节点的左孩子还有右孩子
if(y==y.parent.left){
y.parent.left=x;
}else{
y.parent.right=x;
}
}else{
this.root=x;
x.parent=null;
}
//3.更新y的父节点为x,更新x的右子节点为y
y.parent=x;
x.right=y;
}
//是否是红色
private boolean isRed(Node node){
return node.color==RED;
}
//是否是红色
private boolean isBlack(Node node){
return node.color==BLACK;
}
//返回节点的父亲
private Node<K, V> parentOf(Node node){
return node.parent;
}
//设置红色
private void setRED(Node node){
node.color=RED;
}
//设置黑色
public void setBLACK(Node node){
node.color=BLACK;
}
//添加
public void insert(K key,V value){
Node<K, V> node=new Node<>(key,value);
node.setColor(RED);
insert(node);
}
private void insert(Node<K, V> node){
Node<K, V> newRoot=root;
Node<K, V> parent=null;
while(newRoot!=null){
parent=newRoot;
if(node.key.compareTo(newRoot.key)>0){
newRoot=newRoot.right;
}else if(node.key.compareTo(newRoot.key)<0){
newRoot=newRoot.left;
}else{
newRoot.value=node.value;
return;
}
}
node.parent=parent;
if(parent==null){
this.root=node;
}else if(parent.key.compareTo(node.key)>0){
parent.left=node;
}else{
parent.right=node;
}
insertFixUp(node);//修复红黑树
}
/**
* 插入后修复红黑树平衡的方法
* |---情景1:红黑树为空树
* |---情景2:插入的节点key已经存在
* |---情景3:插入的节点的父节点为黑色
* |---情景4:插入节点的父亲节点为红色
* |---情景4.1:叔叔节点存在，并且为红色(父-叔双红)，将爸爸和叔叔染成黑色，爷爷染成红色，进行下一轮处理
* |---情景4.2:叔叔节点不存在，或者为黑色，父节点为爷爷节点的左子树
* |---情景4.2.1:插入节点为其父节点的左子节点（LL情况），将爸爸染成黑色，将爷爷染成红色然后以爷爷为旋转节点 右旋
* |---情景4.2.2:插入节点为其父节点的右子节点（LR情况），以爸爸节点进行一次左旋，得到LL双红的情景，然后指定爸爸节点为当前节点进行下一轮处理
* |---情景4.3:叔叔节点不存在，或者为黑色，父节点为爷爷节点的右子树
* |---情景4.3.1:插入节点为其父节点的右子节点（RR情况）将爸爸染成黑色，将爷爷染成红色然后以爷爷为旋转节点 左旋
* |---情景4.3.2:插入节点为其父节点的左子节点（RL情况），以爸爸节点进行一次右旋，得到RR双红的情景，然后指定爸爸节点为当前节点进行下一轮处理
*/
private void insertFixUp(Node<K, V> node){
Node parent=node.parent;
this.root.setColor(BLACK);
//情景4:插入节点的父亲节点为红色
if(parent!=null && isRed(parent)){
//情景4.1:叔叔节点存在，并且为红色(父-叔双红)，将爸爸和叔叔染成黑色，爷爷染成红色，进行下一轮处理
Node gParent=parent.parent;
Node uncle=null;
int cmp=gParent.key.compareTo(parent.key);
if(cmp<0){
uncle=gParent.left;
}else if(cmp>0){
uncle=gParent.right;
}
if(uncle!=null && isRed(uncle)){
setBLACK(uncle);
setBLACK(parent);
setRED(gParent);
insertFixUp(node);
return;
}
if((uncle==null || isBlack(uncle)) && cmp>0){
if(parent.key.compareTo(node.key)>0){
setBLACK(parent);
setRED(gParent);
RightRotate(gParent);
return;
}else{
leftRotate(parent);
insertFixUp(parent);
return;
}
}else{
if(parent.key.compareTo(node.key)>0){
RightRotate(parent);
insertFixUp(parent);
return;
}else{
setBLACK(parent);
setRED(gParent);
leftRotate(gParent);
return;
}
}
}
}
//中序打印
public void inOrderPrint(){
if(this.root==null) return;
inOrderPrint(this.root);
}
public Node getRoot(){
return this.root;
}
private void inOrderPrint(Node<K, V> node){
if(node==null) return;
inOrderPrint(node.left);
System.out.println("key:"+node.key+",value:"+node.value);
inOrderPrint(node.right);
}
}
最后再附上验证打印红黑树的类TreeOperation
/**
* TODO
*
* @author DELL
* @version 1.0
* @since 2022-04-22 19:25:39
*/
public class TreeOperation {
/*
树的结构示例：
1
/
2 3
/ /
4 5 6 7
*/
// 用于获得树的层数
public static int getTreeDepth(NewRBTree.Node root) {
return root == null ? 0 : (1 + Math.max(getTreeDepth(root.getLeft()), getTreeDepth(root.getRight())));
}
private static void writeArray(NewRBTree.Node currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
// 保证输入的树不为空
if (currNode == null) return;
// 先将当前节点保存到二维数组中
res[rowIndex][columnIndex] = String.valueOf(currNode.getKey() + "-" + (currNode.isColor() ? "R" : "B") + "");
// 计算当前位于树的第几层
int currLevel = ((rowIndex + 1) / 2);
// 若到了最后一层，则返回
if (currLevel == treeDepth) return;
// 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
int gap = treeDepth - currLevel - 1;
// 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
if (currNode.getLeft() != null) {
res[rowIndex + 1][columnIndex - gap] = "/";
writeArray(currNode.getLeft(), rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
}
// 对右儿子进行判断，若有右儿子，则记录相应的""与右儿子的值
if (currNode.getRight() != null) {
res[rowIndex + 1][columnIndex + gap] = "\";
writeArray(currNode.getRight(), rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
}
}
public static void show(NewRBTree.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());
}
}
}
上一篇：
解决字符的正方形输出问题
下一篇：
一致性哈希算法