自平衡二叉搜索树（AVL）
简述
AVL树是计算机科学中最早被发明的自平衡二叉搜索树，顾名思义，AVL首先是一颗平衡树，其次它能够实现自平衡。
平衡因子
AVL树引入了平衡因子（Balance Factor）的概念，即任意一个节点的左右子树的最大高度差为1，因此平衡因子的取值范围是：{-1, 0, 1}。因此，AVL树也被称为高度平衡树。
复杂度
时间复杂度
由于AVL树一直都处于高度平衡的状态，所以其查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)。
空间复杂度
AVL树的空间复杂度只与节点个数相关，因此为O(n)。
四种旋转
由于AVL树需要时刻保持平衡状态，因此在每一次插入或删除后都可能需要进行旋转操作，以确保插入或删除后的AVL树仍然处于平衡状态。
AVL旋转主要包括四种基础旋转，分别是：
- 左旋转
- 右旋转
- 左右旋转：先进行一次左旋转，再进行一次右旋转
- 右左旋转：先进行一次右旋转，再进行一次左旋转
优缺点
优点
AVL树的优势源于它的高度平衡，不管是查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)。
不足
AVL树不足是为了维持高度平衡，节点需要存储额外的信息，比如每个节点需要存储一个平衡因子（至少是一个整数类型）。
此外，由于AVL树每次插入或删除操作后都可能需要进行旋转操作，所以调整次数会比较频繁，导致维护成本偏高。
适用场景
鉴于AVL树的优缺点，AVL树适用于查询操作远大于插入或删除的场景，比如数据库。