AVL树定义

AVL树本质上还是一棵二叉搜索树，它的特点是：

• 本身首先是一棵二叉搜索树。
• 带有平衡条件：每个结点的左右子树的高度之差的绝对值最多为1。

AVL树的平衡化处理

向AVL树插入结点可能造成不平衡，此时要调整树的结构，使之重新达到平衡

在一棵AVL树上插入结点可能会破坏树的平衡性，需要平衡化处理恢复平衡，且保持BST的结构性质。 若用Y表示新插入的结点，A表示离新插入结点Y最近的，且平衡因子变为±2的祖先结点。

可以用4种旋转进行平衡化处理:

1. LL型：新结点Y 被插入到 A 的左子树的左子树上（顺）
2. RR型：新结点Y 被插入到 A 的右子树的右子树上（逆）
3. LR型：新结点Y 被插入到 A 的左子树的右子树上（逆、顺）
4. RL型：新结点Y 被插入到 A 的右子树的左子树上（顺、逆）

1.LL型：新结点Y 被插入到 A 的左子树的左子树上（顺）

2.RR型：新结点Y 被插入到 A 的右子树的右子树上（逆）

LR型：新结点Y 被插入到 A 的左子树的右子树上(逆,顺)

RL型：新结点Y 被插入到 A 的右子树的左子树上(顺, 逆)

AVL树的插入操作与建立

• 对于一组关键字的输入序列，从空开始不断地插入结点，最后构成AVL树
• 每插入一个结点后就应判断从该结点到根的路径上有无结点发生不平衡
• 如有不平衡问题，利用旋转方法进行树的调整，使之平衡化
• 建AVL树过程是不断插入结点和必要时进行平衡化的过程

示例：

假设 25，27，30，12, 11，18，14，20，15，22 是一关键字序列，并以上述顺序建立AVL树。

示例：假设25，27，30，12， 11，18，14，20，15，22 是一关键字序列，并以上述顺序建立AVL树。

 

AVL树的删除操作

删除与插入操作是对称的（镜像，互逆的）：

• 删除右子树结点导致失衡时，相当于在左子树插入导致失衡，即LL或LR；
• 删除左子树结点导致失衡时，相当于在右子树插入导致失衡，即RR或RL；

删除操作可能需要多次平衡化处理

• 因为平衡化不会增加子树的高度，但可能会减少子树的高度。
• 在有可能使树增高的插入操作中，一次平衡化能抵消掉树增高；
• 而在有可能使树减低的删除操作中，平衡化可能会带来祖先结点的不平衡。
• 因此，删除操作可能需要多次平衡化处理。

示例：删除15，2次旋转到根