当前位置:首页 > Python > 正文

Python实现平衡二叉树(AVL树)完整教程 | 数据结构与算法

Python实现平衡二叉树(AVL树)教程

全面讲解平衡二叉树的原理、旋转操作及Python实现,包含完整代码和可视化演示

什么是平衡二叉树?

平衡二叉树(AVL树)是一种自平衡的二叉搜索树,由Adelson-Velskii和Landis在1962年发明。在AVL树中,任何节点的两个子树的高度最多相差1,这使得树能够保持平衡状态,确保查找、插入和删除操作的时间复杂度稳定在O(log n)。

为什么需要平衡二叉树?

普通二叉搜索树在极端情况下(如按顺序插入数据)会退化成链表,导致操作时间复杂度变为O(n)。AVL树通过旋转操作自动调整树的结构,始终保持平衡,解决了这个问题。

AVL树的核心概念

1. 平衡因子

平衡因子 = 左子树高度 - 右子树高度。在AVL树中,每个节点的平衡因子只能是-1、0或1。

2. 旋转操作

当插入或删除节点导致平衡因子超出允许范围时,AVL树通过旋转操作恢复平衡:

左旋

当右子树过高时使用

→

右旋

当左子树过高时使用

←

左右旋

先左旋再右旋

↷

右左旋

先右旋再左旋

↶

AVL树的Python实现

节点类定义

class AVLNode: def __init__(self, key): self.key = key self.left = None self.right = None self.height = 1

AVL树类实现

class AVLTree: def __init__(self): self.root = None def height(self, node): if not node: return 0 return node.height def balance_factor(self, node): if not node: return 0 return self.height(node.left) - self.height(node.right) def update_height(self, node): if node: node.height = 1 + max(self.height(node.left), self.height(node.right)) # 右旋操作 def right_rotate(self, z): y = z.left T3 = y.right y.right = z z.left = T3 self.update_height(z) self.update_height(y) return y # 左旋操作 def left_rotate(self, z): y = z.right T2 = y.left y.left = z z.right = T2 self.update_height(z) self.update_height(y) return y # 插入节点 def insert(self, root, key): # 1. 标准BST插入 if not root: return AVLNode(key) elif key < root.key: root.left = self.insert(root.left, key) else: root.right = self.insert(root.right, key) # 2. 更新高度 self.update_height(root) # 3. 获取平衡因子 balance = self.balance_factor(root) # 4. 平衡树(4种情况) # 左左情况 - 右旋 if balance > 1 and key < root.left.key: return self.right_rotate(root) # 右右情况 - 左旋 if balance < -1 and key > root.right.key: return self.left_rotate(root) # 左右情况 - 先左旋后右旋 if balance > 1 and key > root.left.key: root.left = self.left_rotate(root.left) return self.right_rotate(root) # 右左情况 - 先右旋后左旋 if balance < -1 and key < root.right.key: root.right = self.right_rotate(root.right) return self.left_rotate(root) return root # 中序遍历 def inorder(self, root): if root: self.inorder(root.left) print(root.key, end=" ") self.inorder(root.right)

重要提示:

在实现AVL树时,需要特别注意在每次插入或删除节点后更新节点高度并检查平衡因子。旋转操作后也要及时更新相关节点的高度。

使用示例

# 创建AVL树并插入数据 avl = AVLTree() root = None keys = [10, 20, 30, 40, 50, 25] for key in keys: root = avl.insert(root, key) # 中序遍历 print("中序遍历结果:") avl.inorder(root) # 输出: 10 20 25 30 40 50

AVL树与其他数据结构的比较

数据结构 插入/删除时间复杂度 查找时间复杂度 是否自平衡
普通二叉搜索树 O(n) (最坏情况) O(n) (最坏情况) 否
AVL树 O(log n) O(log n) 是
红黑树 O(log n) O(log n) 是
哈希表 O(1) O(1) 不适用

平衡二叉树的应用场景

1. 数据库索引

许多数据库系统使用AVL树或类似的自平衡树来实现索引结构,确保高效的数据检索。

2. 内存中的有序数据结构

当需要维护一个动态变化的有序数据集时,AVL树能提供高效的插入、删除和查找操作。

3. 文件系统

某些文件系统使用平衡树来管理目录结构,以支持快速的文件查找操作。

平衡二叉树可视化演示

当前树高度: 0 | 节点数量: 0

平衡二叉树教程 | Python数据结构与算法 | 本教程仅用于学习目的

发表评论