数据结构 玩转数据结构 12-4 旋转操作的基本原理

//3     递归，添加元素
    public void add(K key,V value,Node root){
        //3.1   终止条件
        //3.1.1 要插入的元素和二叉树原有节点相同,这个不用判断，因为已经调了containsKey方法判断了
        /*if(key.equals(root.e)){
            return;
        }*/

        //3.1.2 最终插入左孩子
        if(key.compareTo(root.key)<0 && root.left==null){
            root.left = new Node(key,value);
            size++;
            return;
        }

        //3.1.2 最终插入右孩子
        if(key.compareTo(root.key)>0 && root.right == null){
            root.right = new Node(key,value);
            size++;
            return;
        }

        //3.2   递归
        //3.2.1 递归左孩子
        if(key.compareTo(root.key)<0){
            add(key,value,root.left);
        }

        //3.2.2 递归右孩子
        if(key.compareTo(root.key)>0){
            add(key,value,root.right);
        }
        root.height = 1+Math.max(getHeight(root.left),getHeight(root.right));
        int balanceFactor = getBalanceFactor(root);
        if(Math.abs(balanceFactor)>1){
            System.out.println("unbalanced:"+balanceFactor);
        }

        //左左情况
        if(balanceFactor>1&&getBalanceFactor(root.left)>=0){

        }
    }