Python AVL 树

AVL 树是一种二叉搜索树，以两位苏联发明者 Georgy Adelson-Velsky 和 Evgenii Landis 的名字命名，他们在 1962 年发明了 AVL 树。

AVL 树是自平衡的，这意味着树的高度保持在最低限度，从而确保搜索、插入和删除节点的运行速度非常快，时间复杂度为 \(O( \log n)\)。

AVL 树

普通二叉搜索树和 AVL 树之间的唯一区别在于，AVL 树除了执行旋转操作外，还保持树的平衡。

当左子树和右子树的高度差小于 2 时，二叉搜索树是平衡的。

通过保持平衡，AVL 树确保树的高度最小，这意味着搜索、插入和删除操作可以非常快速地完成。

上面的两棵树都是二叉搜索树，它们具有相同的节点和相同的中序遍历（按字母顺序），但由于 AVL 树已经自我平衡，因此高度非常不同。

通过下面的动画逐步构建 AVL 树，了解平衡因子是如何更新的，以及在需要恢复平衡时如何进行旋转操作。

请继续阅读，了解更多关于如何计算平衡因子、如何进行旋转操作以及如何实现 AVL 树的信息。

向左和向右旋转

为了恢复 AVL 树的平衡，需要进行向左或向右旋转，或者向左和向右旋转的组合。

先前的动画展示了一个特定的左旋转和一个特定的右旋转。

但一般来说，向左和向右旋转就像在下面的动画中一样。

请注意子树如何改变其父节点。旋转期间，子树以这种方式改变父节点，以保持正确的中序遍历，并保持二叉搜索树的属性，即对于树中的所有节点，左子节点小于右子节点。

另外，请记住，需要进行旋转的不一定是根节点。

平衡因子

节点的平衡因子是子树高度之差。

AVL 树中所有节点的子树高度都存储在每个节点中，并根据其子树高度计算平衡因子，以检查树是否失去平衡。

子树的高度是子树的根节点与该子树中最远的叶节点之间的边数。

让我们仔细看看 AVL 树可以进行的各种旋转操作，以恢复平衡。

四种“不平衡”情况

当只有一个节点的平衡因子小于 -1 或大于 1 时，认为树不平衡，需要进行旋转以恢复平衡。

AVL 树有四种不同的不平衡方式，每种情况都需要不同的旋转操作。

请参阅以下对这些情况的动画和解释。

左-左（LL）情况

发现不平衡的节点向左倾斜，并且该节点的左子节点也向左倾斜。

当出现这种 LL 情况时，对不平衡节点进行向右单旋转就足以恢复平衡。

逐步浏览下面的动画，了解 LL 情况，以及如何通过向右单旋转恢复平衡。

逐步浏览上面的动画时，会出现两个 LL 情况：

• 添加 D 时，Q 的平衡因子变为 -2，这意味着树不平衡。这是一个 LL 情况，因为不平衡节点 Q 及其左子节点 P 都向左倾斜（负平衡因子）。在节点 Q 处进行向右单旋转可恢复树的平衡。
• 添加节点 L、C 和 B 后，P 的平衡因子为 -2，这意味着树不平衡。这也是一个 LL 情况，因为不平衡节点 P 及其左子节点 D 都向左倾斜。向右单旋转可恢复平衡。

右-右（RR）情况

当节点不平衡且向右倾斜，并且右子节点也向右倾斜时，就会出现右-右情况。

在 RR 情况下，对不平衡节点进行向左单旋转就足以恢复平衡。

上面的动画中出现了两次 RR 情况：

1. 插入节点 D 时，A 变得不平衡，A 和 B 都向右倾斜。在节点 A 处进行左旋转可恢复树的平衡。
2. 插入节点 E、C 和 F 后，节点 B 变得不平衡。这是一个 RR 情况，因为节点 B 及其右子节点 D 都向右倾斜。左旋转可恢复树的平衡。

左-右（LR）情况

左-右情况是指不平衡节点向左倾斜，但其左子节点向右倾斜。

在这种 LR 情况下，首先对左子节点进行左旋转，然后对原始不平衡节点进行右旋转。

逐步浏览下面的动画，了解左-右情况是如何发生的，以及如何进行旋转操作以恢复平衡。

在上面的动画中构建 AVL 树时，左-右情况会发生两次，需要进行旋转操作以恢复平衡：

1. 插入 K 时，节点 Q 变得不平衡，平衡因子为 -2，因此它向左倾斜，其左子节点 E 向右倾斜，因此这是一个左-右情况。
2. 插入节点 C、F 和 G 后，节点 K 变得不平衡并向左倾斜，其左子节点 E 向右倾斜，因此这是一个左-右情况。

