AVL 树：完整指南与 Python 实现

二叉搜索树中的失衡

二叉搜索树（BST）是一种遵循特定顺序组织数据的二叉树数据结构。每个节点包含一个值，并最多连接两个其他节点：其左子节点和右子节点。在 BST 中，规则是左子节点的值必须小于其父节点的值，右子节点的值必须大于其父节点的值。

BST 在查找特定值时非常高效，因为它允许我们在搜索过程中排除树的大部分。例如，如果我们要在上图的树中查找值 1，我们可以忽略 6 右侧的所有节点。这是因为有序性保证了这些值都大于 6。

理想情况下，每个节点都应将数据一分为二，使得每向下走一步就能排除一半的值，从而实现极快的查找。然而，根据插入顺序的不同，可能会得到一个无法有效分割数据的失衡树。例如，从小到大顺序插入会得到一棵线性树，其性能不比列表更好。

什么是 AVL 树

AVL 树是在二叉搜索树基础上增加了如下性质：

对每个节点而言，其左、右子树的高度差最多为 1。

拆解这个定义：左子树包含该节点左侧的所有节点，右子树包含其右侧的所有节点。树的高度定义为从根节点（最顶层节点）到任意叶子（无子节点）之间最长路径的长度。

节点的平衡因子计算为其左子树与右子树的高度差：

balance(N) = height(N 的左子树) - height(N 的右子树)

例如，balance(6) = 1 - 3 = -2。

在图中，节点6的平衡因子为 -2，表明该树不符合 AVL 树的标准。要被视为 AVL 树，每个节点的平衡因子必须是 -1、0 或 1。

为何使用 AVL 树

二叉搜索树中查询的效率取决于树的高度。在最坏情况下，需要检查的节点数等于树的高度。BST 的关键问题在于树的高度可能与节点数量相当，也就是说一次查询可能需要检查每一个节点。

令 M(h) 表示要使二叉搜索树达到高度 h 所需的最少节点数。对简单的 BST，我们观察到 M(h) = h，即用 h 个节点即可达到高度 h。这意味着 BST 的高度会随节点数线性增长，导致查询时间与数据集规模成正比。

AVL 树具有对数高度的证明

考虑要构造一棵高度为 h 的 AVL 树所需的最少节点数 M(h)。由于是 AVL 树，需要注意每个节点的平衡因子只能是 -1、0 或 1。

然而，在我们假设为了达到高度 h 使用尽可能少的节点时，根的平衡不可能为 0。否则，我们可以从左侧或右侧移除一个节点，使其平衡变为 -1 或 1，仍然是有效的 AVL 树。

假设根的平衡为 1（若为 -1，推理是对称的）。这意味着树的结构如下：

另一方面，左右子树也必须分别是高度各自最小节点数的 AVL 树（否则还可以继续移除节点）。整棵树的节点总数等于 1（根）加上左子树节点数再加上右子树节点数。

M(h) = 1 + （L 中的节点数） + （R 中的节点数） = 1 + M(h - 1) + M(h - 2)

随着高度增长，为达到该高度需要更多节点。因此：

M(h - 1) > M(h - 2)

结合两者，可得：

M(h) = 1 + M(h - 1) + M(h - 2) > 1 + 2 × M(h - 2) > 2 × M(h - 2)

我们可重复应用该不等式 h/2 次，直到达到 M(1) = 1 或 M(2) = 2：

M(h) > 2 × M(h - 2) > 2 × 2 × M(h - 4) > 2 × 2 × 2 × M(h - 6) > … > 2(h/2)

为便于理解，下图给出了 h = 7 与 h = 6 时的具体示例：

我们得出结论：高度为 h 的 AVL 树所需的最少节点数至少为2(h/2)：

M(h) > 2(h/2)

两边取以 2 为底的对数，得到：

log2(M(h)) > log2(2(h/2)) = h/2

因此，两边乘以 2 可得：树高至多为节点数量的以 2 为底对数的两倍：

2 × log2(M(h)) > h

我们已经证明：

包含 N 个节点的 AVL 树的高度至多为 2 × log2(N)。

