前言
最近在复习数据结构，学习了一下 AVL 树，现记录如下。
什么是 AVL 树
AVL 树是一种平衡二叉查找树(self-balancing binary search tree),由苏联两位科学家 Georgy Adelson-Velsky 和 Evgenii Landis 于1962年在论文《An algorithm for the organization of information》中首次提出。
AVL 树的性质
AVL 是一个平衡二叉查找树，首先它应是一个二叉查找树（又称二叉排序树），因此，它首先具备如下特性:
- 若左子树不空，则左子树上所有结点的值均小于它的根结点的值。
- 若右子树不空，则右子树上所有结点的值均大于它的根结点的值。
- 左、右子树也分别为二叉排序树。
AVL 引入了平衡因子，即：
- 每个节点的左右子树高度之间的差异小于或等于1。
AVL 树的旋转
通过对节点的旋转来重新平衡树，通常对 AVL 树的旋转有以下四种情况：
LL(Left Left Case):
LR(Left Right Case):
RR(Right Right Case):
RL(Right Left Case):
p.s. 以上图片通过 draw.io 绘制而成，凑活能看（
再放一张 gif，便于理解，图源来自 Wikipedia:
AVL树的时间空间复杂度
以下图表来源于Wikipedia.
| Algorithm | Average | Worst case |
|---|---|---|
| space | O(n) | O(n) |
| search | O(log n) | O(log n) |
| insert | O(log n) | O(log n) |
| delete | O(log n) | O(log n) |