public class RBTree {

  TreeNode root = null;
  TreeNode nil ;

  public RBTree() {
      this.nil = new TreeNode();
      this.nil.parent=this.nil;
      this.nil.left = this.nil;
      this.nil.right = this.nil;
      this.nil.data = -1;
      this.nil.isRed = false;
  }
  public void insertNode(int data) {
      if(root==null) {  //如果树不存在构建根节点
          root = new TreeNode(nil,nil,nil,data,false);
      }else {
          TreeNode p=root,c=root;
          boolean isLeft;
          do {        //找到要插入节点的父节点;
              p=c;
              if(p.data>=data) {
                  c=p.left;
                  isLeft = true;
              }else {
                  c=p.right;
                  isLeft = false;
              }
            
          }while(c!=nil);
          c = new TreeNode(p,nil,nil,data,true);
          if(isLeft) {  //插入新节点,颜色为红
              p.left = c;
          }else {
                p.right = c;
          }
          checkTree(c); //对树进行调整
      }
  }

  private void checkTree(TreeNode c) { //对树进行调整
      TreeNode p = c.parent; //父节点
      TreeNode gp = p.parent; //祖父节点
    
      if(p.isRed) {  //如果父节点为红节点，则进行调整
          if(!(gp.left.isRed ^ gp.right.isRed)) { //如果叔父节点也是红节点
              gp.left.isRed=false;
              gp.right.isRed=false;
              gp.isRed=true;
              if(gp==root) {
                  gp.isRed = false;
              }else {
                  checkTree(gp);
              }
          }else {   //叔父节点是黑节点，进行旋转操作
              if(p==gp.left) { 
                  if(c==p.left) {//R旋转
                      if(gp.parent==nil) {
                          root = p;
                      }else {
                          if(gp.parent.left==gp) {
                              gp.parent.left = p;
                          }else {
                              gp.parent.right = p;
                          }
                      }
                      gp.left = p.right; 
                      p.right=gp;  
                      p.parent = gp.parent;
                      gp.parent = p;
                      gp.left.parent = gp.left==nil?nil:gp;
                      p.isRed =false;
                      c.isRed = true;
                      gp.isRed = true;
                    
                  }else { //LR旋转
                      if(gp.parent==nil) {
                          root = c;
                      }else {
                          if(gp.parent.left==gp) {
                              gp.parent.left = c;
                          }else {
                              gp.parent.right = c;
                          }
                      }
                      p.right = c.left;
                      p.right.parent = p.right==nil?nil:p;
                      p.parent =c;
                      c.left = p;
                      gp.left = c.right;
                      gp.left.parent = gp.left==nil?nil:gp;
                      c.right =gp;
                      gp.parent = c;
                      c.isRed =false;
                      p.isRed =true;
                      gp.isRed = true;
                  }
              }else { 
                  if(c==p.left) { //RL旋转
                      if(gp.parent==nil) {
                          root = c;
                      }else {
                          if(gp.parent.left==gp) {
                              gp.parent.left = c;
                          }else {
                              gp.parent.right = c;
                          }
                      }
                      p.left = c.right;
                      p.left.parent = p.left==nil?nil:p;
                      p.parent = c;
                      c.right = p;
                      gp.right = c.left;
                      gp.right.parent = gp.right==nil?nil:gp;
                      gp.parent = c;
                      c.left =gp;
                      c.isRed =false;
                      p.isRed = true;
                      gp.isRed = true;
                  }else {// L旋转
                      if(gp.parent==nil) {
                          root = p;
                      }else {
                          if(gp.parent.left==gp) {
                              gp.parent.left = p;
                          }else {
                              gp.parent.right = p;
                          }
                      }
                      gp.right = p.left;
                      gp.right.parent = gp.right==nil?nil:gp;
                      p.left =gp;
                      gp.parent = p;
                      p.isRed =false;
                      c.isRed = true;
                      gp.isRed = true;
                  }
              }
          }
      }  //父为黑节点不需要操作
  }
}

class TreeNode{

  TreeNode parent;
  TreeNode left;
  TreeNode right;
  int data;

  boolean isRed;
  public TreeNode() {
    
  }
  public TreeNode(TreeNode parent, TreeNode left, TreeNode right, int data, boolean isRed) {
      this.parent = parent;
      this.left = left;
      this.right = right;
      this.data = data;
      this.isRed = isRed;
  }
}