这意味着在 AVL 树中进行查询只需检查数据集中的很小一部分。比如，若有 10 亿条记录，其对数约为 30，这意味着即便有 10 亿个数据点，找到某一条记录也只需检查约 60 个数据点。与最坏情况下需要检查全部 10 亿个数据点的 BST 相比，这是一项显著提升。

如需进一步了解算法的时间复杂度，以及线性时间复杂度与对数复杂度的差异，请参阅这篇关于大 O 表示法与时间复杂度的博文。

用 AVL 树维持平衡

AVL 树通过强制每个节点的平衡因子为 -1、0 或 1 来保证快速查询。为确保每个节点的平衡得以维持，我们需要在插入新值后对树进行再平衡。

在二叉搜索树中，插入操作是从根节点沿路径向下进行。待插入值较小时向左走，否则向右走。

一次插入最多会使高度增加 1。因此，如果插入后不满足平衡性质，意味着原本平衡为 -1 的某个节点现在变为 -2，或原本为 1 的节点现在变为 2。上例就是第一种情况。

单旋转

为恢复平衡，我们依赖树旋转操作。对节点A 进行左旋会将A向左旋转，从而重组树，如下所示：

在该示意图中：

• BL 表示 B 的左子树
• BR 表示其右子树
• AL 表示 A 的左子树

注意旋转后，节点的有序性仍然成立：

1. 节点 A 小于 B，因为 B 原本是它的右子节点。
2. 位于 BL 的节点都大于 A，因为它们位于 A 的右侧。
3. 位于 AL 的节点都小于 B，因为它们小于 A。

右旋与此对称，通过将A向右旋转实现。

让我们通过一个具体示例来修复插入19后出现的失衡：对节点6执行一次左旋。

插入后，我们通过旋转平衡因子为 -2 或 2 的节点来修复失衡。本例中，节点6的平衡因子为 -2，表示树向右倾斜，因此我们进行了左旋（与失衡方向相反的方向）。若平衡因子为 2，则应使用右旋。

双旋转

在前一个示例中，整棵树完全向右倾斜，因此一次左旋即可恢复平衡。但在某些情况下，会出现“之”字形失衡：树向一侧倾斜，而其子树朝相反方向倾斜。为此，我们回到插入19之前的原始树，改为插入7：

此时，整棵树仍向右倾斜，但以10为根的子树却向左倾斜。这种情况下，我们需要先将节点10右旋：

注意节点 B 没有右子节点。我们仍在图中用蓝色显示，以便于可视化。

完成右旋后，回到之前的情形：对6做一次左旋即可恢复平衡：

如何在 Python 中实现 AVL 树

先从节点实现开始。

节点实现

树中的每个节点包含五个属性：

• 其存储的值（self.value）
• 父节点（self.parent）
• 左子节点（self.left）
• 右子节点（self.right）
• 以该节点为根的子树高度（self.height）

class Node:
  def __init__(self, value, parent = None):
    self.value = value
    self.parent = parent
    self.left = None
    self.right = None
    self.height = 1技术支持

我们用值 None 表示缺失的节点。默认 height 设为 1，因为仅包含单个节点的树高度为 1。

为方便树的实现，我们在 Node 类中引入若干方法。

# Inside the Node class
  def left_height(self):
    # Get the heigth of the left subtree
    return 0 if self.left is None else self.left.height
  
  def right_height(self):
    # Get the height of the right subtree
    return 0 if self.right is None else self.right.height
  def balance_factor(self):
    # Get the balance factor
    return self.left_height() - self.right_height()
  def update_heigth(self):
    # Update the heigth of this node
    self.height = 1 + max(self.left_height(),self.right_height())
    
  def set_left(self, node):
    # Set the left child
    self.left = node
    if node is not None:
      node.parent = self
    self.update_heigth()
  
  def set_right(self, node):
    # Set the right child
    self.right = node
    if node is not None:
      node.parent = self
    self.update_heigth()
  def is_left_child(self):
    # Check whether this node is a left child
    return self.parent is not None and self.parent.left == self
  
  def is_right_child(self):
    # Check whether this node is a right child
    return self.parent is not None and self.parent.right == self技术支持

