平衡二叉树

平衡二叉树(AVL)

• 平衡二叉树(AVL)
  • 背景引入
  • 基本介绍
  • 实现思路
  • 代码实现

背景引入

二叉排序树可能的问题：

给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST)，并分析问题所在。

BST存在的问题分析：

（1）左子树全部为空，从形式上看，更像一个单链表。
（2）插入速度没有影响
（3）查询速度明显降低（因为需要依次比较），不能发挥BST
的优势，因为每次还需要比较左子树，其查询速度比单链表还慢
（4）解决方案-平衡二叉树(AVL)

基本介绍

（1）平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树，可以保证查询效率较高。

（2）平衡二叉树具有以下特点：

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

实现思路

（1）每次添加都要判断左右子树的高度差

（2）如果高度差大于1

• 如果左子树高度更高，执行右旋转
• 如果右子树高度更改，执行左旋转

（3）平衡方法

（3.1）右旋转

• 新建结点，值为当前结点
• 新节点的右子树指向当前结点的右子树
• 新节点的左子树指向当前结点的左子树的右子树
• 使当前结点的值等于右子结点的值
• 使当前结点的右子树指向右子树的右子树
• 使当前节点的左子树指向新结点

（3.2）左旋转

• 新建结点，值为当前结点
• 新节点的左子树指向当前结点的左子树
• 新节点的右子树指向当前结点的右子树的左子树
• 使当前结点的值等于左子结点的值
• 使当前结点的左子树指向左子树的左子树
• 使当前节点的右子树指向新结点

（4）双旋转问题

虽然每次添加节点都会执行平衡过程（左旋转或者右旋转），但是对于一些特殊的二叉树，单次左旋转或者右旋转并不能平衡二叉树，所以要增加双旋转的情况。

在步骤（2）中

• 如果右子树高度更高，且它的右子树的左子树高度大于右子树高度，则先对右子树进行右旋转，再对当前树进行左旋转。

• 如果左子树高度更高，且它的左子树的右子树高度大于左子树高度，则先对左子树进行左旋转，再对当前树进行右旋转。

代码实现

public class AVLTree extends BinarySortTree {

    public static void main(String[] args) {
//        int[] arr = {};
        int[] arr = {10, 11, 7, 6, 8, 9, 4, 3, 6, 5, 7, 8, 44, 1, 2, 14, 25, 36, 19, 15};
        AVLTree avlTree = new AVLTree();

        // 添加结点
        for (int val : arr) {
            avlTree.add(new AVLNode(val));
        }
        // 遍历
        avlTree.infixOrder();
        System.out.println("\n平衡后树的高度" + ((AVLNode) (avlTree.getRoot())).height());
        System.out.println("平衡前树的左子树高度" + ((AVLNode) (avlTree.getRoot())).leftHeight());
        System.out.println("平衡前树的右子树高度" + ((AVLNode) (avlTree.getRoot())).rightHeight());
    }
}

class AVLNode extends Node {

    public AVLNode(int val) {
        super(val);
    }

    @Override
    public void add(Node node) {
        super.add(node);
        if (rightHeight() - leftHeight() > 1) {
            // 如果它的右子树的左子树高度大于右子树高度（双旋转）
            if (right != null && ((AVLNode) right).leftHeight() > ((AVLNode) right).rightHeight())
                // 先对当前这个结点的右节点进行右旋转
                ((AVLNode) right).rightRotate();
            // 再对当前结点进行左旋转
            leftRotate();
            return;// 重要
        }

        if (leftHeight() - rightHeight() > 1) {
            // 如果它的左子树的右子树高度大于左子树高度
            if (left != null && ((AVLNode) left).rightHeight() > ((AVLNode) left).leftHeight())
                // 先对当前这个结点的左节点进行左旋转
                ((AVLNode) left).leftRotate();
            // 再对当前结点进行右旋转
            rightRotate();
        }
    }

    // 左旋转
    public void leftRotate() {
        // 创建一个新的节点,值等于当前根节点的值
        AVLNode newNode = new AVLNode(val);
        // 把新节点的左子树设置了当前节点的左子树
        newNode.left = left;
        // 把新节点的右子树设置为当前节点的右子树的左子树
        newNode.right = right.left;
        // 把当前节点的值换为右子节点的值
        val = right.val;
        // 把当前节点的右子树设置成右子树的右子树
        right = right.right;
        // 把当前节点的左子树设置为新节点
        left = newNode;
    }

    // 右旋转
    public void rightRotate() {
        AVLNode newNode = new AVLNode(val);
        newNode.right = right;
        newNode.left = left.right;
        val = left.val;
        left = left.left;
        right = newNode;
    }

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

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

    // 返回以当前结点为根节点的书的高度
    public int height() {
        return Math.max(
                left == null ? 0 : ((AVLNode) left).height(),
                right == null ? 0 : ((AVLNode) right).height()
        ) + 1;
    }
}