AVL树详解（Python语言实现自平衡二叉搜索树完整教程）

核心概念：平衡因子与旋转

每个AVL树节点都有一个平衡因子（Balance Factor），定义为：左子树高度 - 右子树高度。平衡因子只能是 -1、0 或 1。如果插入/删除后某个节点的平衡因子变为 2 或 -2，就需要进行旋转。

旋转分为四种类型：

• 右旋（Right Rotation）：用于处理左-左（LL）失衡
• 左旋（Left Rotation）：用于处理右-右（RR）失衡
• 左右旋（Left-Right Rotation）：先左旋再右旋，处理左-右（LR）失衡
• 右左旋（Right-Left Rotation）：先右旋再左旋，处理右-左（RL）失衡

Python实现AVL树

下面我们用Python一步步构建AVL树。首先定义节点类，然后实现旋转、高度计算、平衡因子判断以及插入逻辑。

class AVLNode:    def __init__(self, key):        self.key = key        self.left = None        self.right = None        self.height = 1  # 新节点初始高度为1class AVLTree:    def get_height(self, node):        if not node:            return 0        return node.height    def get_balance(self, node):        if not node:            return 0        return self.get_height(node.left) - self.get_height(node.right)    def rotate_right(self, y):        x = y.left        T2 = x.right        # 执行旋转        x.right = y        y.left = T2        # 更新高度        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))        x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))        return x    def rotate_left(self, x):        y = x.right        T2 = y.left        # 执行旋转        y.left = x        x.right = T2        # 更新高度        x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))        return y    def insert(self, root, key):        # 第1步：执行标准BST插入        if not root:            return AVLNode(key)                if key < root.key:            root.left = self.insert(root.left, key)        elif key > root.key:            root.right = self.insert(root.right, key)        else:            # 不允许重复键            return root        # 第2步：更新当前节点的高度        root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))        # 第3步：获取平衡因子        balance = self.get_balance(root)        # 第4步：如果失衡，进行旋转        # 情况1：左-左（LL）        if balance > 1 and key < root.left.key:            return self.rotate_right(root)        # 情况2：右-右（RR）        if balance < -1 and key > root.right.key:            return self.rotate_left(root)        # 情况3：左-右（LR）        if balance > 1 and key > root.left.key:            root.left = self.rotate_left(root.left)            return self.rotate_right(root)        # 情况4：右-左（RL）        if balance < -1 and key < root.right.key:            root.right = self.rotate_right(root.right)            return self.rotate_left(root)        return root    def inorder(self, root):        if root:            self.inorder(root.left)            print(root.key, end=' ')            self.inorder(root.right)

使用示例

现在我们创建一个AVL树并插入一些数据：

tree = AVLTree()root = Nonekeys = [10, 20, 30, 40, 50, 25]for key in keys:    root = tree.insert(root, key)print("中序遍历结果（应为升序）:")tree.inorder(root)  # 输出: 10 20 25 30 40 50

为什么选择AVL树？

在需要频繁查找且数据动态变化的场景中，AVL树能保证最坏情况下的 O(log n) 性能。相比普通二叉搜索树（可能退化为链表），AVL树更适合对查询性能要求严格的系统，如数据库索引、内存缓存等。

总结

通过本教程，你已经掌握了Python AVL树实现的核心原理与代码编写。我们学习了平衡因子、四种旋转操作，并亲手构建了一个功能完整的AVL树。这是理解高级数据结构教程的重要一步。建议你动手运行代码，尝试插入不同序列，观察树的结构变化，加深理解。

记住：掌握AVL树不仅能提升你的算法能力，也是面试中的高频考点！