注意我们使用 .set_left() 与 .set_right() 方法分别设置左右子节点。之所以不直接修改 self.left 与 self.right，是因为每当变更子节点时，都需要同时更新新子节点的父节点以及当前节点的高度。

AVL 树实现

AVL 树维护一个参数：树的根，即最顶层节点。

class AVLTree:
  def __init__(self):
    self.root = None技术支持

为维持树的平衡，我们需要实现左右旋。先回顾左旋在示意图中的呈现方式：

# Inside the AVLTree class
  
  def rotate_left(self, a):
    b = a.right
    # 1. The new right child of A becomes the left child of B
    a.set_right(b.left)
    # 2. The new left child of B becomes A
    b.set_left(a)
    return b # 3. Return B to replace A with it技术支持

右旋的实现是对称的：

# Inside the AVLTree class
  
  def rotate_right(self, a):
    b = a.left
    a.set_left(b.right)
    b.set_right(a)
    return b技术支持

借助旋转，我们可以对树进行再平衡。当节点的平衡因子达到 2（树左倾）或 -2（树右倾）时，需要对该节点进行再平衡。总体上有四种情形需要处理：

我们在 .rebalance() 方法中实现上述四种情况。

# Inside the AVLTree class
  
  def rebalance(self, node):
    if node is None:
      # Empty tree, no rebalancing needed
      return None
    balance = node.balance_factor()
    if abs(balance) <= 1:
      # The node is already balanced, no rebalancing needed
      return node
    if balance == 2: 
      # Cases 1 and 2, the tree is leaning to the left
      if node.left.balance_factor() == -1: 
        # Case 2, we first do a left rotation
        node.set_left(self.rotate_left(node.left))
      return self.rotate_right(node)
    # Balance must be -2
    # Cases 3 and 4, the tree is leaning to the left
    if node.right.balance_factor() == 1:
      # Case 4, we first do a right rotation
      node.set_right(self.rotate_right(node.right)) 
    return self.rotate_left(node)技术支持

请注意，在每种情况下，该方法都会返回刚刚完成平衡的子树的根。稍后在再平衡过程中，将使用这个新的子树根来更新父节点的子链接。

向 AVL 树添加节点与普通 BST 类似，但在插入后多了恢复平衡的步骤。在 BST 中添加节点时，我们从根开始向下遍历，每一步将待添加值与当前节点值比较。若更小则向左，否则向右。向下遍历时，要记录父节点，以便将新节点插入为其子节点。

当到达空位置时，有两种情况：

1. 父节点为None，说明树为空，则新节点成为根节点。
2. 已找到父节点，则根据节点值将新节点设置为其左或右子节点。

# Inside the AVLTree class
  def add(self, value):
    self.size += 1
    parent = None
    current = self.root
    while current is not None:
      parent = current
      if value < current.value:
        # Value to insert is smaller than node value, go left
        current = current.left
      else:
        # Value to insert is larger than node value, go right
        current = current.right
    # We found the parent, create the new node
    new_node = Node(value, parent)
    # Case 1: The parent is None so the new node is the root
    if parent is None:
      self.root = new_node
    else:
      # Case 2: Set the new node as a child of the parent
      if value < parent.value:
        parent.left = new_node
      else:
        parent.right = new_node
    # After a new node is added, we need to restore balance
    self.restore_balance(new_node)技术支持

BST 的 .add() 方法与 AVL 树的唯一区别在最后一步：从新插入的节点开始一路回溯到根，逐个对节点调用 .rebalance() 来恢复平衡。

# Inside the AVLTree class
  def restore_balance(self, node):
    current = node
    # Go up the tree and rebalance left and right children
    while current is not None:
      current.set_left(self.rebalance(current.left))
      current.set_right(self.rebalance(current.right))
      current.update_heigth()
      current = current.parent
    self.root = self.rebalance(self.root)
    self.root.parent = None技术支持

注意：当节点已处于平衡状态时，.rebalance() 方法不会做任何改动——它会直接返回该节点本身。因此，在向上回溯时，我们可以同时对左右子树调用它，尽管只有一侧可能失衡，另一侧的调用不会改变树。

