RBTree 红黑树代码

package Test;

public class RBTree{
 TreeNode root;
 // 建立红黑树
 public void create(int[] list){
  for(int i = 0;i < list.length;i ++){
   this.insert(list[i]);
   }
 }
 // 插入一个元素
 public void insert(int elem){// 为新元素开辟一个空间
  TreeNode s = new TreeNode();
  s.data = elem;
  s.color = "red";
  s.lchild = null;
  s.rchild = null;
  // 判断根是否为空,如果为空,则将root指向新元素.否则,进入循环
 if(root == null){
  root = s;
  root.color = "black";
  return ;
 } else {
  // 定义四个指针,分别指向祖先,祖,父,自身
 TreeNode p = root,q;
 TreeNode parent = root;
 TreeNode grand = root;
 TreeNode ancestor = root;
 
 while(p != null) {
  // 如果P的左右孩子均不为空且颜色均为红色,则执行颜色转换并进行调整
 if(p.lchild != null && p.rchild != null) {
  if(p.lchild.color==("red") && p.rchild.color==("red")) {
   convertColor(p);
   adjust(ancestor,grand,parent,p);   
   }
 }
 if(elem == p.data){
  return;
 }
 q = p; // 指针依次向后移动
 ancestor = grand;
 grand = parent;
 parent = p;// 如果,元素小于P
 
 if(elem < q.data) { // P的左孩子为空
  if(q.lchild == null){
   // 将P的左孩子指向新建元素
   q.lchild = s;
   p = s; // 调整
   adjust(ancestor,grand,parent,p);
   return;
  } else {// P的左孩子不为空
   // P向左下移动
           p = p.lchild;
  }
 } else {// 如果,元素大于P
 if(elem > q.data) { // P的右孩子为空
  if(q.rchild == null){
   // 将P的右孩子指向新建元素
   q.rchild = s;
   p = s;// 调整
   adjust(ancestor,grand,parent,p);
   return;
  } else {// P的右孩子不为空
      // P向右下移动
   p = p.rchild;
   }  
  }
 }
    }
 }
 }

 // 调整颜色的方法
 
 public void convertColor(TreeNode p){
  // 将P的左右孩子的颜色均置为黑
  p.lchild.color = "black";
  p.rchild.color = "black";
  // 若P为根结点,则颜色仍为黑,否则颜色置为红
  if(!(p.equals(root))){
   p.color = "red";
   return;
  }
  if(p.equals(root)) {
   p.color = "black";
  }
 }
 
 public void adjust(TreeNode ancestor,TreeNode grand,TreeNode parent,TreeNode x){// 是否存在红红冲突
  if(!(parent.color == "red" && x.color == "red")) {
   return;
  }
  // 符合一次调整的,将调用一次调整
  if((grand.lchild == parent && parent.lchild == x) ||(grand.rchild == parent && parent.rchild == x )){
   onceAdjust(ancestor,grand,parent,x);
   return;
  }
  // 符合二次调整的,将调用二次调整
  if((grand.lchild == parent && parent.rchild == x ) || (grand.rchild == parent && parent.lchild == x )){
   twiceAdjust(ancestor,grand,parent,x);
   return;
   }
 }
 
 private void onceAdjust(TreeNode ancestor,TreeNode grand,TreeNode parent,TreeNode x){ // 调整父结点和祖结点的颜色
  this.exchangeColor(grand);
  this.exchangeColor(parent);
  // 将祖先结点指向父结点
  if(ancestor ==  grand && ancestor == this.root ){
   this.root = parent;
   ancestor = parent;
  } else {
   if(ancestor.lchild == grand){
    ancestor.lchild = parent;
   } else if(ancestor.rchild == grand) {
    ancestor.rchild = parent;
   }
  }
  // 左左型调整
  if(grand.lchild == parent && parent.lchild == x ){
   grand.lchild = parent.rchild;
   parent.rchild = grand;  
   return;
  }
  // 右右型调整
  if(grand.rchild == parent && parent.rchild == x ){
   grand.rchild = parent.rchild;
   parent.lchild = grand;
   return;
  }
 }
 
 private void twiceAdjust(TreeNode ancestor,TreeNode grand,TreeNode parent,TreeNode x){ // 调整自身结点和祖结点的颜色
  this.exchangeColor(grand);
  this.exchangeColor(x);
  // 将祖先结点指向自身结点
  if(ancestor == grand && ancestor == root){
   root = x;
   ancestor = x;
  } else {
   if(ancestor.lchild == grand){
    ancestor.lchild = x;
   } else if(ancestor.rchild == grand){
    ancestor.rchild = x;
   } else if(ancestor == root){
    ancestor = x;
    root = x;
    }
  }// 左右型调整
  
  if(grand.lchild == parent && parent.rchild == x ){
   grand.lchild = x.rchild;
   parent.rchild = x.lchild;
   x.lchild = parent;
   x.rchild = grand;
   return;
  }// 右左型调整 if(grand.rchild ==
             // parent && parent.lchild
             // == x){
  grand.rchild = x.lchild;
  parent.lchild = x.rchild;
  x.lchild = grand;
  x.rchild = parent;
  return;
 }

 // 变换颜色的方法
 private void exchangeColor(TreeNode p){
  if(p.color.equals("red")){
   p.color = "black"; } else{
    p.color = "red";
    }
  }
  
 public void inorder(){inorder(root); }// 中序遍历
 
 private void inorder(TreeNode root){
  if(root != null){
   inorder(root.lchild);
   System.out.println(root.data+"  "+root.color);
   inorder(root.rchild);
   }   
  }
 }

 class TreeNode{
  public int data;
  public String color;
  public TreeNode lchild;
  public TreeNode rchild;
 }