1 平衡二叉树之AVL树的特点与实现

在数据结构的学习中，平衡二叉树是一个非常重要的主题。我们上篇中介绍了二叉搜索树的基本概念及其实现，今天我们将深入探讨其中一种广泛应用的平衡二叉树：AVL树。

什么是AVL树？

AVL树是一种自平衡的二叉搜索树，由George Adelson-Velsky和Evgenii Landis于1962年提出。AVL树的关键特点是它的每一个节点都有一个平衡因子，定义为其左子树的高度减去右子树的高度。具体来说，对于每个节点，平衡因子可以用以下公式表示：

$$
\text{平衡因子} = \text{左子树高度} - \text{右子树高度}
$$

在AVL树中，平衡因子的值只能是-1、0或1。也就是说，全树的高度不会超过最坏情况下的平均高度，保持了$O(\log n)$的查找效率。

AVL树的特点

1. 搜索效率高：由于其平衡结构，AVL树的查找、插入和删除操作的时间复杂度均为$O(\log n)$。

2. 自平衡特性：每当插入或删除节点导致树的平衡被破坏时，AVL树会通过旋转操作自动恢复平衡。

3. 严格的平衡条件：AVL树比其他平衡树（如红黑树）更加严格，这使得它在动态数据集合中更适合频繁查询操作。

AVL树的实现

我们先来了解如何实现一个AVL树。下面是AVL树的节点结构和基本插入操作的代码示例。

AVL树节点结构

class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1  # 节点的高度初始为1

获取节点高度

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

计算平衡因子

def get_balance(node):
    if not node:
        return 0
    return get_height(node.left) - get_height(node.right)

旋转操作

为了保持AVL树的平衡，我们需要实现四种旋转操作：

1. 右旋转（Right Rotation）
2. 左旋转（Left Rotation）
3. 左右旋转（Left Right Rotation）
4. 右左旋转（Right Left Rotation）

以下是右旋转的实现：

def right_rotate(y):
    x = y.left
    T2 = x.right

    # 执行旋转
    x.right = y
    y.left = T2

    # 更新高度
    y.height = max(get_height(y.left), get_height(y.right)) + 1
    x.height = max(get_height(x.left), get_height(x.right)) + 1

    return x

左旋转和其他旋转可以类比实现。

插入操作

下面是插入操作的整体步骤：

def insert(node, key):
    # 1. 执行普通二叉搜索树的插入
    if not node:
        return TreeNode(key)
    elif key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)

    # 2. 更新节点高度
    node.height = 1 + max(get_height(node.left), get_height(node.right)))

    # 3. 获取平衡因子
    balance = get_balance(node)

    # 4. 检查树的平衡情况，并进行相应的旋转
    # 左左情况
    if balance > 1 and key < node.left.key:
        return right_rotate(node)

    # 右右情况
    if balance < -1 and key > node.right.key:
        return left_rotate(node)

    # 左右情况
    if balance > 1 and key > node.left.key:
        node.left = left_rotate(node.left)
        return right_rotate(node)

    # 右左情况
    if balance < -1 and key < node.right.key:
        node.right = right_rotate(node.right)
        return left_rotate(node)

    # 返回（未平衡的）节点指针
    return node

示例

假设我们需要插入一组数字：30, 20, 10, 25, 40, 50。通过上面的 insert 函数，我们可以看到，每次插入后都将自动调整树的结构，以保证它的平衡性。这保证了每次的查找操作在最坏情况下也仅需$O(\log n)$的时间。

总结

AVL树作为一种自平衡的二叉搜索树，不仅保持了良好的查询性能，而且通过旋转操作确保了树的高度始终保持在一个较低的水平。虽然在插入和删除时需要多次调整平衡状态，但这种代价在查询效率上是值得的。

在下一篇中，我们将讨论另一种广泛应用的平衡二叉树：红黑树的特点与应用。通过对比AVL树与红黑树，我们将能更好地理解在不同场景下选择合适的树结构的重要性。