回想我们将 .rebalance() 设计为返回（可能已经变化的）子树根节点，其目的正是为了在向上恢复平衡的过程中，更新当前节点的左右子链接。

下图展示了 .restore_balance() 在树上向上执行的步骤。

在该示例中，我们先添加节点8。随后，从该节点开始恢复平衡，并沿树向上逐一检查与再平衡每个遇到节点的左右子树，直至到达节点10。在此之前，对 .rebalance() 的调用均无效果，因为这些节点都处于平衡状态。

然而，当到达节点10时，观察到其左子节点7的平衡因子为 -2，需要进行再平衡。因此调用 .rebalance(7)，从而用新的左子树根节点8替换节点10的左子节点，进而恢复树的平衡。

AVL 树的其他操作

除了在保持平衡的前提下进行插入与删除，AVL 树还支持若干其他关键操作。

最小值与最大值

由于 BST 的有序性，最小值位于树的最左侧节点，最大值位于最右侧节点。

我们实现了两个辅助函数，用于从给定节点开始找到最左与最右的节点。这些函数有助于实现节点删除。

# Inside the AVLTree class
  
  def leftmost(self, starting_node):
    # Find the leftmost node from a given starting node
    previous = None
    current = starting_node
    while current is not None:
      previous = current
      current = current.left
    return previous
  def minimum(self):
    # Return the minimum value in the tree
    if self.root is None:
      raise Exception("Empty tree")
    return self.leftmost(self.root).value技术支持

# Inside the AVLTree class
 
  def rightmost(self, starting_node):
    # Find the rightmost node from a given starting node
    previous = None
    current = starting_node
    while current is not None:
      previous = current
      current = current.right
    return previous
  
  def maximum(self):
    # Fidn the maximum value in the tree
    if self.root is None:
      raise Exception("Empty tree")
    return self.rightmost(self.root).value技术支持

包含关系

要判断树中是否包含某个特定值，我们利用树的有序性引导搜索。从根开始，若目标值小于当前节点则向左，否则向右。若走到树的尽头仍未找到，即表明该值不存在于树中。

为便于此过程，我们实现了辅助方法 .locate_node()。它不仅适用于查找，也适用于删除等操作。此外，我们实现了 .__contains__()，从而可使用 in 运算符简化包含性检查。

# Inside the AVLTree class

  def locate_node(self, value):

    # Returns the node containing a given value or None if no

    # such node exists

    current = self.root

    while current is not None:

      if value == current.value:

        return current

      if value < current.value:

        current = current.left

      else:

        current = current.right

    return None

  def __contains__(self, value):

    node = self.locate_node(value)

    return node is not None技术支持

删除

当待删节点位于树的中间位置时，在 AVL 树中删除会尤为棘手。若该节点是叶子（无子节点），只需根据其是左子还是右子，将父节点的对应指针设为 None 即可删除。

当待删节点是树根时属于特殊情况，此时可将根设为 None 以删除该节点。

# Inside the AVLTree class

  def delete_leaf(self, node):

    if node.parent is None:

      self.root = None

    elif node.is_left_child():

      node.parent.left = None

      node.parent = None

    else:

      node.parent.right = None

      node.parent = None技术支持

要从 AVL 树中删除一个值，首先需使用 .locate_node() 定位包含该值的节点。若其为叶子节点，可用 .delete_leaf() 删除。若不是叶子，直接移除会破坏树的结构。此时需要寻找合适的替代节点：若待删节点有左子，则选择其左子树中的最右节点。这样可确保维持树的有序结构。

下图演示了从树中删除节点 10 的过程。由于它有左子节点，我们用左子树中的最右节点替换之。完成替换后，应从新替换节点的父节点开始对树进行再平衡。

在该示例中，替代节点是叶子节点。但如果替代节点有子节点，需要将这些子节点重新挂接到替代节点的父节点上。由于替代节点是极值节点（最左或最右），它至多只有一个子节点，因此总能完成此类重新挂接。

