二叉平衡树（AVL树）是一种特殊的的二叉搜索树，由Adelson-Velsky和Landis在1962年提出。它通过自动维护树的平衡性来保证所有操作的时间复杂度都是O(log n)。AVL树的查找，插入，构建，删除，的过程与二叉搜索树相同，失衡的时候需要作出相应调整。

AVL树的基本概念

平衡因子（Balance Factor）：

每个节点的平衡因子定义为：左子树高度 – 右子树高度

• 平衡因子只能是 -1、0、1
• 如果某节点的平衡因子为 ±2，说明树失衡了，则需要进行旋转调整

平衡条件：

对于AVL树中的任意节点：

• 左右子树的高度差不超过1
• 左右子树本身也是AVL树

失衡处理

AVL树通常4种失衡情况，通过四种旋转操作来维持平衡：

LL型：将失衡节(图中C节点)点右旋

若失衡节点的左孩子(图中B节点)左右孩子都存在，即发生冲突时，将冲突节点置为旋转节点的孩子节点

RR型：将失衡节点(图中A节点)左旋

若失衡节点的右孩子(图中B节点)左右孩子都存在，即发生冲突时，将冲突节点置为旋转节点的孩子节点

LR型：先将左孩子左旋，再将失衡节点右旋

RL型：先将右孩子右旋，再将失衡节点左旋

写在最后

看完上面一大段，可能容易被搞懵，什么左旋什么右旋什么LR什么RL，安啦安啦，看着图稍微分析一下不难的啦。LL以及RR就不讲了，这个好记。LR以及RL，先将孩子节点单独拎出来操作，是右孩子就对其进行右旋，左孩子就对其进行左旋。随后再对失衡节点往相反方向旋转即可。