Python中如何实现和解决AVL树的问题
比如 10 9 这俩数 插入一个 6
10
/
9
/
6
这种旋转完之后就是
9
/
6. 10
但如果是这种的话
10 9 6 插入一个 4
10
/
9
/
6
/
4
10 和 9 都可以认为这棵树不平衡，也就是说 10 和 9 的左右子树都不平衡（或者说是故障点，等于现在树里有 2 个故障点）
逻辑上该认为哪个是轴呢
代码该从哪个节点开始处理呢
我知道旋转之后的结果肯定是这
9
/
6. 10
/
4
但是逻辑上不太清楚（或者说先处理哪个故障点呢）
Python中如何实现和解决AVL树的问题
4 回复
AVL树是一种自平衡二叉搜索树，通过旋转操作维护平衡因子（左右子树高度差不超过1）。核心是四种旋转：左旋、右旋、左右旋、右左旋。下面是完整实现：
class AVLNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
class AVLTree:
def get_height(self, node):
return node.height if node else 0
def get_balance(self, node):
return self.get_height(node.left) - self.get_height(node.right) if node else 0
def right_rotate(self, y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))
return x
def left_rotate(self, x):
y = x.right
T2 = y.left
y.left = x
x.right = T2
x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
return y
def insert(self, root, key):
if not root:
return AVLNode(key)
if key < root.key:
root.left = self.insert(root.left, key)
else:
root.right = self.insert(root.right, key)
root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
balance = self.get_balance(root)
# 左左情况
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 delete(self, root, key):
if not root:
return root
if key < root.key:
root.left = self.delete(root.left, key)
elif key > root.key:
root.right = self.delete(root.right, key)
else:
if not root.left:
return root.right
elif not root.right:
return root.left
temp = self.get_min_node(root.right)
root.key = temp.key
root.right = self.delete(root.right, temp.key)
if not root:
return root
root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
balance = self.get_balance(root)
# 重新平衡
if balance > 1:
if self.get_balance(root.left) >= 0:
return self.right_rotate(root)
else:
root.left = self.left_rotate(root.left)
return self.right_rotate(root)
if balance < -1:
if self.get_balance(root.right) <= 0:
return self.left_rotate(root)
else:
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
return root
def get_min_node(self, root):
current = root
while current.left:
current = current.left
return current
def inorder(self, root):
if root:
self.inorder(root.left)
print(root.key, end=" ")
self.inorder(root.right)
# 使用示例
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
# 删除节点
root = avl.delete(root, 30)
print("\n删除30后:")
avl.inorder(root) # 输出: 10 20 25 40 50
关键点：
- 每个节点维护高度，平衡因子 = 左高 - 右高
- 插入/删除后从修改点向上回溯检查平衡
- 四种不平衡情况对应不同旋转组合
- 删除时用右子树最小节点替换被删节点
总结建议： 理解四种旋转情况并保证每次操作后更新高度。
