AVL二叉平衡树

AVL二叉平衡树
说明： AVL二叉平衡树是对二叉排序树的一种调整，当 7 为根节点，6、5、4、3、2 时，所有节点位于左子节点上，导致相当于一条链表， 增删无问题，可是查询的效率甚至还要比链表差[ 因为还需要额外的判断右子树等操作 ]

前提： 是一颗二叉排序树
特点： 它是一颗空树 或者 它的节点的左子树和右子树的高度差绝对值不超过 1


思路：
0. 每添加一次节点，调整一次树

1. 左旋转
   1.1 左子树高度 - 右子树高度 > 1
   1.2 用当前节点值创建出一个新节点 newNode
   1.3 新节点 newNode 的左子树 指向 原当前节点的左子树
   1.4 新节点 newNode 的右子树 指向 原当前节点的右子树的左子树
   1.5 将原当前节点的右子树的值替换到原当前节点的值
   1.6 将原当前节点的左子树 指向 新节点 newNode
   1.7 将原当前节点的右子树指向 原当前节点的右子树的右子树

2. 右旋转
   2.1 右子树高度 - 左子树高度 > 1
   2.2 类似左旋转

3. 双旋转
   3.1 如果 左子树高度 - 右子树高度 > 1
   3.2 不能马上进行右旋转
   3.3 还需要判断 当前节点的左子树的右子树高度 > 当前节点的左子树的左子树高度
   3.4 if 高于
   3.4.1 对当前节点的左子树进行左旋转，然后再对当前节点进行右旋转
   3.5 if 低于
   3.5.1 直接对当前节点进行右旋转
   3.6 处理完退出方法，因为每添加一个节点进行一个树调整判断，处理完退出就好了，避免后面的相关调整造成影响。

汇总代码

public class AVLTreeDemo {

    public static void main(String[] args) {
//        int[] arr = {4,3,6,5,7,8};
//        int[] arr = {10,12,8,9,7,6};
        int[] arr = {10,11,7,6,8,9};

        AVLTree alv = new AVLTree();
        // 创建二叉排序树
        for (int i = 0 ; i < arr.length ; i++){
            alv.add(new Node(arr[i]));
        }


        System.out.println("树的高度= " + alv.root.height()); // 4  --> 3
        System.out.println("树的左子树高度= " + alv.root.left.height());  // 1  --> 2
        System.out.println("树的右子树的高度= " + alv.root.right.height());  // 3  --> 2
        System.out.println("当前的根节点 == " + alv.root);


    }

}

// 创建 AVLTree
class AVLTree{

    public Node root ;

    /**
     *  添加节点
     */
    public void add(Node node){
        if(root == null){
            // 如果根节点为 空
            root = node;
        }else {
            root.add(node);
        }
    }

    /**
     *  中序遍历
     */
    public void infixOrder(){
        if(root == null){
            System.out.println("二叉排序树为空");
            return ;
        }
        root.infixOrder();
    }


    /**
     *  删除具有左右子节点的节点时
     *  -找出右子树最小的节点
     * @return
     */
    public Node getMinInRight(Node node){
        // 为空
        if(node == null){
            return null;
        }
        // 跑去删除节点的右子树呗
        Node rightNode = node.right; // 起始位置

        // 然后一直向左找最小，找到叶子节点
        while (rightNode.left != null){
            rightNode = rightNode.left;
        }
        // 删除右子树最小节点
        delNode(rightNode);
        return rightNode;
    }