右-左（RL）情况

右-左情况是指不平衡节点向右倾斜，其右子节点向左倾斜。

在这种情况下，我们首先对不平衡节点的右子节点进行右旋转，然后对不平衡节点本身进行左旋转。

逐步浏览下面的动画，了解右-左情况是如何发生的，以及如何进行旋转以恢复平衡。

插入节点 B 后，我们得到一个右-左情况，因为节点 A 变得不平衡并向右倾斜，其右子节点向左倾斜。为了恢复平衡，首先对节点 F 进行右旋转，然后对节点 A 进行左旋转。

下一个右-左情况发生在添加节点 G、E 和 D 之后。这是一个右-左情况，因为 B 不平衡并向右倾斜，其右子节点 F 向左倾斜。为了恢复平衡，首先对节点 F 进行右旋转，然后对节点 B 进行左旋转。

AVL 树中的回溯

在 AVL 树中插入或删除节点后，树可能变得不平衡。为了确定树是否不平衡，我们需要更新所有祖先节点的高度并重新计算平衡因子。

这一过程称为回溯，通过递归实现。在插入或删除操作后，递归调用会回溯到根节点，在此过程中更新每个祖先节点的高度并重新计算平衡因子。如果发现任何祖先节点的平衡因子超出 -1 到 1 的范围，则在该节点进行旋转以恢复树的平衡。

在下面的模拟中，插入节点 F 后，节点 C、E 和 H 都不平衡，但由于回溯是通过递归进行的，因此首先发现并修复节点 H 的不平衡，在这种情况下，这也修复了节点 E 和 C 的不平衡。

插入节点 F 后，代码将回溯，在向根节点传播的过程中计算平衡因子。当到达节点 H 并计算出平衡因子为 -2 时，进行右旋转。只有在完成此旋转后，代码才会继续回溯，进一步计算祖先节点 E 和 C 的平衡因子。

由于进行了旋转，节点 E 和 C 的平衡因子与插入节点 F 之前相同。

Python 中的 AVL 树实现

这段代码基于上一页的二叉搜索树实现，用于插入节点。

与二叉搜索树相比，AVL 树中的每个节点只有一个新属性，即高度，但由于 AVL 树的自我平衡方式，AVL 树的实现需要许多新函数和额外的代码行。

下面的实现基于字符列表构建 AVL 树，以创建上面模拟中的 AVL 树。最后插入的节点“F”也会触发右旋转，就像上面的模拟一样。

实例

在 Python 中实现 AVL 树：

class TreeNode:
  def __init__(self, data):
    self.data = data
    self.left = None
    self.right = None
    self.height = 1

def getHeight(node):
  if not node:
    return 0
  return node.height

def getBalance(node):
  if not node:
    return 0
  return getHeight(node.left) - getHeight(node.right)

def rightRotate(y):
  print('Rotate right on node',y.data)
  x = y.left
  T2 = x.right
  x.right = y
  y.left = T2
  y.height = 1 + max(getHeight(y.left), getHeight(y.right))
  x.height = 1 + max(getHeight(x.left), getHeight(x.right))
  return x

def leftRotate(x):
  print('Rotate left on node',x.data)
  y = x.right
  T2 = y.left
  y.left = x
  x.right = T2
  x.height = 1 + max(getHeight(x.left), getHeight(x.right))
  y.height = 1 + max(getHeight(y.left), getHeight(y.right))
  return y

def insert(node, data):
  if not node:
    return TreeNode(data)

  if data < node.data:
    node.left = insert(node.left, data)
  elif data > node.data:
    node.right = insert(node.right, data)

  # Update the balance factor and balance the tree
  node.height = 1 + max(getHeight(node.left), getHeight(node.right))
  balance = getBalance(node)

  # Balancing the tree
  # Left Left
  if balance > 1 and getBalance(node.left) >= 0:
    return rightRotate(node)

  # Left Right
  if balance > 1 and getBalance(node.left) < 0:
    node.left = leftRotate(node.left)
    return rightRotate(node)

  # Right Right
  if balance < -1 and getBalance(node.right) <= 0:
    return leftRotate(node)

  # Right Left
  if balance < -1 and getBalance(node.right) > 0:
    node.right = rightRotate(node.right)
    return leftRotate(node)

  return node

def inOrderTraversal(node):
  if node is None:
    return
  inOrderTraversal(node.left)
  print(node.data, end=", ")
  inOrderTraversal(node.right)

# Inserting nodes
root = None
letters = ['C', 'B', 'E', 'A', 'D', 'H', 'G', 'F']
for letter in letters:
  root = insert(root, letter)

inOrderTraversal(root)

亲自试一试

