数据结构编程实践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 # 初始化根节点为 None
def height(self, node):
if not node:
return 0 # 如果节点为空,高度为 0
return node.height # 返回节点的高度
def balance(self, node):
if not node:
return 0 # 如果节点为空,平衡因子为 0
return 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.
原文地址:https://blog.csdn.net/qq_32882309/article/details/142765167
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!