    /**
     *  删除节点
     */
    public void delNode(Node node){
        // 为空
        if(node == null){
            return ;
        }

        // 删除
        Node targetNode = root.searchNode(node);
        if(targetNode == null){
            System.out.println("没有找到删除的节点");
            return ;
        }

        if(root.left == null && root.right == null){
            root = null;
            return ;
        }

        // 找父节点
        Node parent = root.nodeParent(node);

        // 找到了删除的节点、找到了删除节点的父节点
        // 删除情况
        if(targetNode.left == null && targetNode.right == null){
            // 删除的是叶子节点
            if(parent.left == targetNode){
                parent.left = null;
            }else if(parent.right == targetNode){
                parent.right = null;
            }
        }else if(targetNode.left != null && targetNode.right != null){
            // 删除具有左右子节点的节点
            Node minInRight = getMinInRight(targetNode); // 这里得到了最小的节点。
            // 直接替换掉值就可以了
            // 其他关系保持
            targetNode.value = minInRight.value;

        }else {
            // 删除具有左右其中一个子节点的节点
            if(targetNode.left != null ){
                // 这里之前有漏洞，补上
                if(parent != null){
                    if(parent.left.value == node.value){
                        parent.left = targetNode.left;
                    } else {
                        parent.right = targetNode.left;
                    }
                } else {
                    root = targetNode.left;
                }
            }else {
                // 删除只有右子节点的节点
                if(parent != null){
                    // 删除根节点的时候，  parent 为 null，所以这里还是需要判断一下
                    if(parent.right.value == node.value){
                        parent.right =  targetNode.right;
                    } else {
                        parent.left = targetNode.right;
                    }
                } else {
                    root = targetNode.right;
                }

            }
        }
    }


}

/**
 *  节点
 */
class Node {
    public int value;
    public Node left;
    public Node right;

    // 记录当前节点的高度
    public int height;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "bsNode{" +
                "value=" + value +
                '}';
    }

    /**
     *  获取左子树的高度
     * @return
     */
    public int leftHeight(){
        if(left == null){
            return  0;
        }
        return left.height();
    }

    /**
     *  获取右子树的高度
     * @return
     */
    public int rightHeight(){
        if(right == null){
            return  0;
        }
        return right.height();
    }

    /**
     *  获取根节点得高度
     * @return
     */
    public int height(){
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    }


    /**
     *  左旋转
     */
    public void leftRotate(){
        // 创建一个新的当前节点
        Node newNode = new Node(value);
        // 新建的节点左子树指向该节点的左子树
        newNode.left = left;
        // 讲新建的节点右子树指向该节点的右子树的右子树
        newNode.right = right.left;
        // 将该节点的右子树值赋到该节点
        value = right.value;
        // 将该节点的右子树指向该节点的右子树的右子树
        right = right.right;
        // 将该节点的左子树指向新建节点
        left = newNode;
    }

    /**
     *  右旋转
     */
    public void rightRotate(){
        // 新建当前节点
        Node newNode = new Node(value);
        newNode.right = right;
        newNode.left = left.right;
        value = left.value;
        left = left.left;
        right = newNode;

    }


    /**
     * 添加节点
     *
     * @param node
     */
    public void add(Node node) {
        // 递归
        if (this.value > node.value) {
            if (this.left == null) {
                this.left = node;
                return;
            }
            this.left.add(node);
        } else if (this.value < node.value) {
            if (this.right == null) {
                this.right = node;
                return;
            }
            this.right.add(node);
        }

        // 旋转调整
        // 左旋转 左矮
        if(rightHeight() - leftHeight() > 1){
            // 差距大于 1
            // 右子树高度 >  左子树高度
            if(right != null && right.leftHeight() > right.rightHeight()){
                // 先右旋转
                right.rightRotate();
                // 再左旋转
                leftRotate();
            } else {
                // 如果右子树的左子树的高度小于右子树的右子树高度
                // 直接左旋好了
                leftRotate();
            }
            /**
             *  加一个调整一次，调整完就必须退出，不然可能发生某些情况
             *   下面的执行已经无意义了
             */
            return ;
        }


        // 右旋转 右矮
        // 左子树高度 > 右子树
        if(leftHeight() - rightHeight() > 1){
            if(left != null && left.rightHeight() > left.leftHeight()){
                // 如果左子树的右子树高度大于左子树的左子树
                // 那么先进行左旋转
                left.leftRotate();
                // 然后再右旋转
                rightRotate();
            } else {
                 // 右旋转
                rightRotate();
            }
        }

    }


    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    /**
     * 查找需要删除的节点
     */
    public Node searchNode(Node node) {
        // 为空
        if (node == null) {
            return null;
        }

        if (this.value == node.value) {
            return this;
        } else if (this.value < node.value) {
            // 大于当前节点的值
            // 跑去右边呗
            if (this.right == null) {
                return null;
            }
            return this.right.searchNode(node);
        } else {
            // 小于当前节点的值
            // 跑去左边呗
            if (this.left == null) {
                return null;
            }
            return this.left.searchNode(node);
        }
    }

    /**
     * 找到需要呗删除的节点的父节点
     *
     * @param node 需要呗删除的节点
     * @return
     */
    public Node nodeParent(Node node) {
        // 为空
        if (node == null) {
            return null;
        }
        // 比较
        if (this.left != null && this.left.value == node.value) {
            return this;
        } else if (this.right != null && this.right.value == node.value) {
            return this;
        } else if (this.left != null && this.value > node.value) {
            // 如果当前值小于左子节点
            // 跑左边呗
            return this.left.nodeParent(node);
        } else if (this.right != null && this.value <= node.value) {
            return this.right.nodeParent(node);
        } else {
            // 都不满足
            // 根节点
            // 没有父节点
            return null;
        }
    }
}