AVL 树删除节点的实现

当删除的节点不是叶节点时，AVL 树需要 minValueNode() 函数在中序遍历中找到节点的下一个节点。这与上一页中解释的在二叉搜索树中删除节点的情况相同。

要在 AVL 树中删除节点，需要与插入节点的代码相同的代码来恢复平衡。

实例

删除节点：

def minValueNode(node):
  current = node
  while current.left is not None:
    current = current.left
  return current

def delete(node, data):
  if not node:
    return node

  if data < node.data:
    node.left = delete(node.left, data)
  elif data > node.data:
    node.right = delete(node.right, data)
  else:
    if node.left is None:
      temp = node.right
      node = None
      return temp
    elif node.right is None:
      temp = node.left
      node = None
      return temp

    temp = minValueNode(node.right)
    node.data = temp.data
    node.right = delete(node.right, temp.data)

  return node

def inOrderTraversal(node):
  if node is None:
    return
  inOrderTraversal(node.left)
  print(node.data, end=", ")
  inOrderTraversal(node.right)

# Inserting nodes
root = None
letters = ['C', 'B', 'E', 'A', 'D', 'H', 'G', 'F']
for letter in letters:
  root = insert(root, letter)

inOrderTraversal(root)

亲自试一试

AVL 树的时间复杂度

看看下面不平衡的二叉搜索树。搜索“M”意味着必须比较除 1 以外的所有节点。但在下面的 AVL 树中搜索“M”只需要访问 4 个节点。

因此，在最坏的情况下，搜索、插入和删除等算法必须遍历树的整体高度。这意味着，像我们使用 AVL 树一样保持树的高度（h）较低，可以缩短运行时间。

请参阅下面二叉搜索树和 AVL 树的时间复杂度比较，以及时间复杂度与树的高度 (\(h\)) 和树中节点数 (\(n\)) 的关系。

• 二叉搜索树（BST）不是自平衡的。这意味着二叉搜索树可能非常不平衡，几乎像一条长链，高度几乎与节点数相同。这使得搜索、删除和插入节点等操作变慢，时间复杂度为 \(O(h) = O(n)\)。
• 然而，AVL 树是自平衡的。这意味着树的高度保持在最低限度，因此搜索、删除和插入节点等操作要快得多，时间复杂度为 \(O(h) = O( \log n)\)。

\(O( \log n)\) 解释

对于高度为 \(h\) 、节点数为 \(n\) 的 AVL 树，搜索、插入和删除的时间复杂度为 \(O(h) = O( \log n)\)，原因如下：

想象一个完美的二叉树，其中除最低层外，所有节点都有两个子节点，就像下面的 AVL 树一样。

在这种 AVL 树中，每一层的节点数为：

\[1, 2, 4, 8, 16, 32, ..\]

这与以下相同：

\[2^0, 2^1, 2^2, 2^3, 2^4, 2^5, ..\]

要得到高度为 \(h=3\) 的完美二叉树中的节点数 \(n\)，我们可以将每一层的节点数相加：

\[n_3=2^0 + 2^1 + 2^2 + 2^3 = 15\]

这实际上与以下相同：

\[n_3=2^4 - 1 = 15\]

对于更大的树也是如此！例如，如果我们想得到高度为 \(h=5 \) 的树中的节点数 \(n \)，我们可以这样找到节点数：

\[n_5=2^6 - 1 = 63\]

因此，一般来说，完美二叉树的高度 \(h \) 与其中节点数 \(n \) 之间的关系可以表示为：

\[n_h = 2^{h+1} - 1\]

我们知道在 AVL 树中搜索、删除或插入节点的时间复杂度为 \(O(h) \)，但我们想证明时间复杂度实际上是 \(O(\log(n)) \)，因此我们需要找到由节点数 \(n\) 描述的高度 \(h\)：

\[ \begin{equation} \begin{aligned} n & = 2^{h+1}-1 \\ n+1 & = 2^{h+1} \\ \log_2(n+1) & = \log_2(2^{h+1}) \\ h & = \log_2(n+1) - 1 \\ \\ O(h) & = O(\log{n}) \end{aligned} \end{equation} \]

上面的最后一行是如何得出的可能并不明显，但对于具有大量节点（大 \(n\)）的二叉树，当我们考虑时间复杂度时，"+1" 和 "-1" 项并不重要。有关如何使用大 O 符号计算时间复杂度的更多详细信息，请参阅此页。

上面的数学计算表明，AVL 树上的搜索、删除和插入操作的时间复杂度 \(O(h) \) 实际上可以表示为 \(O(\log{n}) \)，这种速度非常快，比二叉搜索树的时间复杂度 \(O(n) \) 快得多。