日志
【数据结构】尝试JAVA实现红黑树
热度 107 ||
package BeginPackage;
public class RBTree {
private int value;
private boolean color;
private RBTree left,right;
public RBTree(int value) {
this.value=value;
this.color=false;
this.left=null;
this.right=null;
}
private int altColor() {
if(this.color) {
return 0;
}else{
this.color=true;
if(this.left!=null && this.right!=null) {
this.left.color=false;
this.right.color=false;
return 0;
}else if(this.left!=null) {
if(this.left.right!=null) {
this.left.right.color=false;
}
return 1;
}else if(this.right!=null){
if(this.right.left!=null) {
this.right.left.color=false;
}
return -1;
}else{
return 0;
}
}
}
public RBTree min() {
return this.left==null?this:this.left.min();
}
public RBTree max() {
return this.right==null?this:this.right.max();
}
private RBTree leftRevolve() {
RBTree temp=this.right;
this.right=temp.left;
temp.left=this;
return temp;
}
private RBTree rightRevolve() {
RBTree temp=this.left;
this.left=temp.right;
temp.right=this;
return temp;
}
private RBTree revolve(int colorMessage) {
if(colorMessage==0) {
return this;
}
if(colorMessage==1) {
if(this.left.left==null) {
this.left=this.left.leftRevolve();
}
return this.rightRevolve();
}else {
if(this.right.right==null) {
this.right=this.right.rightRevolve();
}
return this.leftRevolve();
}
}
public RBTree insert(RBTree node) {
if(this.value>node.value) {
if(this.left!=null) {
this.left=this.left.insert(node);
}else {
node.color=true;
return node;
}
}else if(this.value<node.value) {
if(this.right!=null) {
this.right=this.right.insert(node);
}else {
node.color=true;
return node;
}
}else {
return this;
}
int colorMessage=this.altColor();
return this.revolve(colorMessage);
}
public RBTree del(RBTree node) {
if(this.value>node.value) {
if(this.left!=null) {
this.left=this.left.del(node);
}
}else if(this.value<node.value) {
if(this.right!=null) {
this.right=this.right.del(node);
}
}else {
if(this.left==null && this.right==null) {
return null;
}else if(this.left==null) {
return this.right;
}else if(this.right==null) {
return this.left;
}else {
RBTree temp=this.right.min();
this.value=temp.value;
temp.right=this.right.del(temp);
}
}
int colorMessage=this.altColor();
return this.revolve(colorMessage);
}
}
GameMale