[TOC] ## 概述 二叉查找树的树高度影响了查找的效率，需要尽量减小树的高度，AVL树正是这样的树。 AVL树是一棵严格自平衡的二叉查找树,这是较早发明的平衡二叉树。 为了维持AVL树的特征，每次添加和删除元素都需要一次或多次旋转来调整树的平衡。调整的依据来自于二叉树节点的平衡因子：节点的左子树与右子树的高度差称为该节点的平衡因子，约束范围为`[-1，0，1]`。 ## AVL树添加元素 1. 在右子树上插上右儿子导致失衡，左旋，转一次。 2. 在左子树上插上左儿子导致失衡，右旋，转一次。 3. 在左子树上插上右儿子导致失衡，先左后右旋，转两次。 4. 在右子树上插上左儿子导致失衡，先右后左旋，转两次。