数据布局编程实践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 示例

1. import matplotlib.pyplot as plt
3. # macos系统显示中文
4. plt.rcParams['font.sans-serif'] = ['Arial Unicode MS']
6. class Node:
7.     def __init__(self, key):
8.         self.key = key  # 节点的键值
9.         self.left = None  # 左子节点
10.         self.right = None  # 右子节点
11.         self.height = 1  # 节点的高度
13. class AVLTree:
14.     def __init__(self):
15.         self.root = None  # 初始化根节点为 None
17.     def height(self, node):
18.         if not node:
19.             return 0  # 如果节点为空，高度为 0
20.         return node.height  # 返回节点的高度
22.     def balance(self, node):
23.         if not node:
24.             return 0  # 如果节点为空，平衡因子为 0
25.         return self.height(node.left) - self.height(node.right)  # 计算平衡因子
27.     def update_height(self, node):
28.         if not node:
29.             return
30.         # 更新节点高度为左右子树高度的最大值加一
31.         node.height = 1 + max(self.height(node.left), self.height(node.right))
33.     def right_rotate(self, y):
34.         x = y.left  # 获取当前节点的左子节点
35.         T2 = x.right  # 获取左子节点的右子节点
37.         # 执行右旋操作
38.         x.right = y  # 左子节点成为新的根节点
39.         y.left = T2  # 原根节点的左子节点指向 T2
41.         # 更新节点高度
42.         self.update_height(y)
43.         self.update_height(x)
45.         return x  # 返回新的根节点
47.     def left_rotate(self, x):
48.         y = x.right  # 获取当前节点的右子节点
49.         T2 = y.left  # 获取右子节点的左子节点
51.         # 执行左旋操作
52.         y.left = x  # 右子节点成为新的根节点
53.         x.right = T2  # 原根节点的右子节点指向 T2
55.         # 更新节点高度
56.         self.update_height(x)
57.         self.update_height(y)
59.         return y  # 返回新的根节点
61.     def insert(self, root, key):
62.         if not root:
63.             return Node(key)  # 如果当前节点为空，插入新节点
65.         # 根据键值插入节点
66.         if key < root.key:
67.             root.left = self.insert(root.left, key)  # 插入左子树
68.         else:
69.             root.right = self.insert(root.right, key)  # 插入右子树
71.         # 更新当前节点的高度
72.         self.update_height(root)
74.         # 计算当前节点的平衡因子
75.         balance = self.balance(root)
77.         # 左左情况（LL）
78.         if balance > 1 and key < root.left.key:
79.             return self.right_rotate(root)
81.         # 右右情况（RR）
82.         if balance < -1 and key > root.right.key:
83.             return self.left_rotate(root)
85.         # 左右情况（LR）
86.         if balance > 1 and key > root.left.key:
87.             root.left = self.left_rotate(root.left)  # 先左旋
88.             return self.right_rotate(root)  # 再右旋
90.         # 右左情况（RL）
91.         if balance < -1 and key < root.right.key:
92.             root.right = self.right_rotate(root.right)  # 先右旋
93.             return self.left_rotate(root)  # 再左旋
95.         return root  # 返回当前节点
97.     def insert_key(self, key):
98.         self.root = self.insert(self.root, key)  # 从根节点开始插入
100.     def inorder_traversal(self)</

复制代码