红黑树
介绍
jdk8的HashMap中加入了红黑树，然后红黑树就成了万恶之源。
红黑树是一种自平衡的二叉查找树。放松了对平衡的限制，只要求部分达到平衡，不再是严格意义上的平衡二叉树。节点增加了红黑颜色用非严格的平衡来换取增删节点时候旋转次数降低，任何不平衡都会在三次旋转之类解决。因为平衡没有AVL严格，红黑树的查询性能会稍微逊色于AVL树，但是在插入和删除上为了维持平衡的开销要小很多。
基本规则
1.每个节点分为红色或者黑色
2.根节点必为黑色；
3.叶子节点都为黑色，且为null
4.红色节点的两个子节点一定是黑色，不能有两个红色节点相连
5.从任意节点到其每个叶子的所有路径都包含相同的黑色节点
手写代码
红黑树的查和改比较简单，比较复杂的是增和删之后的平衡。
先定义树和节点代码如下：
public class RBTree<T extends Comparable<T>> {
private static final boolean RED = true;
private static final boolean BLACK =false;
//根节点
public TreeNood<T> root;
//定义红黑树的节点
private class TreeNood<T extends Comparable>{
TreeNood<T> left;
TreeNood<T> right;
TreeNood<T> parent;
T value;
String color;
}
}
插入节点
插入节点有三个基本操作，染色，左旋和右旋。染色就是红变黑，黑变红，具体结合场景介绍，此处主要介绍左旋和右旋。
左旋
左旋操作如图：
在这里插入图片描述
实现代码如下图：
private void leftRotate(TreeNood<T> x){
//创建临时节点保存y节点
TreeNood<T> y = x.right;
//y的左儿子变成x的右儿子
x.right = y.left;
//把y的左儿子彻底过继给x
if(y.left != null){
y.left.parent = x;
}
//让y节点取代x的位置，如果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;
}
//此时将x变为y的左孩子
x.parent = y;
y.left = x;
}
右旋
右旋操作如图：
在这里插入图片描述
右旋操作与左旋操作相反，实现代码如下：
private void rightRotate(TreeNood<T> y){
//创建临时节点保存x节点
TreeNood<T> x = y.left;
//x的右儿子变成y的左儿子
y.left = x.right;
//把x的右儿子彻底过继给y
if(x.right != null){
x.right.parent = y;
}
//让x节点取代y的位置，如果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 {
this.root = x;
this.root.parent = null;
}
//此时将y变为x的右孩子
y.parent = x;
x.right = y;
}
插入节点
节点的插入比较简单，寻找插入就可以了，比较复杂的是插入之后的二叉树平衡，插入代码如下(插入后续是平衡)：
插入代码实现如下：
public void insertTreeNode(T value){
TreeNood<T> newNode = new TreeNood<>();
newNode.value = value;
//新节点一定是红色
newNode.color = RED;
//保存父节点，默认为root节点
TreeNood<T> parent = root;
//保存当前节点
TreeNood<T> node = root;
if(parent == null){
newNode.color = BLACK;
root = newNode;
}else{
while (node != null){
parent = node;
int cmp = newNode.value.compareTo(node.value);
if(cmp > 0){
node = node.right;
}else if(cmp == 0){
node.value = value;
return;
}else {
node = node.left;
}
}
newNode.parent = parent;
int cmp = newNode.value.compareTo(parent.value);
if(cmp > 0){
parent.right = newNode;
}else{
parent.left = newNode;
}
fixRBTree(newNode);
}
}
平衡规则如下：
1.红黑树为空树，将插入节点变为根节点，染黑（新插入节点必为红色节点）
2.插入节点的key已存在，无需处理
3.插入节点的父节点是黑色，插入后依旧平衡，无需处理
4.需要做平衡的场景：插入节点的父节点为红色
（1）叔叔节点存在，且为红色。此时将父亲和叔叔节点染黑，将祖父节点染红，然后将祖父节点设置为当前节点，重新平衡。
（2）叔叔节点不存在或者为黑色，父节点为爷爷节点的左子树
① 插入节点为其父节点的左子节点（LL情况），将父节点变为黑色，将祖父节点变为红色，对祖父节点右旋
② 插入节点为其父节点的右子节点（LR情况），将父节点左旋得到①，后续按①操作
（3）叔叔节点不存在或者为黑节点，并且插入节点的父亲节点时祖父节点的右子节点
③ 插入节点为父节点的右子节点（RR情况），将父节点变为黑色，将祖父节点变为红色，对祖父节点左旋
④ 插入节点为父节点的左子节点（RL情况），将父节点右旋，得到③，后续按③操作
调整代码实现如下：
private void fixRBTree(TreeNood<T> node){
root.color = BLACK;
//创建临时节点记录父节点
TreeNood<T> p = node.parent;
//父节点为红色，则一定存在祖父节点，因为根节点必为黑色
if(p != null && p.color == RED){
TreeNood<T> gp = p.parent;
TreeNood<T> u = null;
//如果父亲节点是祖父的左子节点
if(p == gp.left){
//保存叔叔节点
u = gp.right;
//此为（1）场景，叔红
if(u != null && u.color == RED){
//父叔染黑，祖父染红，递归
p.color = BLACK;
u.color = BLACK;
gp.color = RED;
fixRBTree(gp);
return;
}
if(u == null || u.color == BLACK){
//①场景，LL情况，父亲染黑，祖父染红，对祖父右旋
if(node == p.left){
p.color = BLACK;
gp.color = RED;
rightRotate(gp);
return;
}
//②场景，LR情况，父节点左旋，递归
if(node == p.right){
leftRotate(p);
fixRBTree(p);
}
}
}else{
//如果父亲节点是祖父的右子节点
//保存叔叔节点
u = gp.left;
//此为（1）场景
if(u != null && u.color == RED){
//父叔染黑，祖父染红，递归
p.color = BLACK;
u.color = BLACK;
gp.color = RED;
fixRBTree(gp);
return;
}
if(u == null || u.color == BLACK){
//③场景，RR情况，父节点变黑，祖父变红，对祖父节点左旋
if(node == p.right){
p.color = BLACK;
gp.color = RED;
leftRotate(gp);
return;
}
//④场景，RL情况，父节点右旋，递归
if(node == p.left){
rightRotate(p);
fixRBTree(p);
return;
}
}
}
}
}
层序遍历红黑树，实现代码如下：
public void showRBTree() {
if (root == null) {
return;
}
//三个变量作用只是输出的时候用来分层换行，并不影响遍历
int size = 0;
int x = 0;
int y = 0;
LinkedList<TreeNood<T>> list = new LinkedList<>();
list.offer(root);
while (!list.isEmpty()) {
TreeNood<T> node = list.pop();
if(node.left != null){
y++;
}
if(node.right != null){
y++;
}
if(node.color) {
if(node.parent != null){
System.out.print(node.value + ",红" + "(" + node.parent.value + ") ");
}else {
System.out.print(node.value + ",红 ");
}
}else{
if(node.parent != null){
System.out.print(node.value + ",黑" + "(" + node.parent.value + ") ");
}else {
System.out.print(node.value + ",黑 ");
}
}
if (node.left != null) {
list.offer(node.left);
}
if (node.right != null) {
list.offer(node.right);
}
if(size == x){
System.out.println();
x = y;
size = 0;
y = 0;
}
size ++;
}
}
删除节点待补充.......
网友评论