平衡二叉查找树（AVL） ​

平衡二叉查找树具有如下几个性质：

1. 可以是空树。
2. 假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1。

平衡二叉树是为了解决二叉查找树中出现链式结构（只有左子树或只有右子树）的情况，这样的情况出现后对我们的查找没有一点帮帮助，反而增加了维护的成本。

平衡因子使用两个字母来表示。第一个字母表示最小不平衡子树根结点的平衡因子，第二个字母表示最小不平衡子树较高子树的根结点的平衡因子。根据不同的情况使用不同的方法来调整失衡的子树。

详细资料可以参考： ​

• 《平衡二叉树，AVL 树之图解篇》