一、平衡二叉树定义

平衡二叉树又称AVL树。它可以是一颗空树，或者具有以下性质的二叉排序树：它的左子树和右子树的高度之差(平衡因子)的绝对值不超过1且它的左子树和右子树都是一颗平衡二叉树。

从上面简单的定义我们可以得出几个重要的信息：

• 平衡二叉树又称AVL树
• 平衡二叉树必须是二叉排序树
• 每个节点的左子树和右子树的高度差至多为1。

树的高度和深度本质区别：深度是从根节点数到它的叶节点，高度是从叶节点数到它的根节点。

二、这货还是不是平衡二叉树？

判断一棵平衡二叉树（AVL树）有如下必要条件：

• 条件一：必须是二叉搜索树。
• 条件二：每个节点的左子树和右子树的高度差至多为1。

三、平衡因子

四、如何保持平衡二叉树平衡？

由于普通的二叉查找树会容易失去”平衡“，极端情况下，二叉查找树会退化成线性的链表，导致插入和查找的复杂度下降到 O(n) ，所以，这也是平衡二叉树设计的初衷。那么平衡二叉树如何保持”平衡“呢？

不难看出平衡二叉树是一棵高度平衡的二叉查找树。所以，要构建跟维系一棵平衡二叉树就比普通的二叉树要复杂的多。在构建一棵平衡二叉树的过程中，当有新的节点要插入时，检查是否因插入后而破坏了树的平衡，如果是，则需要做旋转去改变树的结构。

左旋：

试着用动态和下面的左旋结果图分析分析，想象一下，估计分分钟明白左旋！！！