[数据结构与算法]AVLTree-insert() -java

java avlTree insert()

package avltree;

public class AVLTree {
    static class AVLTreeNode{
        public int value = 0; // 节点的内容 ;
        public int balance_factor = 0; // 当前节点的平衡因子;
        public AVLTreeNode left = null; // 左孩子
        public AVLTreeNode right = null; // 右边孩子
        public AVLTreeNode parent = null; // 节点的双亲

        public AVLTreeNode(int value) {
            this.value = value;
        }
    }
    public AVLTreeNode root = null;
    // 平衡二叉树的插入
    // 1. 按照二叉搜索数的方式 插入新的节点;

    public boolean insert(int val) throws Exception {
        // 先按照 二叉搜索树的 规则 将节点插入 ;
        if(root == null){
            root = new AVLTreeNode(val);
            return true;
        }
        AVLTreeNode parent = null;
        AVLTreeNode cur = root;
        while(cur != null){
            if(cur.value < val){
                parent = cur;
                cur = cur.right;
            }else if(cur.value > val){
                parent = cur;
                cur = cur.left;
            }else {// cur.value == val;
                return false; // treeSet TreeMap 的 key 不可以重复;
            }
        }
        // 当 cur == null 退出循环 此时找到要插入的位置;
        cur = new AVLTreeNode(val);
        if(parent.value < val){
            parent.right = cur;
        }else {
            parent.left = cur;
        }
        // 新增插入完成 ;
        cur.parent = parent;
        // 2. 调整节点的平衡因子;
        // 2.1 从当前位置向上 调节parent 的 balance_factor ;
        // 2.2 根据 parent.balance_factor 采取对应的平衡策略;
        while(parent != null){
            if(cur == parent.left){
                parent.balance_factor--;
            }else {
                parent.balance_factor++;
            }
            if(parent.balance_factor == 0){
                break; // 当前增量相对与上层没有变化,不用继续向上 ;
            }else if(parent.balance_factor == 1 || parent.balance_factor == -1){
                // 增量对上层会造成影响;
                cur = parent;
                parent = parent.parent;
            }else if(parent.balance_factor == 2){// 需要进行调整 (右子树增量 破防);
                    if(cur.balance_factor == 1){ // 这里证明 是右子树的右子树 增量导致
                        // 需要进行左单旋转;
                        RotateL(parent);
                    }else { // cur.balance_factor == -1;
                        // parent 的右子树的左子树 发生增量 需要给 parent.right 先做一个右单旋,再给parent 来个左单旋转;
                        // 简称 右左 双旋转;
                        RotateRL(parent);
                    }
                    // 调整结束就不用再向上调整,下层能够摆平就不劳烦上层
                    break;
            }else if(parent.balance_factor == -2){// 需要进行调整 (左子树增量 破防) ;
                    if(cur.balance_factor == -1){ // 这里证明 是parent 的左子树的左子树上的增量导致的;
                        // 需要来个右单旋
                        RotateR(parent);
                    }else{ // cur.balance_factor == 1;
                        // parent 的左子树的右子树的增量
                        // 需要对 parent 左子树进行左单旋,再对 parent 进行右单旋;
                        RotateLR(parent);
                    }
                break;
            }else {
                throw new Exception("balance_factor 异常 ");
            }
        } // 平衡因子调节完成 , 插入完毕;
        return true;
    }


    // 原因 : 需要右左双旋,是因为 parent 的右子树的左子树 产生了增量导致
    private void RotateRL(AVLTreeNode parent) {
        AVLTreeNode cur = parent.right;
        AVLTreeNode curL = cur.left;
        // 根据右子树的左子树 的增量平衡因子确定 平衡后 parent , cur 和 curL 的 balance_factor;
        int balance_factor = curL.balance_factor;
        RotateR(cur);
        RotateL(parent);

        if(balance_factor == -1){
            parent.balance_factor = 0;
            cur.balance_factor = 1;
            curL.balance_factor = 0;
        }else if(balance_factor == 1){
            parent.balance_factor = -1;
            cur.balance_factor = 0;
            curL.balance_factor = 0;
        }else { // balance_factor == 0;
            parent.balance_factor = 0;
            cur.balance_factor = 0;
            curL.balance_factor = 0;
        }
    }

    // 增量产生与 parent 的左子树的右子树上,具体调节依赖curR.balance_factor 的值
    private void RotateLR(AVLTreeNode parent) {
        AVLTreeNode cur = parent.left;
        AVLTreeNode curR = cur.right;
        int balance_factor = curR.balance_factor;

        RotateL(cur);
        RotateR(parent);

        if(balance_factor == -1){
            cur.balance_factor = 0;
            parent.balance_factor = 1;
            curR.balance_factor = 0;
        }else if(balance_factor == 1){
            parent.balance_factor = 0;
            cur.balance_factor = -1;
            curR.balance_factor = 0;
        }else {
            parent.balance_factor = 0;
            cur.balance_factor = 0;
            curR.balance_factor = 0;
        }
    }

    // 左单旋;
    private void RotateL(AVLTreeNode parent) {
        AVLTreeNode cur = parent.right;
        AVLTreeNode curL = cur.left;
        parent.right = curL;
        if(parent.parent != null){
            if(parent == parent.parent.left){
                parent.parent.left = cur;
            }else {
                parent.parent.right = cur;
            }
            cur.parent = parent.parent;
        }else {
            root = cur;
            root.parent = null;
        }
        parent.parent = cur;
        cur.left = parent;
        if(curL != null){
            curL.parent = parent;
        }

        parent.balance_factor = 0;
        cur.balance_factor = 0;
    }
    // 右单旋;
    private void RotateR(AVLTreeNode parent) {
        AVLTreeNode cur = parent.left;
        AVLTreeNode curR = cur.right;

        parent.left = curR;

        if(parent.parent != null){
            if(parent == parent.parent.left){
                parent.parent.left = cur;
            }else {
                parent.parent.right = cur;
            }
            cur.parent = parent.parent;
        }else {
            root = cur;
            root.parent = null;
        }
        parent.parent = cur;
        cur.right = parent;
        if(curR != null){
            curR.parent = parent;
        }
        parent.balance_factor = 0;
        cur.balance_factor = 0;
    }

    void midOrder(AVLTreeNode root){
        if(root == null) return ;
        midOrder(root.left);
        System.out.print(root.value+" ");
        midOrder(root.right);
    }

    public static void main(String[] args) throws Exception {
        AVLTree avlTree = new AVLTree();
        int[] arr = {3,6,8,9,23,7,6,90};
        for(int num : arr){
            avlTree.insert(num);
        }
        avlTree.midOrder(avlTree.root);
    }
}