手写AVL树（平衡二叉搜索树）的实现
AVL树是一种自平衡的二叉搜索树，在插入和删除操作后，能通过旋转操作自动调整树的结构，使树保持平衡，从而保证查找、插入、删除操作的时间复杂度均为O(log n)。它的核心特性是：任何节点的左右子树的高度差（平衡因子）的绝对值不超过1。
一、核心概念与定义
- 平衡因子：对于任意节点，其平衡因子 = 左子树高度 - 右子树高度。在AVL树中，平衡因子的值只能是-1、0、1。
- 旋转操作：当插入或删除节点导致树不平衡时（即某个节点的平衡因子变为2或-2），需要通过旋转来恢复平衡。旋转分为四种基本类型。
二、节点结构
我们先定义树节点，它除了存储键值、左右子节点指针外，还需要存储当前节点的高度（或平衡因子）。
class AVLNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1 # 节点初始高度为1
三、辅助函数
实现几个辅助函数，用于计算高度、更新高度、计算平衡因子。
def get_height(node):
if not node:
return 0
return node.height
def get_balance_factor(node):
if not node:
return 0
return get_height(node.left) - get_height(node.right)
def update_height(node):
if not node:
return
node.height = 1 + max(get_height(node.left), get_height(node.right))
四、旋转操作
旋转操作是AVL树实现平衡的核心。根据不平衡节点的平衡因子以及其较高子树（导致不平衡的那一侧子树）的平衡因子，分为四种情况。
1. 左旋（LL型）
当节点A的平衡因子为-2，且其右子节点B的平衡因子为-1或0时，进行左旋。
- 情况描述：在A的右子树的右侧插入了新节点，导致A不平衡。
- 操作：以A的右子节点B为支点，将A向左旋转下来，使B成为新的根节点。
def left_rotate(z):
y = z.right
T2 = y.left
# 执行旋转
y.left = z
z.right = T2
# 更新高度
update_height(z)
update_height(y)
return y
2. 右旋（RR型）
当节点A的平衡因子为2，且其左子节点B的平衡因子为1或0时，进行右旋。
- 情况描述：在A的左子树的左侧插入了新节点，导致A不平衡。
- 操作：以A的左子节点B为支点，将A向右旋转下来，使B成为新的根节点。
def right_rotate(z):
y = z.left
T3 = y.right
# 执行旋转
y.right = z
z.left = T3
# 更新高度
update_height(z)
update_height(y)
return y
3. 左右旋（LR型）
当节点A的平衡因子为2，且其左子节点B的平衡因子为-1时，先对B进行左旋，再对A进行右旋。
- 情况描述：在A的左子树的右侧插入了新节点。
- 操作：先左旋B，将情况转换为RR型，再右旋A。
def left_right_rotate(z):
z.left = left_rotate(z.left)
return right_rotate(z)
4. 右左旋（RL型）
当节点A的平衡因子为-2，且其右子节点B的平衡因子为1时，先对B进行右旋，再对A进行左旋。
- 情况描述：在A的右子树的左侧插入了新节点。
- 操作：先右旋B，将情况转换为LL型，再左旋A。
def right_left_rotate(z):
z.right = right_rotate(z.right)
return left_rotate(z)
五、插入操作
插入操作与BST插入类似，但插入后需要从插入点向上回溯，更新祖先节点的高度，并检查平衡因子，如果不平衡则进行相应的旋转。
def insert(root, key):
# 1. 执行标准的BST插入
if not root:
return AVLNode(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
else:
return root # 重复键不插入
# 2. 更新当前节点的高度
update_height(root)
# 3. 获取当前节点的平衡因子
balance = get_balance_factor(root)
# 4. 根据平衡因子进行旋转调整
# 左左情况
if balance > 1 and key < root.left.key:
return right_rotate(root)
# 右右情况
if balance < -1 and key > root.right.key:
return left_rotate(root)
# 左右情况
if balance > 1 and key > root.left.key:
return left_right_rotate(root)
# 右左情况
if balance < -1 and key < root.right.key:
return right_left_rotate(root)
return root
六、删除操作
删除操作也与BST删除类似，但删除后同样需要回溯调整平衡。删除有三种情况：
- 要删除的节点是叶子节点：直接删除。
- 要删除的节点只有一个子节点：用子节点替换它。
- 要删除的节点有两个子节点：找到其右子树中的最小节点（或左子树中的最大节点），用这个最小节点的键值替换要删除节点的键值，然后递归删除那个最小节点。
删除后，同样需要更新高度并检查平衡因子，进行必要的旋转。
def delete(root, key):
if not root:
return root
# 1. 执行标准的BST删除
if key < root.key:
root.left = delete(root.left, key)
elif key > root.key:
root.right = delete(root.right, key)
else:
# 节点有一个子节点或没有子节点
if not root.left:
return root.right
elif not root.right:
return root.left
# 节点有两个子节点：获取右子树的最小节点
temp = get_min_node(root.right)
root.key = temp.key
# 删除右子树的最小节点
root.right = delete(root.right, temp.key)
# 如果树只有一个节点，删除后返回
if not root:
return root
# 2. 更新当前节点的高度
update_height(root)
# 3. 获取当前节点的平衡因子
balance = get_balance_factor(root)
# 4. 根据平衡因子进行旋转调整
# 左左情况
if balance > 1 and get_balance_factor(root.left) >= 0:
return right_rotate(root)
# 左右情况
if balance > 1 and get_balance_factor(root.left) < 0:
return left_right_rotate(root)
# 右右情况
if balance < -1 and get_balance_factor(root.right) <= 0:
return left_rotate(root)
# 右左情况
if balance < -1 and get_balance_factor(root.right) > 0:
return right_left_rotate(root)
return root
def get_min_node(node):
current = node
while current.left:
current = current.left
return current
七、总结
AVL树通过严格维持每个节点的平衡因子在[-1,1]之间，保证了树的高度始终为O(log n)。其核心在于插入和删除后的回溯调整，通过四种旋转操作（LL、RR、LR、RL）来恢复平衡。虽然调整增加了常数时间开销，但换来了最坏情况下稳定的O(log n)操作时间复杂度，适用于需要频繁查找而插入删除相对较少的场景。理解并实现AVL树，是深入理解自平衡数据结构的重要一步。