package R20220707;

import org.junit.Test;

import java.util.*;

/**
 * @author myd
 * @date 2022/7/10  15:13
 */

public class RBT {


    Node root;
    class Node{
        Node parent;
        Node left;
        Node right;
        boolean red = true;//新节点都是红色；
        int data;
        public Node(int val){
            data = val;
        }
    }

    Node LL_rotate(Node node){
        Node parent =  node.parent;
        Node left = node.left;
        Node lr = left.right;//可能为空;
        if(parent == null){
            root = left;
            root.red = false;
        }else{
            if(parent.left == node)parent.left = left;
            else parent.right = left;
        }
        left.parent = parent;
        left.right = node;
        node.left = lr;
        if(lr != null)lr.parent = node;
        node.parent = left;
//       left.left.red = false;
        return left;
    }
    Node RR_rotate(Node node){
        Node parent  = node.parent;
        Node right =  node.right;
        Node rl = right.left;//right_left_node
        if(parent == null){
            root = right;
            root.red = false;
        }else{
            if(parent.left == node)parent.left = right;
            else parent.right = right;
        }
        right.parent = parent;
        right.left = node;
        node.parent = right;
        node.right = rl;
        if(rl!= null)rl.parent = node;
        return right;
    }
    Node RL_rotate(Node node){
        LL_rotate(node.right);
        return RR_rotate(node);
    }
    Node LR_rotate(Node node){
        RR_rotate(node.left);
        return  LL_rotate(node);
    }

    public void addVal(int val){
        Node node = new Node(val);
        if(root == null){
            root = node;
            root.red = false;
            return ;
        }
        boolean addSuccess = insert(node,root);
        if(!addSuccess)return;//插入失败；===》插入元素与tree中原有数据重复；
        addBalance(node);
    }
    Node search(int val, Node node){
        if(node == null)return null;
        if(node.data == val) return node;
        else if(val > node.data)return search(val,node.right);
        else return search(val,node.left);
    }
    boolean insert(Node node, Node cur){
        if(node.data == cur.data )return false;
        else if(node.data > cur.data){
            if(cur.right == null){
                cur.right = node;
                node.parent = cur;
            }else{
                return insert(node,cur.right);
            }
        }else{
            if(cur.left == null){
                cur.left = node;
                node.parent = cur;
            }else{
                return insert(node,cur.left);
            }
        }
        return true;
    }
    /**
     *
     * 颜色调整
     * @param node
     */
     void addBalance(Node node){
        if(!(isRed(node.parent)))return;//父节点为黑色。不会产生冲突；
        Node grandpa = node.parent.parent;
        Node left = grandpa.left;
        Node right = grandpa.right;
        //判断是哪种类型的冲突；
        boolean leftColor  = isRed(left);
        boolean rightColor = isRed(right);
        if(leftColor && rightColor){// case 1: 叔父节点是红色
            //将黑红红  --> 红黑黑
            grandpa.red = true;
            left.red = false;
            right.red = false;
            if(grandpa==root){
                grandpa.red = false;
                return;
            }
            addBalance(grandpa);
        }else if (leftColor ){//case 2 :红黑 LL,LR
            Node vertex;
            if(isRed(left.left)){//LL
                vertex = LL_rotate(grandpa);
            }else{//LR
                vertex = LR_rotate(grandpa);
            }
            //旋转后，一个红色节点下沉，形成新的tree：黑（树顶） 红红（左右子节点）
            if(!vertex.left.red){
                vertex.left.red = true;
            }else{
                vertex.right.red = true;
            }
            vertex.red = false;
        }else if(rightColor){//case 3 : 黑红 RR,RL
            Node vertex ;
            if(isRed(right.left)){//RL
                vertex = RL_rotate(grandpa);
            }else{//RR
                vertex = RR_rotate(grandpa);
            }
            //旋转后，一个红色节点下沉，形成新的tree：黑（树顶） 红红（左右子节点）
            if(!vertex.left.red){
                vertex.left.red = true;
            }else{
                vertex.right.red = true;
            }
            vertex.red = false;
        }
    }
     boolean isRed(Node node){
        return node == null ? false : node.red;
    }

