AVL树
AVL树是在二叉搜索树上加上自平衡的功能。
AVL树是最早发明的自
平衡二叉搜索树之一。AVL取名于两位发明者的名字：G.M.
Aelson-Velsky和E.M.Landis。
1.1 平衡因子
平衡因子(Balance Factor)：某节点的左右子树高度差
平衡因子 = 左子树高度 - 右子树高度
1.2 AVL树特点
- 每个节点的平衡因子只可能是1、0、-1(绝对值 <= 1，如果超过1，称之为"失衡")
- 每个节点的左右子树高度差的绝对值不超过1
- 搜索、添加、删除的时间复杂度是O(logn)
普通二叉搜索树与AVL树对比
1.3 添加导致的失衡
示例：往下面这棵子树中添加13
添加之前
添加之后
添加的最坏情况：可能会导致所有祖先节点都失衡。(红色的线所涉及的祖先节点都可能失衡)
父节点(12)、非祖先节点(4、6、8、16)都不可能失衡。
1.3.1 LL、RR、LR、RL总结
在插入操作中，只要将
最小不平衡子树调整平衡，则其他祖先节点都会恢复平衡。查找最小不平衡子树的方法：
从插入的节点开始，找到第一个失衡的祖先节点。
调整最小不平衡子树(g是最小不平衡子树的根节点)
LL—在
g的左孩子的左子树中插入节点导致的不平衡
- 调整：g的
左孩子右上旋- 对g进行右旋转
RR—在
g的右孩子的右子树中插入节点导致的不平衡
- 调整：g的
右孩子左上旋- 对g进行左旋转
LR—在
g的左孩子的右子树中插入节点导致的不平衡
- 调整：g的
左孩子的右孩子，先左上旋再右上旋- 先对p进行左旋转，再对g进行右旋转
RL—在
g的右孩子的左子树中插入节点导致的不平衡
- 调整：g的
右孩子的左孩子，先右上旋再左上旋- 先对p进行右旋转，再对g左旋转
记忆：
左孩子—右上旋
右孩子—左上旋说明：n—node、p—parent、g—grandparent
p是g的左右子树中高度较高的那个节点
n是p的左右子树中高度较高的那个节点
1.3.2 LL图示
1.3.3 RR图示
1.3.4 LR图示
1.3.5 RL图示
1.4 删除导致的失衡
示例：删除子树中的16
删除之前
删除之后
删除节点之后可能会导致
父节点或祖先节点失衡(只有1个节点会失衡)，其他节点，都不可能失衡。
1.4.1 LL图示
1.4.2 RR图示
1.4.3 LR图示
1.4.4 RL图示
1.5 总结
- 添加
- 可能会导致所有祖先节点都失衡
- 只要让高度最低的失衡节点恢复平衡，整棵树就会恢复平衡【仅需O(1)次调整】
- 删除
- 可能会导致父节点或祖先节点失衡
(只有1个节点会失衡)- 让父节点恢复平衡后，可能会导致更高层的祖先节点失衡【最多需要O(logn)次调整】
- 平衡时间复杂度
- 搜索：O(logn)
- 添加：O(logn)，仅需O(1)次的旋转操作
- 删除：O(logn)，最多需要O(logn)次的旋转操作