数据结构编程实践20讲(Python版)—07AVL树

往期链接

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.