     boolean notNull(Node node){
        return node != null;
    }
    //删除叶子节点
     void deleteLeaf(Node node){
        Node parent = node.parent;
        if(parent.left == node)parent.left = null;
        else parent.right = null;
    }
    public boolean deleteVal(int val ){
        Node target = search(val,root);
        deleteNode(target);
        return target != null;
    }
      void  deleteNode(Node target){
        if(target == null)return;
        if(notChild(target)){
            if(target.red)//被删除节点是红色，并且没有子节点
                deleteLeaf(target);
            else{//!target.red;被删除的是黑色叶子节点；
                if(root == target){
                    root=null;
                }else {
                    deleteBalance(target);
                    deleteLeaf(target);
                }
            }
        }else  if(hasOneChild(target)){//target只有一个子节点，那么target一定是黑色
            if(notNull(target.left)){//left子节点有且只有一个红节点
                target.data = target.left.data;
                target.left = null;
            }else{
                target.data = target.right.data;
                target.right = null;
            }
        }else{//有2个孩子
            Node replaceNode  = searchReplace(target.left);//replaceNode是left半区的；
            target.data = replaceNode.data;
            deleteNode(replaceNode);
        }
    }
       void deleteBalance(Node node){
        if(node == null || node.parent == null)return;
        Node parent = node.parent;
        Node bro = parent.left == node ? parent.right : parent.left;
        if(!bro.red){//bro是黑色
            Node vertex = null;
            if(bro == parent.left){//左, L
                if(isRed(bro.left)){//ll
                    vertex = LL_rotate(parent);
                    vertex.left.red = false;
                    vertex.red = parent.red;
                    parent.red = false;
                }else if(isRed(bro.right)){//lr
                    vertex = LR_rotate(parent);
                    vertex.red = parent.red;
                    parent.red = false;
                }else{  //全黑，bro节点的子节点也没有红色节点；先将bro节点让染红，然后向上递归
                    bro.red = true;
                    if(parent.red)
                        parent.red = false;
                    else
                        deleteBalance(parent);
                }
            }else{//右, R
                if(isRed(bro.right)){//rr
                    vertex = RR_rotate(parent);
                    vertex.right.red = false;
                    vertex.red = parent.red;
                    parent.red = false;
                }else if(isRed(bro.left)){//rl
                    vertex = RL_rotate(parent);
                    vertex.red = parent.red;
                    parent.red = false;
                }else{ //全黑，bro节点的子节点也没有红色节点；先将bro节点让染红，然后判断parent颜色，如果是红色，直接染黑就行；黑色则向上递归
                    bro.red = true;
                    if(!parent.red)
                        deleteBalance(parent);
                    else
                        parent.red = false;
                }
            }
        }else{//bro是红色
            Node vertex = null;
            if(bro == parent.right){
                vertex = RR_rotate(parent);
                parent.right.red = true;
                vertex.red =false;
            }else{
                vertex = LL_rotate(parent);
                parent.left.red = true;
                vertex.red = false;
            }

        }
    }
    /**
     *
     * 当被删除的target有2个子节点时，使用该方法找到一个被替代删除的节点；
     * @param target  真实被删除的节点；
     * @return target 的左边最大值节点来代替target被删除
     */private Node searchReplace(Node target){
        if(target.right == null)return target;
        return searchReplace(target.right);
    }
    /**
     *
     *
     * @param node
     * @return
     */
    private boolean notChild(Node node){
        return !notNull(node.left) && !notNull(node.right);
    }
    private boolean hasOneChild(Node node){//只有一个节点
        return !notChild(node) && !hasTwoChild(node);
    }
    private boolean hasTwoChild(Node node){
        return notNull(node.left) && notNull(node.right);
    }