---

核心代码

1. 获取树的高度

	// 记录当前节点的高度
    public int height;

   /**
     *  获取左子树的高度
     * @return
     */
    public int leftHeight(){
        if(left == null){
            return  0;
        }
        return left.height();
    }

    /**
     *  获取右子树的高度
     * @return
     */
    public int rightHeight(){
        if(right == null){
            return  0;
        }
        return right.height();
    }

    /**
     *  获取根节点得高度
     * @return
     */
    public int height(){
    // 递归运用
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    }
    

2. 左旋转、右旋转

    /**
     *  左旋转
     */
    public void leftRotate(){
        // 创建一个新的当前节点
        Node newNode = new Node(value);
        // 新建的节点左子树指向该节点的左子树
        newNode.left = left;
        // 讲新建的节点右子树指向该节点的右子树的右子树
        newNode.right = right.left;
        // 将该节点的右子树值赋到该节点
        value = right.value;
        // 将该节点的右子树指向该节点的右子树的右子树
        right = right.right;
        // 将该节点的左子树指向新建节点
        left = newNode;
    }

    /**
     *  右旋转
     */
    public void rightRotate(){
        // 新建当前节点
        Node newNode = new Node(value);
        newNode.right = right;
        newNode.left = left.right;
        value = left.value;
        left = left.left;
        right = newNode;

    }

3. 双旋转

        // 旋转调整
        // 左旋转 左矮
        if(rightHeight() - leftHeight() > 1){
            // 差距大于 1
            // 右子树高度 >  左子树高度
            if(right != null && right.leftHeight() > right.rightHeight()){
                // 先右旋转
                right.rightRotate();
                // 再左旋转
                leftRotate();
            } else {
                // 如果右子树的左子树的高度小于右子树的右子树高度
                // 直接左旋好了
                leftRotate();
            }
            /**
             *  加一个调整一次，调整完就必须退出，不然可能发生某些情况
             *   下面的执行已经无意义了
             */
            return ;
        }


        // 右旋转 右矮
        // 左子树高度 > 右子树
        if(leftHeight() - rightHeight() > 1){
            if(left != null && left.rightHeight() > left.leftHeight()){
                // 如果左子树的右子树高度大于左子树的左子树
                // 那么先进行左旋转
                left.leftRotate();
                // 然后再右旋转
                rightRotate();
            } else {
                 // 右旋转
                rightRotate();
            }
        }