1. 红黑树的定义
红黑树是一颗二叉查找树，且具有如下特性：
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点。
红黑树插入操作的实现依赖于下图,读懂了此图实现起来就比较简单了
package com.example.demo;
/**
* 红黑树实现
* @author
*
*/
public class RBTree {
RBTreeNode root;
private final boolean RED = false;
private final boolean BLACK = true;
public RBTreeNode query(int key) {
RBTreeNode tmp = root;
while (tmp != null) {
if (tmp.getKey() == key)
return tmp;
else if (tmp.getKey() > key)
tmp = tmp.getLeft();
else
tmp = tmp.getRight();
}
return null;
}
/**
* 搜索二叉树插入代码 插入总是红节点
* @param key
*/
public void insert(int key) {
RBTreeNode node = new RBTreeNode(key);
if (root == null) {
root = node;
node.setColor(BLACK);
return;
}
RBTreeNode parent = root;
RBTreeNode son = null;
if (key <= parent.getKey()) {
son = parent.getLeft();
} else {
son = parent.getRight();
}
//find the position
while (son != null) {
parent = son;
if (key <= parent.getKey()) {
son = parent.getLeft();
} else {
son = parent.getRight();
}
}
if (key <= parent.getKey()) {
parent.setLeft(node);
} else {
parent.setRight(node);
}
node.setParent(parent);
//调整节点
adjustRBTree(node);
}
/**
* 左旋代码 参考上一篇AVL
* @param node
*/
private void leftRotate(RBTreeNode node) {
RBTreeNode right = node.getRight();
RBTreeNode parent = node.getParent();
if (parent == null) {
root = right;
right.setParent(null);
} else {
if (parent.getLeft() != null && parent.getLeft() == node) {
parent.setLeft(right);
} else {
parent.setRight(right);
}
right.setParent(parent);
}
node.setParent(right);
node.setRight(right.getLeft());
if (right.getLeft() != null) {
right.getLeft().setParent(node);
}
right.setLeft(node);
}
/**
* 右旋代码 参考上一篇AVL
* @param node
*/
private void rightRotate(RBTreeNode node) {
RBTreeNode left = node.getLeft();
RBTreeNode parent = node.getParent();
if (parent == null) {
root = left;
left.setParent(null);
} else {
if (parent.getLeft() != null && parent.getLeft() == node) {
parent.setLeft(left);
} else {
parent.setRight(left);
}
left.setParent(parent);
}
node.setParent(left);
node.setLeft(left.getRight());
if (left.getRight() != null) {
left.getRight().setParent(node);
}
left.setRight(node);
}
/**
* 调整插入红黑树代码
* @param node
*/
private void adjustRBTree(RBTreeNode node) {
RBTreeNode fatherNode=null,gradeFatherNode=null,uncleNode=null;
/**
* 红黑树停止调整的条件是父节点是空节点或者父节点的颜色不是红色
*/
while(((fatherNode=node.getParent())!=null)&&(fatherNode.getColor()==RED)){
gradeFatherNode=fatherNode.getParent();
/**
*如果父节点在祖父节点的左侧
*/
if(fatherNode==gradeFatherNode.getLeft()){
uncleNode=gradeFatherNode.getRight();
//当叔叔节点非空而且是红色 调整父节点 叔叔节点为黑色 祖父节点为红色 并且将祖父节点继续循环
if((uncleNode!=null)&&uncleNode.getColor()==RED){
fatherNode.setColor(BLACK);
uncleNode.setColor(BLACK);
gradeFatherNode.setColor(RED);
node=fatherNode;
continue;
}
//如果当前节点为父节点的右节点 则当前二叉树成为了LR型二叉树 将父节点左旋变成LL
if(node==fatherNode.getRight()){
leftRotate(fatherNode);
RBTreeNode tmp=fatherNode;
fatherNode=node;
node=tmp;
}
//LL型二叉树 进行右旋 并且将父节点设为黑色 祖父节点设为红色
fatherNode.setColor(BLACK);
gradeFatherNode.setColor(RED);
rightRotate(gradeFatherNode);
}else{
/**
* 父节点在祖父节点右侧
*/
uncleNode=gradeFatherNode.getLeft();
//当叔叔节点非空而且是红色 调整父节点 叔叔节点为黑色 祖父节点为红色 并且将祖父节点继续循环
if((uncleNode!=null)&&uncleNode.getColor()==RED){
fatherNode.setColor(BLACK);
uncleNode.setColor(BLACK);
gradeFatherNode.setColor(RED);
node=fatherNode;
continue;
}
//如果当前节点为父节点的左节点 则当前二叉树成为了RL型二叉树 将父节点右旋变成RR
if(node==fatherNode.getLeft()){
rightRotate(fatherNode);
RBTreeNode tmp=fatherNode;
fatherNode=node;
node=tmp;
}
//RR型二叉树 进行左旋 并且将父节点设为黑色 祖父节点设为红色
fatherNode.setColor(BLACK);
gradeFatherNode.setColor(RED);
leftRotate(gradeFatherNode);
}
}
node.setColor(BLACK);
}
}
/**
*
* @author
*红黑二叉树节点定义
*/
class RBTreeNode {
private final boolean RED = false;
private final boolean BLACK = true;
private int key;
private boolean color;
private RBTreeNode left;
private RBTreeNode right;
private RBTreeNode parent;
public RBTreeNode(int key) {
this.key = key;
this.color = RED;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public boolean getColor() {
return color;
}
public void setColor(boolean color) {
this.color = color;
}
public RBTreeNode getLeft() {
return left;
}
public void setLeft(RBTreeNode left) {
this.left = left;
}
public RBTreeNode getRight() {
return right;
}
public void setRight(RBTreeNode right) {
this.right = right;
}
public RBTreeNode getParent() {
return parent;
}
public void setParent(RBTreeNode parent) {
this.parent = parent;
}
@Override
public String toString() {
return "RBTreeNode{" +
",key=" + key +
", color=" + color +
'}';
}
}
参考: 1、https://www.jianshu.com/p/e136ec79235c 2、https://blog.csdn.net/qq_41854763/article/details/82694873
评论区