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