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”意味着必须比较除一个节点以外的所有节点。但在下面的 AVL 树中搜索“M”只需要访问 4 个节点。

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

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

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

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

AVL 树上搜索、插入和删除操作的时间复杂度为 \(O(h) = O( \log n)\) 的事实可以用以下方式解释，其中 \(h\) 是高度，\(n\) 是节点数量。

想象一棵完美的二叉树，其中所有节点都有两个子节点，除了最底层，就像下面的 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 .

提交答案 »

开始练习