# Inside the AVLTree class

  def delete(self, value):

    # Delete a value from the tree

    node = self.locate_node(value)

    if node is None:

      raise Exception("Value not stored in tree")

    replacement = None

    rebalance_node = node.parent

    if node.left is not None:

      # There's a left child so we replace with rightmost node

      replacement = self.rightmost(node.left)

      # Check if reparenting is needed

      if replacement.is_left_child():

        replacement.parent.set_left(replacement.left)

      else:

        replacement.parent.set_right(replacement.left)

    elif node.right is not None:

      # There's a right child so we replace with the leftmost node

      replacement = self.leftmost(node.right)

      # Check if reparenting is needed

      if replacement.is_left_child():

        replacement.parent.set_left(replacement.right)

      else:

        replacement.parent.set_right(replacement.right)

    if replacement:

      # We found a replacement so replace the value

      node.value = replacement.value

      rebalance_node = replacement.parent

    else:

      # No replacement so it means the node to delete is a leaf

      self.delete_leaf(node)

    if rebalance_node is not None:

      self.restore_balance(rebalance_node)技术支持

范围查询

范围查询用于找出所有位于两个给定值之间的值。由于 AVL 树的有序性，我们可以高效地定位这些值。

为查找下界 lb 与上界 ub 之间的所有值，我们采用递归遍历。对每个遇到的节点，若其值落在区间内，则将其加入结果；随后继续探索其左右子树。

若节点值小于下界，则忽略其左子树，因为左子树中的所有值都更小。同理，若节点值大于上界，则忽略其右子树，因为右子树中的所有值都会更大。

  def search(self, node, lb, ub, results):

    # Search for values between lower bound and upper bound

    if node is None:

      return

    if lb <= node.value and node.value <= ub:

      results.append(node.value)

    if node.value >= lb:

      self.search(node.left, lb, ub, results)

    if node.value <= ub:

      self.search(node.right, lb, ub, results)

  def range_query(self, lb, ub):

    # Search for values between lower bound and upper bound

    results = []

    self.search(self.root, lb, ub, results)

    return results技术支持

其他自平衡树

我们已经实现了一棵 AVL 树，能够执行以下操作：

• 添加一个值
• 删除一个值
• 查找一个值
• 查询最小值与最大值
• 查询位于两个值之间的所有值

avltree 包提供了具备这些能力的 Python 实现。

其他自平衡二叉搜索树（如红黑树、伸展树与 B 树）也提供类似功能。总体而言，它们在大多数应用中的性能相近，因为都能保证对数级的高度。不过，AVL 树平衡更精细，优化了查找操作，但由于需要更严格的再平衡，插入可能稍慢。

伸展树在最近访问的元素会被频繁重用的场景中尤为有效，因此非常适合用作缓存的实现。

B 树专为磁盘而非内存中的高效操作而设计，适合管理超出内存容量的大型数据集，例如用于创建数据库索引。

进一步改进

我们的实现还有多种改进空间。以下是一些练习建议，以加深您对 AVL 树的理解：

• 当前实现中，节点只存储单个值。若用作数据库索引，需要存储整行数据，因为该值对应表的一列。我们可以改进实现，使 AVL 树像字典一样，将值映射到相应的数据行。
• 我们的实现不支持重复值，不过可以修改以允许多个节点共享同一值。
• 典型的 AVL 树多采用递归实现。我们刻意回避递归，以免依赖对递归概念的深入理解。虽然递归实现通常更优雅简洁，但需要对递归有扎实把握。

结语

BST 是一种遵循特定顺序组织数据的二叉树数据结构。这样的组织能够避免在查找特定值时检查整个数据集。然而，BST 可能失衡，导致性能退化，在某些情形下甚至需要检查整个数据集。

AVL 树通过旋转强制施加额外的平衡性质，从而解决这一问题。这些性质确保树的高度相对于数据集大小保持对数级，带来显著改进。

对数时间复杂度相较线性时间复杂度是巨大的提升，使 AVL 树在查询方面极其高效。即使面对数十亿条记录，AVL 树也只需检查极少的数据点即可定位元素，效率远胜一筹。