平衡二叉树(AVL树）

逸帅

平衡二叉树(AVL树）

1、为什么要平衡二叉树

如果由数组{1, 2, 3, 4, 5}来构建一颗二叉排序树，得到的二叉树不仅没有体现其特点，反而还退化成了链表，且因为要判断左子树，查询效率比链表还低

2、平衡二叉树的介绍

• 平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树，可以保证查询效率较高
• 具有以下特点：
  • 它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树
  • 平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等

3、平衡二叉树的应用

3.1、左旋转

3.1.1、应用场景

右子树的高度高于左子树，且差值大于1，所以需要进行左旋转，来降低右子树的高度

3.1.2、思路分析

1. 创建一个newRoot新节点，值为当前节点root的值
2. 让新节点的左子树newRoot.left指向当前节点root.left的左子树
3. 让新节点的右子树newRoot.right指向当前节点的右子树的左子树root.right.left
4. 将当前节点的值root.value改为其右子树的值root.right.value
5. 将当前节点的右子树变为其右子树的右子树root.right = root.right.right
6. 让当前节点的左子树指向新节点root.left = newRoot

3.1.3、代码实现

注意：

在获取树的高度的时候，精髓在最后面的+1，只要left或者right有值，就将要返回的值+1，然后做递归
当左边的节点为null了，左边的递归就结束了，右边同理

//核心代码
public void leftRotate() {
        Node newRoot = new Node(root.value);
        newRoot.left = root.left;
        newRoot.right = root.right.left;
        root.value = root.right.value;
        root.right = root.right.right;
        root.left = newRoot;
    }

        //取当前节点树的高度
    public int getHeight() {
        //精髓在最后面的+1，只要left或者right有值，就将要返回的值+1，然后做递归
        //当左边的节点为null了，左边的递归就结束了，右边同理
        return Math.max(left == null ? 0 : left.getHeight(), right == null ? 0 : right.getHeight()) + 1;
    }

    //返回左子树的高度
    public int leftHeight() {
        if (left == null) {
            return 0;
        } else {
            return left.getHeight();
        }
    }

    //返回右子树的高度
    public int rightHeight() {
        if (right == null) {
            return 0;
        } else {
            return right.getHeight();
        }
    }

3.2、右旋转

3.1.1、应用场景

左子树的高度高于右子树，且差值大于1，所以需要进行右旋转，来降低左子树的高度

3.1.2、思路分析(和左旋转完全相反)

1. 创建一个newRoot新节点，值为当前节点root的值
2. 让新节点的右子树newRoot.right指向当前节点root.right的右子树
3. 让新节点的左子树newRoot.left指向当前节点的左子树的右子树root.left.right
4. 将当前节点的值root.value改为其左子树的值root.left.value
5. 将当前节点的左子树变为其左子树的右子树root.left = root.left.left
6. 让当前节点的右子树指向新节点root.right = newRoot

3.1.3、代码实现

public void rightRotate(){
        Node newRoot = new Node(root.value);
        newRoot.right = root.right;
        newRoot.left = root.left.right;
        root.value = root.left.value;
        root.left = root.left.left;
        root.right = newRoot;
    }

        //取当前节点树的高度
    public int getHeight() {
        //精髓在最后面的+1，只要left或者right有值，就将要返回的值+1，然后做递归
        //当左边的节点为null了，左边的递归就结束了，右边同理
        return Math.max(left == null ? 0 : left.getHeight(), right == null ? 0 : right.getHeight()) + 1;
    }

    //返回左子树的高度
    public int leftHeight() {
        if (left == null) {
            return 0;
        } else {
            return left.getHeight();
        }
    }

    //返回右子树的高度
    public int rightHeight() {
        if (right == null) {
            return 0;
        } else {
            return right.getHeight();
        }
    }

3.3 双向旋转

3.3.1、应用场景

某些时候，只进行左旋转或者右旋转，并不能将二叉排序树变为平衡二叉树。这时就需要进行双旋转，即同时进行左旋转和右旋转

3.3.2、思路分析

• 进行左旋转时，如果root节点的右子树root.right的左子树root.right.left高于其右子树root.right.right，需要先把root节点的右子树root.right.rightRotate()进行右旋转，再把root节点进行左旋转root.leftRotate()
• 进行右旋转时，如果root节点的左子树root.left的右子树root.left.right，高于其左子树root.left.left，需要先把root节点的左子树root.left.leftRotate进行左旋转，再对root节点进行右旋转root.rightRotate()

3.3.3、代码实现

//右边比左边高，左旋转
        if ((avlTree.getRoot().rightHeight() - avlTree.getRoot().leftHeight()) > 1) {
            //左旋转判断是否要进行双向选择
            /**
             * 进行左旋转时，如果root节点的右子树`root.right`的左子树`root.right.left`高于其右子树`root.right.right`，
             * 需要先把root节点的右子树`root.right.rightRotate()`进行右旋转，
             * 再把root节点进行左旋转`root.leftRotate()`
             */
            if (avlTree.getRoot().right.rightHeight() > avlTree.getRoot().right.leftHeight()){
                //把root的右子树，进行右旋转
                avlTree.rightRotate(avlTree.getRoot().right);
            }
            avlTree.leftRotate(avlTree.getRoot());
            System.out.println(avlTree.getRoot().leftHeight());
            System.out.println(avlTree.getRoot().rightHeight());
        }
        //左边比右边高，右旋转
        if ((avlTree.getRoot().leftHeight() - avlTree.getRoot().rightHeight()) > 1) {
            //右旋转判断是否要进行双向选择
            /**
             * 进行右旋转时，如果root节点的左子树`root.left`的右子树`root.left.right`，高于其左子树`root.left.left`，
             * 需要先把root节点的左子树`root.left.leftRotate`进行左旋转，
             * 再对root节点进行右旋转`root.rightRotate()`
             */
            if (avlTree.getRoot().left.rightHeight() > avlTree.getRoot().left.leftHeight()){
                //把root的左子树，进行左旋转
                avlTree.leftRotate(avlTree.getRoot().left);
            }
            avlTree.rightRotate(avlTree.getRoot());
            System.out.println(avlTree.getRoot().leftHeight());
            System.out.println(avlTree.getRoot().rightHeight());
        }

3.4 注意点

由于没有参照尚硅谷韩顺平老师的代码写，只按照思路，用自己的代码将其体现了出来。

由代码可以看出，多次获取了avlTree.getRoot，建议把root节点抽出来，这样子节省很多效率，而且代码更规范

return Math.max(left == null ? 0 : left.getHeight(), right == null ? 0 : right.getHeight()) + 1;这一串代码老师讲述的不太清楚，我的理解如下：

在获取树的高度的时候，精髓在最后面的+1，只要left或者right有值，就将要返回的值+1，递归了多少次，就有多少个+1，直到为null时，结束递归，最后加上本身的1，返回的就是层数，右边同理，最后把最大的那个值返回。

Lthero

求解高度用向下递归感觉不好，不如从添加的这个节点向上遍历，上面节点层数逐个加一，计算量会少很多