撰写AVL树是一种自平衡二叉搜索树（Binary Search Tree, BST），它在每次插入或删除操作后会自动调整自身以保持高度平衡。这种平衡性确保了所有操作的时间复杂度保持在O(log n)。
AVL树的基本概念
-
平衡因子 (Balance Factor):
- 每个节点都有一个平衡因子，定义为该节点的左子树高度与右子树高度之差。
- 平衡因子 = 高度(左子树) – 高度(右子树)
- 平衡因子的值只能是-1, 0, 或1。
-
自平衡机制:
- 当插入或删除操作导致某个节点的平衡因子变为-2或2时，需要通过旋转（Rotation）操作来恢复平衡。
- 根据失衡的具体情况，AVL树有四种基本的旋转方式：
- 右旋 (Right Rotation)
- 左旋 (Left Rotation)
- 左右旋 (Left-Right Rotation)
- 右左旋 (Right-Left Rotation)
AVL树的操作
插入操作
-
插入节点:
- 按照BST的规则插入新节点。
- 从插入点开始，向上回溯并计算每个节点的平衡因子。
-
调整平衡:
- 如果某个节点的平衡因子变为-2或2，则需要进行旋转操作以恢复平衡。
- 具体旋转方式取决于失衡的具体情况：
- LL型 (Left-Left): 左子树的左子树高，进行右旋。
- RR型 (Right-Right): 右子树的右子树高，进行左旋。
- LR型 (Left-Right): 左子树的右子树高，先左旋再右旋。
- RL型 (Right-Left): 右子树的左子树高，先右旋再左旋。
删除操作
-
删除节点:
- 按照BST的规则删除节点。
- 从删除点开始，向上回溯并计算每个节点的平衡因子。
-
调整平衡:
- 如果某个节点的平衡因子变为-2或2，则需要进行旋转操作以恢复平衡。
- 具体旋转方式与插入操作类似，根据失衡的具体情况选择相应的旋转方式。
AVL树的实现
下面是一个简单的Python实现示例：
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 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 right_rotate(y):
x = y.left
T2 = x.right
# Perform rotation
x.right = y
y.left = T2
# Update heights
y.height = max(get_height(y.left), get_height(y.right)) + 1
x.height = max(get_height(x.left), get_height(x.right)) + 1
return x
def left_rotate(x):
y = x.right
T2 = y.left
# Perform rotation
y.left = x
x.right = T2
# Update heights
x.height = max(get_height(x.left), get_height(x.right)) + 1
y.height = max(get_height(y.left), get_height(y.right)) + 1
return y
def insert_node(root, key):
if not root:
return TreeNode(key)
if key < root.key:
root.left = insert_node(root.left, key)
else:
root.right = insert_node(root.right, key)
# Update the height of this ancestor node
root.height = 1 + max(get_height(root.left), get_height(root.right))
# Get the balance factor of this ancestor node to check whether
# this node became unbalanced
balance = get_balance_factor(root)
# If this node becomes unbalanced, then there are 4 cases
# Left Left Case
if balance > 1 and key < root.left.key:
return right_rotate(root)
# Right Right Case
if balance < -1 and key > root.right.key:
return left_rotate(root)
# Left Right Case
if balance > 1 and key > root.left.key:
root.left = left_rotate(root.left)
return right_rotate(root)
# Right Left Case
if balance < -1 and key < root.right.key:
root.right = right_rotate(root.right)
return left_rotate(root)
return root
def inorder_traversal(root):
if not root:
return []
result = []
result += inorder_traversal(root.left)
result.append(root.key)
result += inorder_traversal(root.right)
return result
# Example usage
if __name__ == "__main__":
root = None
keys = [10, 20, 30, 40, 50, 25]
for key in keys:
root = insert_node(root, key)
print("Inorder traversal of the AVL tree:")
print(inorder_traversal(root))总结
AVL树通过在每次插入或删除操作后调整节点的平衡因子，确保了树的高度始终保持对数级别。这种高度平衡性使得AVL树在查找、插入和删除操作中都能保持O(log n)的时间复杂度。