DSA AVL 树

AVL 树

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

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

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

上面的两棵树都是二叉搜索树，它们拥有相同的节点和相同的有序遍历（按字母顺序），但高度却大不相同，因为 AVL 树已经进行了自平衡。

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

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

左旋和右旋

为了恢复 AVL 树中的平衡，需要执行左旋或右旋，或者左右旋的组合。

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

但总的来说，左旋和右旋的操作就像下面的动画所示。

请注意子树是如何改变其父节点的。在旋转过程中，子树通过这种方式改变父节点，以保持正确的有序遍历，并维持 BST 的属性，即树中所有节点，左子节点都小于右子节点。

同时也要记住，并非总是根节点会失去平衡并需要旋转。

平衡因子

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

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

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

让我们仔细看看 AVL 树可以执行的四种不同类型的旋转操作，以重新获得平衡。

四种“失衡”情况

当仅一个节点的平衡因子小于 -1 或大于 1 时，该树被视为失衡，需要进行旋转以恢复平衡。

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

请参阅下面的动画和解释。

左-左 (LL) 情况

发现失衡的节点呈左重，并且该节点的左子节点也呈左重。

当发生 LL 情况时，对失衡节点进行单次右旋就足以恢复平衡。

逐步执行下面的动画，以查看 LL 情况，以及如何通过单次右旋恢复平衡。

当你逐步执行上面的动画时，发生了两次 LL 情况。

1. 当插入 D 时，Q 的平衡因子变为 -2，这意味着树失衡。这是 LL 情况，因为失衡节点 Q 及其左子节点 P 都呈左重（负平衡因子）。在节点 Q 处进行单次右旋可以恢复树的平衡。
2. 在插入 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 树时，左-右情况发生了 2 次，并且需要执行旋转操作来恢复平衡。

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 之前的情况保持不变。

AVL 插入节点实现

此代码基于前一页关于插入节点的 BST 实现。

与 BST 相比，AVL 树的每个节点只有一个新属性，那就是高度，但由于 AVL 树的自平衡机制，AVL 树实现需要许多新函数和额外的代码行。

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

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)

    if node is None:
        return node

    # 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

AVL 树的时间复杂度

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

因此，在最坏情况下，像搜索、插入和删除这样的算法必须遍历整个树的高度。这意味着使用 AVL 树保持树的低高度（\(h\)) 可以带来更低的运行时。

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

• BST 不会自动平衡。这意味着 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})\)，这很快，比 BST 的时间复杂度 \(O(n)\) 快得多。

DSA 练习

通过练习来测试自己

练习

下面的 AVL 树中，每个节点都与其平衡因子一起显示。

什么是平衡因子？

The balance factor is the 
difference between each node's 
left and right subtree .

提交答案 »

开始练习