AVL树（得名于发明者G. M. Adelson-Velsky 和 E. M. Landis）本质上是一棵带有平衡条件的二叉搜索树。AVL树具有以下2个性质：
- 左子树和右子树的深度之差的绝对值不超过
1； - 左子树和右子树全都是
AVL树。
其中为了度量左右子树的深度之差，我们引入平衡因子(BF)的概念。
平衡因子： 某个节点的左子树的高度减去右子树的高度得到的差值。
对于一棵 AVL树，里面的所有节点的平衡因子只能取值于-1、0、1，否则，AVL树将是不平衡的并且需要平衡调整。
1. AVL 树平衡调整
二叉树的平衡化有两大基础操作： 左旋（rotate left）和右旋（rotate right）。
左旋，即是逆时针旋转，以某个节点作为旋转点，其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变；
右旋，即是顺时针旋转，以某个节点作为旋转点，其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变。
这种旋转在整个平衡化过程中可能进行一次或多次，这两种操作都是从失去平衡的最小子树根节点开始的(即离插入节点最近且平衡因子超过1的祖节点)。
造成失衡一共有 4 种情况：LL型、LR型、RL型、RR型，如下图所示。
LL型平衡调整：对节点C右旋即可。
LR型平衡调整：先对A进行一次左旋再对C进行一次右旋。
RL型平衡调整：先对C进行一次右旋再对A进行一次左旋。
RR型平衡调整：对节点A左旋即可。
2. 模拟建 AVL 树
按照整数序列 {4,5,7,2,1,3,6} 依次插入AVL树。
由于AVL树必须保证左右子树平衡(左子树和右子树的深度之差的绝对值不超过1)，
所以在插入的时候很容易出现不平衡的情况，一旦这样，就需要进行旋转以求达到平衡。
正是由于这种严格的平衡条件，导致AVL需要花大量时间在调整上，故AVL树一般适用于查询场景， 而不适用于增删频繁的场景。