1. 什么是AVL树

1.1. 简介

AVL树又称为高度平衡的二叉搜索树，目的在于尽量降低二叉树的高度，减少平均搜索长度。

1.2. AVL树的性质

  1. 左子树和右子树高度差的绝对值不超过1
  2. 树中的每一个左子树和右子树都是AVL树
  3. 每一个节点都有一个平衡因子，AVL树中任意节点的平衡因子可取值为-1，1，0

（平衡因子就是 右子树的高度-左子树的高度）

2. 插入、删除、查找效率

一棵AVL树有N个节点，高度可以保持在log2N
插入、删除、查找的时间复杂度是O(log2N)

3. 平衡因子更新规则

  1. 左子树插入节点，该节点的父节点bf -= 1
  2. 右子树插入节点，该节点的父节点bf += 1

4. AVL树的插入

  1. 当插入一个节点后当前节点的父节点的平衡因子变为0，说明当前树是平衡的，不会对上层节点产生影响，所以结束更新直接返回。

  2. 假如插入节点之后该节点的父节点平衡因子变为1或者-1，此时说明之前父节点的平衡因子是0，那就破坏了平衡，那就会对上层节点的平衡性产生影响。此时就需要不断循环向上层更新，只要上层是1或者-1，循环就无法停下，直到父节点为根节点为止，才算插入完毕。

  3. （循环向上层更新父节点出现的）如果父节点的平衡因子变成-2 或者2，那么就要进行旋转，更新节点的bf值，调整树的高度。

  4. 节点的平衡因子为-3 或者3，这种情况是不可能出现的，如果有说明原来的树就不是AVL树。我们要保证每个树再插入之前都是一颗AVL树。

5. 判断一棵树是否为AVL树

5.1. 递归判断

  1. class Solution {
  2.     public boolean isBalanced(TreeNode root) {
  3.         if(root == null){
  4.             return true;
  5.         }
  6.         int left = maxDepth(root.left);
  7.         int right = maxDepth(root.right);
  8.         return (Math.abs(left-right)<2)&&isBalanced(root.left)&&isBalanced(root.right);
  9.     }
  10.     public static int maxDepth(TreeNode root){
  11.         if(root == null){
  12.             return 0;
  13.         }
  14.         int left = maxDepth(root.left);
  15.         int right = maxDepth(root.right);
  16.         return (left>right?left:right)+1;
  17.     }
  18. }

5.2. 迭代判断

class Solution {
    public boolean isBalanced(TreeNode root) {
        return function(root).balance;
    }
    public IsBalance function(TreeNode root){
        IsBalance res = new IsBalance();
        res.height = 0;
        res.balance = true;
        if(root == null){
            return res;
        }
        IsBalance lres = new IsBalance();
        lres = function(root.left);
        if(lres.balance==false){
            return lres;
        }
        IsBalance rres = new IsBalance();
        rres = function(root.right);
        if(rres.balance==false){
            return rres;
        }
        res.height = (lres.height>rres.height)?lres.height+1:rres.height+1;
        res.balance = Math.abs(lres.height-rres.height)<2;
        return res;
    }

    class IsBalance{
        public int height;
        public boolean balance;
    }
}