第8章. AVL树

AVL树

AVL树是在二叉搜索树上加上自平衡的功能。

AVL树是最早发明的自平衡二叉搜索树之一。

AVL取名于两位发明者的名字：G.M.Aelson-Velsky和E.M.Landis。

1.1 平衡因子

平衡因子(Balance Factor)：某节点的左右子树高度差

平衡因子 = 左子树高度 - 右子树高度

1.2 AVL树特点

1. 每个节点的平衡因子只可能是1、0、-1(绝对值 <= 1，如果超过1，称之为"失衡")
2. 每个节点的左右子树高度差的绝对值不超过1
3. 搜索、添加、删除的时间复杂度是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)次的旋转操作