红黑树定义
1.每个节点为红色或者黑色
2.根节点为黑色
3.叶子节点为黑色
4.如果一个节点为红色，则它的子节点只能为黑色
5.从一个节点到叶子节点的所有路径上黑色节点个数相同
红黑树的java数据结构
public class RBTree<T extends Comparable<T>>{
private RBTNode mRoot;
private static final boolean RED=false;
private static final boolean BLACK=true;
public class RBTNode<T extends Comparable<T>>{
boolean color;
T key;
RBTNode<T> left;
RBTNode<T> right;
RBTNode<T> paraent;
public RBTNode(T key,boolean color, RBTNode<T> parent,RBTNode<T> left, RBTNode<T> right){
this.key=key;
this.color=color;
this.parent=parent;
this.left=left;
this.right=right;
}
}
}
红黑树插入过程中会有左旋和右旋，下面介绍这两种情况
1.左旋
//todo 插入图片
//java 代码
private void leftRotate(RBTNode<T> x){
//设置x的右孩子为y
RBTNode<T> y=x.right;
//将y的左孩子设置为x的右孩子
x.right=y.left;
if(y.left != null){
y.left.parent=x;
}
y.parent=x.parent;
if(x.parent == null){
this.mRoot=y;
}else{
if(x.parent.left==x){
x.parent.left=y;
}
x.parent.right=y;
}
y.left=x;
x.parent=y;
}
- 右旋
//todo 插入图片
//java代码
private void rightRotate(RBTNode<T> x){
//设置x的左孩子为y
RBTNode<T> y=x.left;
//将x的右孩子设置为y的左孩子
y.left=x.right;
if(x.right != null){
x.right.parent=y;
}
//将y的parent设置为x的parent
x.parent=y.parent;
if(y.parent == null){
this.mRoot=x;
}else{
if(y.parent.left == y){
y.parent.left=x;
}else{
y.parent.right=x;
}
}
x.right=y;
y.parent=x;
}
红黑树的添加
红黑树添加节点默认为红色，添加后分三种情况
1.父节点为红色，叔叔节点为红色
将父节点和叔叔节点调整为黑色，祖父节点调整为红色，将祖父节点作为新的节点重新调整
2.父亲节点为红色，叔叔节点为黑色，自己为父亲节点的左孩子
将父节点调整为黑色，祖父节点调整为红色，对祖父节点进行右旋操作
3.父节点为红色，叔叔节点为黑色，自己为父亲节点的右孩子
对父亲节点左旋操作，则转化成情况2
//java代码
private void insert(RBTNode<T> node){
int cmp;
RBTNode<T> y=null;
RBTNode<T> x=this.mRoot;
//查找要插入的节点
while(x != null){
y=x;
cmp=node.key.compareTo(x.key)
if (cmp<0){
x=x.left;
} else{
x=x.right;
}
}
node.parent=y;
if( y != null){
cmp=node.key.compareTo(y.key);
if(cmp<0){
y.left=node;
}else{
y.right=node;
}
}else{
this.mRoot=node;
}
//将节点置为红色
node.color=RED;
//调整红黑树
insertFixUp(node);
}
添加节点后台调整红黑树 java代码
private void insertFixUp(RBTNode<T> node){
RBTNode<T> parent, gparent;
while((parent=parentOf(node))!=null&&isRed(parent)){
gparent=parentOf(parent);
//父节点是祖父节点的左孩子
if(parent==gparent.left){
RBTNode<T> uncle=gparent.right;
//case1: 叔叔节点为红色
if(uncle!=null && uncle.color==RED){
setBlack(parent);
setBlack(parent);
setRed(gparent);
node=parent;
continue;
}
//case2: 叔叔节点为黑色，且自己为右节点
if(node==parent.right){
RBTNode<T> tmp;
leftRotate(parent);
tmp=parent;
parent=node;
node=parent;
}
//case3: 叔叔节点为黑色，且自己为左节点
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
}else{ //父节点是祖父节点的右孩子
RBTNode<T> uncle=gparent.right;
//case1: 叔叔节点为红色
if(uncle!=null && uncle.color==RED){
setBlack(parent);
setBlack(parent);
setRed(gparent);
node=parent;
continue;
}
//case2: 叔叔节点为黑色，且自己为左节点
if(node==parent.left){
RBTNode<T> tmp;
rightRotate(parent);
tmp=parent;
parent=node;
node=tmp;
}
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
}
}
//将根节点设置为黑色
setBlack(this.mRoot);
}
红黑树删除
红黑树的删除分为4种情况
1.兄弟节点为红色，且父亲节点为黑色，将父亲节点设置为红色，兄弟节点设置为黑色，对父亲节点旋转操作
2.兄弟节点为黑色，且兄弟节点的子节点都为黑色，将兄弟节点调整为红色
3.兄弟节点为黑色，且兄弟节点的左孩子为红色，右孩子为黑色，将父节点设置为黑色，兄弟节点右孩子设置为黑色，对父节点选择操作
4.兄弟节点为黑色，且兄弟节点的左孩子为黑色，右孩子为红色，将兄弟节点设置为红色，右孩子设置为黑色，对兄弟节点进行旋转操作。
private void remove(RBTNode<T> node){
RBTNode<T> child,parent;
boolean color;
if((node.left!=null)&&(node.right!=null)){
RBTNode<T> replace=node;
replace=repalce.right;
while(replace.left!=null)
replace=replace.left;
if(parent(node)!=null){
if(parent(node).left=node)
parentOf(node).left=node;
else
parentOf(node).right=node;
}else{
this.mRoot=node;
}
child=replace.right;
parent=parentOf(replace);
color=colorOf(replace);
if(parent==node)
parent=replace;
else{
if(child!=null){
setParent(child,parent);
}
parent.left=child;
replace.right=node.right;
setParent(node.right,replace);
}
replace.parent=node.parent;
replace.color=node.color;
replace.left=node.left;
node.left.parent=replace;
if(color==BLACK)
removeFixUp(child,parent);
node=null;
return;
}
}
删除节点后调整代码
private void removeFixUp(RBTNode<T> child,RBTNode<T> parent){
RBTNode<T> other;
while((node==null || isBlack(node))&&(node!=this.mRoot)){
if(parent.left==node){
other=parent.right;
if(isRed(other)){
//case1: 兄弟节点是红色
setBlack(other);
setRed(parent);
leftRotate(parent);
other=parent.right;
}
if((other.left!=null&&Color(other.left)==BLACK)&&(other.right==null&&Color(other.right)==BLACK)){
//case2
setRed(other);
node=parent;
parent=parentOf(node);
}else{
//case3
if(other.right!=null&&Color(other.right)==RED){
setColor(other,ColorOf(parent));
setBlack(parent);
setBlack(other.right);
leftRotate(parent)
node=this.mRoot;
}
setBlack(other.left);
setRed(other);
rightRotate(other);
other=parent.right;
break;
}
}
else{
other=parent.left;
if(isRed(other)){
//case1: 兄弟节点是红色
setBlack(other);
setRed(parent);
rightRotate(parent);
other=parent.left;
}
if((other.left!=null&&Color(other.left)==BLACK)&&
(other.right==null&&Color(other.right)==BLACK)){
//case2
setRed(other);
node=parent;
parent=parentOf(node);
}else{
if(other.left!=null&&Color(other.left)==RED){
setColor(other,ColorOf(parent));
setBlack(parent);
setBlack(other.right);
rightRotate(parent)
node=this.mRoot;
}
setBlack(other.left);
setRed(other);
leftRotate(other);
other=parent.right;
break;
}
}
if (node!=null)
setBlack(node);
}
//todo未完待续