    void printNode(List<Node> nodes){
        if(nodes.isEmpty())return;
        List<Node> children =  new ArrayList<>();
        for(Node node : nodes ){
            if(node.red){//\033[34;4m
                System.out.print("\033[91;1m["+node.data+"]\033[0m\t");
            }else
                System.out.print("["+node.data+"]\t");
            if(node.left!=null)children.add(node.left);
            if(node.right!=null)children.add(node.right);
        }
        System.out.println("\n*******************************");
        printNode(children);
    }
    public void print(){
        List<Node> nodes =  new ArrayList<>();
        nodes.add(root);
        printNode(nodes);
    }

    List<Node>  pre =  new ArrayList<>();

    void preOrder(Node node){
        if(node == null)return;
        pre.add(node);
        preOrder(node.left);
        preOrder(node.right);
    }
    List<Node> mid = new ArrayList<>();

    void midOrder(Node node){
        if(node == null)return;
        midOrder(node.left);
        mid.add(node);
        midOrder(node.right);
    }

    Map<Node,Integer> map =new HashMap<>();
    void init(){
        if(root == null)return;
        midOrder(root);
        for (int i = 0; i < mid.size(); i++) {
            map.put(mid.get(i),i);
        }
    }


    void printLevel(List<Node> nodes){
        String VLine = "";
        String dataLine = "";
        String line = "";
        int lastNodeIndex = 0;
        int lastRightIndex = 0;
        for (Node node : nodes) {
            int x =  map.get(node);
            String addEmpty = getEmpty(x-lastNodeIndex);
            lastNodeIndex = x;
            VLine    += addEmpty+"|";//竖线拼接
            //数字拼接
            if(node.red)
                dataLine+= addEmpty +"\033[91;1m"+node.data+"\033[0m";//打印红色
            else
                dataLine += addEmpty+node.data;

            Node left  = node.left;
            Node right = node.right;
            String leftLine  = null;
            String rightLine = null;
            int leftIndex  = -1;
            int rightIndex = -1;
            if(left  != null){
                leftIndex = map.get(left);
                leftLine = getLineToSon(x - leftIndex);
            }
            if(right != null){
                rightIndex = map.get(right);
                rightLine = getLineToSon(rightIndex - x);
            }
            String curLine  = (leftLine == null ? "" :leftLine)  + "|"+(rightLine == null ? "" : rightLine);
            if(leftLine == null && rightLine == null)curLine="";
            //线段之间的间隔
            int dif = (leftIndex == -1 ? x : leftIndex) - lastRightIndex;
            String difEmpty = getEmpty(dif);
            line += difEmpty + curLine;//拼接线段
            lastRightIndex = rightIndex == -1 ? x : rightIndex;
        }
        System.out.println(VLine +"\n" + dataLine +"\n" + line);
    }


    String  getEmpty(int x){
        String empty ="";
        for (int i = 0; i < x; i++) {
            empty+="\t";
        }
        return empty;
    }

    void treePrint(List<Node> nodes){
        if(nodes.isEmpty())return;
        printLevel(nodes);
        List<Node> children =  new ArrayList<>();
        for (Node node : nodes) {
            if(node.left != null)children.add(node.left);
            if(node.right != null) children.add(node.right);
        }
        treePrint(children);
     }

     public void treePrint(){
        init();
        List<Node> nodes =  new ArrayList<>();
        nodes.add(root);
        treePrint(nodes);
     }

    String getLineToSon(int end){
        String line = "";
        if(end ==0)return line;
        for (int i = 0; i < end; i++) {
             line+="____";
        }
        return line;
    }






  @Test
  public void test7(){

      System.out.println("\tAA");
      System.out.println("----|-----");
      System.out.println("======");
      int x = 4,y = 0 ;
      System.out.println("\tAA\n   /  \\");
//      System.out.println("   /  \\");

  }




    @Test
    public void test(){

        for (int i = 0; i < 31; i++) {
            addVal(i);
        }

        System.out.println("\n+++++++++++++++++++++++++++++++++++++++TreePrint test++++++++++++++++++++++++++++++++++++++");

        System.out.println("[start] print.....");
        long start = System.currentTimeMillis();
        treePrint();
        long end = System.currentTimeMillis();
        System.out.println("[end] print tree time:"+(end-start)+"ms");


    }


}