AVL树：平衡二叉查找树的奥秘

一、原理

1、概念

AVL树自平衡，二叉查找树，左右子树都是AVL树，且左右子树的高度差的绝对值不超过1，通过控制高度差曲控制平衡。每个结点都有一个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，任何平衡因子为0/1/-1。

此为标准图

此为错误图形，结点10的右边高度为2左边为0，平衡因子为2，不平衡。

AVL结构

2、平衡因子

平衡因子=右子树高度-左子树高度，只有子树高度变化时才会影响当前节点的平衡因子，新增在右++，新增在左，--

二、旋转

1、原则

a、保持搜索树的规则

b、让旋转的树从不满足变平衡，其次减低旋转树的高度

旋转有4种：左旋/右旋/左右双旋/右左双旋

2、右单旋

如图

3、左单旋

与右单旋类似（不再进行画图叙述）

4、左右双旋

如图，只是进行简单的单旋不能够使AVL树平衡，所以必须进行双旋，这里以左右双旋进行演示

5、右左双旋

6、查找