数据结构（混合式）23-24-1 AVL树复习笔记

本资料由 @BlockLune 整理，课本为《数据结构（C 语言）第 2 版慕课版》2020 年 2 月第 2 版，2022 年 12 月第 11 次印刷。

注意：

本资料知识点来自于对应的复习 PPT，但具体实现更多参考自 Princeton Algs4、GeeksforGeeks 的内容。这导致文中的实现并不一定与课本实现完全一致。
本资料免费分享于 NJUPTFreeExams，请勿商业使用！如有错别字等错误，请在 Issues 中提出，感谢！

什么是 AVL 树

AVL 树是一种自平衡的二叉搜索树（BST），对于其中的每个结点，它的左子树和右子树的高度差均不会超过 1。

为什么需要 AVL 树

大多数对 BST 进行的操作操作（如搜索、最大值、最小值、插入、删除…等）都需要 $O(h)$ 时间，其中 h 是 BST 的高度。对于倾斜的二叉树，这些操作的成本可能会变成 $O(n)$ 。如果我们确保在每次插入和删除后，树的高度都保持 $O(log(n))$ ，那么我们就能保证所有这些操作的上限都是 $O(log(n))$ 。AVL 树就确保了这一点，使对它进行的操作能在 $O(log(n))$ 的复杂度下进行。

插入操作

我们必须确保插入新节点后的 AVL 树仍然是平衡的，即“左节点 < 根节点 < 右节点”。这是通过两种操作来实现的：

左旋（Left Rotation）
右旋（Right Rotation）

T1、T2 和 T3 是树的子树，以 y（左侧）或 x（右侧）为根。

     y                               x
    / \     Right Rotation          /  \
   x   T3   - - - - - - - >        T1   y
  / \       < - - - - - - -            / \
 T1  T2     Left Rotation            T2  T3

在上边两棵树中的所有关键字值都遵循“keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)”，满足 BST 的性质。

插入操作的参考步骤

记新插入的节点为 w，将 w 照常插入 BST。
从 w 开始向根遍历，找到第一个非平衡节点，记为 z。记在从 w 到 z 的路径上的 z 的儿子为 y，孙子为 x。
对四种可能的情形，通过旋转操作，重新平衡以 z 为根的子树。

四种可能的情形

下边符号表示中，T1、T2、T3 和 T4 都是子树。

左左

左左情形：y 是 z 的左孩子，x 是 y 的左孩子

         z                                      y
        / \                                   /   \
       y   T4      Right Rotate (z)          x      z
      / \          - - - - - - - - ->      /  \    /  \
     x   T3                               T1  T2  T3  T4
    / \
  T1   T2

左右

左右情形：y 是 z 的左孩子，x 是 y 的右孩子

     z                               z                           x
    / \                            /   \                        /  \
   y   T4  Left Rotate (y)        x    T4  Right Rotate(z)    y      z
  / \      - - - - - - - - ->    /  \      - - - - - - - ->  / \    / \
T1   x                          y    T3                    T1  T2 T3  T4
    / \                        / \
  T2   T3                    T1   T2

右右

右右情形：y 是 z 的右孩子，x 是 y 的右孩子

  z                                y
 /  \                            /   \
T1   y     Left Rotate(z)       z      x
    /  \   - - - - - - - ->    / \    / \
   T2   x                     T1  T2 T3  T4
       / \
     T3  T4

右左

右左情形：y 是 z 的右孩子，x 是 y 的左孩子

   z                            z                            x
  / \                          / \                          /  \
T1   y   Right Rotate (y)    T1   x      Left Rotate(z)   z      y
    / \  - - - - - - - - ->     /  \   - - - - - - - ->  / \    / \
   x   T4                      T2   y                  T1  T2  T3  T4
  / \                              /  \
T2   T3                           T3   T4

删除操作

类似于插入操作，我们仍然需要借助旋转操作来让 AVL 树保持平衡。

删除操作的参考步骤

记需要删除的节点为 w，将 w 照常从 BST 中删除。
从 w 开始向根遍历，找到第一个非平衡节点，记为 z。将 z 的较高的孩子记为 y，将 y 的较高的孩子记为 x。(注意此处的记法与插入操作不同)
对四种可能的情形，通过旋转操作，重新平衡以 z 为根的子树。四种可能情形及调整方法与插入操作中的完全相同。
注意：与插入操作不同，调整完以 z 为根的子树的平衡性后，可能需要继续向上遍历调整以 z 的祖先为根的子树的平衡性，直到调整完整棵树的平衡性。

各操作的复杂度

操作	时间复杂度	空间复杂度
查找元素	$O(\log n)$	$O(1)$
插入元素	$O(\log n)$	$O(1)$
删除元素	$O(\log n)$	$O(1)$
查找最小元素	$O(\log n)$	$O(1)$
查找最大元素	$O(\log n)$	$O(1)$
查找前驱元素	$O(\log n)$	$O(1)$
查找后继元素	$O(\log n)$	$O(1)$
旋转操作（左旋和右旋）	$O(1)$	$O(1)$
平衡因子更新	$O(1)$	$O(1)$

数据结构（混合式）23-24-1 AVL树 复习笔记