本文目录
- 07 AVL树（Adelson-Velsky and Landis Tree）
- S1 说明
- S2 示例
- S3 问题：简单的联系人管理系统
- Python3程序
- 代码说明
- S4 问题：用AVL树实现优先队列
- Python3程序
- 代码说明
- S5 问题：使用AVL树实现符号表
- Python3程序
- 代码说明
往期链接
| 01 数组 | 02 链表 | 03 栈 | 04 队列 | 05 二叉树 | 06 二叉搜索树 |
|---|
07 AVL树（Adelson-Velsky and Landis Tree）
S1 说明
AVL树（Adelson-Velsky and Landis Tree）是一种自平衡的二叉搜索树，它通过维护每个节点的平衡因子来确保树的高度尽可能低，从而保证查找、插入和删除操作的时间复杂度为 O(log n)。
特征
（1）平衡因子
AVL树中的每个节点都有一个平衡因子（Balance Factor），定义为该节点的左子树高度减去右子树高度。平衡因子可以为 -1、0 或 1：
- 0：表示左右子树高度相等。
- 1：表示左子树比右子树高 1。
- -1：表示右子树比左子树高 1。
如果某个节点的平衡因子的绝对值大于 1，则该节点不平衡，需要进行旋转操作来恢复平衡。
（2）旋转操作
为了保持树的平衡，AVL树使用四种基本的旋转操作：
- 右旋转（Right Rotation）：用于处理左左情况（LL）。
- 左旋转（Left Rotation）：用于处理右右情况（RR）。
- 左-右旋转（Left-Right Rotation）：用于处理左右情况（LR），先左旋再右旋。
- 右-左旋转（Right-Left Rotation）：用于处理右左情况（RL），先右旋再左旋。
（3）高度平衡
AVL树的高度在最坏情况下为 O(log n)，这意味着每次插入或删除操作后，树的高度不会超过 log(n)，从而保证有效的查找性能。
（4）查找性能
查找操作的时间复杂度为 O(log n)，与普通的二叉搜索树相比，AVL树由于其自平衡特性，可以提供更快的查找速度，尤其是在频繁插入和删除的情况下。
（5）插入和删除
在插入和删除节点时，AVL树会根据节点的平衡因子自动调整树的结构，可能需要多次旋转以保证整个树的平衡。
S2 示例
import matplotlib.pyplot as plt# macos系统显示中文
plt.rcParams['font.sans-serif'] = ['Arial Unicode MS']class Node:def __init__(self, key):self.key = key # 节点的键值self.left = None # 左子节点self.right = None # 右子节点self.height = 1 # 节点的高度class AVLTree:def __init__(self):self.root = None # 初始化根节点为 Nonedef height(self, node):if not node:return 0 # 如果节点为空，高度为 0return node.height # 返回节点的高度def balance(self, node):if not node:return 0 # 如果节点为空，平衡因子为 0return self.height(node.left) - self.height(node.right) # 计算平衡因子def update_height(self, node):if not node:return# 更新节点高度为左右子树高度的最大值加一node.height = 1 + max(self.height(node.left), self.height(node.right))def right_rotate(self, y):x = y.left # 获取当前节点的左子节点T2 = x.right # 获取左子节点的右子节点# 执行右旋操作x.right = y # 左子节点成为新的根节点y.left = T2 # 原根节点的左子节点指向 T2# 更新节点高度self.update_height(y)self.update_height(x)return x # 返回新的根节点def left_rotate(self, x):y = x.right # 获取当前节点的右子节点T2 = y.left # 获取右子节点的左子节点# 执行左旋操作y.left = x # 右子节点成为新的根节点x.right = T2 # 原根节点的右子节点指向 T2# 更新节点高度self.update_height(x)self.update_height(y)return y # 返回新的根节点def insert(self, root, key):if not root:return Node(key) # 如果当前节点为空，插入新节点# 根据键值插入节点if key < root.key:root.left = self.insert(root.left, key) # 插入左子树else:root.right = self.insert(root.right, key) # 插入右子树# 更新当前节点的高度self.update_height(root)# 计算当前节点的平衡因子balance = self.balance(root)# 左左情况（LL）if balance > 1 and key < root.left.key:return self.right_rotate(root)# 右右情况（RR）if balance < -1 and key > root.right.key:return self.left_rotate(root)# 左右情况（LR）if balance > 1 and key > root.left.key:root.left = self.left_rotate(root.left) # 先左旋return self.right_rotate(root) # 再右旋# 右左情况（RL）if balance < -1 and key < root.right.key:root.right = self.right_rotate(root.right) # 先右旋return self.left_rotate(root) # 再左旋return root # 返回当前节点def insert_key(self, key):self.root = self.insert(self.
