引言
AVL树是一种自平衡二叉搜索树,由Adelson-Velsky和Landis于1962年提出。它通过在插入和删除节点时保持树的平衡,从而确保查找、插入和删除操作的时间复杂度均为O(log n)。本文将详细解析AVL树的构建技巧,并通过实例帮助你轻松入门。
AVL树的基本概念
1. 定义
AVL树是一种特殊的二叉搜索树,它的每个节点都有一个平衡因子(Balance Factor),即左子树的高度与右子树的高度的差值。AVL树要求所有节点的平衡因子都在-1、0或1之间。
2. 平衡因子
平衡因子的计算公式为:
平衡因子 = 左子树高度 - 右子树高度
3. 平衡操作
当插入或删除节点导致某个节点的平衡因子超过1或低于-1时,需要进行平衡操作。AVL树的平衡操作包括四种情况:左左(LL)、右右(RR)、左右(LR)和右左(RL)。
AVL树的构建技巧
1. 插入操作
插入操作分为以下步骤:
- 插入节点:按照二叉搜索树的规则插入节点。
- 更新高度:从插入节点开始,向上更新每个节点的height属性。
- 检查平衡因子:从插入节点开始,向上检查每个节点的平衡因子。
- 平衡操作:如果发现某个节点的平衡因子超过1或低于-1,则根据情况选择相应的平衡操作。
2. 删除操作
删除操作分为以下步骤:
- 删除节点:按照二叉搜索树的规则删除节点。
- 更新高度:从删除节点开始,向上更新每个节点的height属性。
- 检查平衡因子:从删除节点开始,向上检查每个节点的平衡因子。
- 平衡操作:如果发现某个节点的平衡因子超过1或低于-1,则根据情况选择相应的平衡操作。
实例解析
以下是一个AVL树的构建实例,包括插入和删除操作:
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
class AVLTree:
def insert(self, root, key):
if not root:
return Node(key)
elif key < root.key:
root.left = self.insert(root.left, key)
else:
root.right = self.insert(root.right, key)
root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
balanceFactor = self.getBalance(root)
if balanceFactor > 1 and key < root.left.key:
return self.rightRotate(root)
if balanceFactor < -1 and key > root.right.key:
return self.leftRotate(root)
if balanceFactor > 1 and key > root.left.key:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
if balanceFactor < -1 and key < root.right.key:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
def delete(self, root, key):
if not root:
return root
elif key < root.key:
root.left = self.delete(root.left, key)
elif key > root.key:
root.right = self.delete(root.right, key)
else:
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
temp = self.getMinValueNode(root.right)
root.key = temp.key
root.right = self.delete(root.right, temp.key)
if root is None:
return root
root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
balanceFactor = self.getBalance(root)
if balanceFactor > 1 and self.getBalance(root.left) >= 0:
return self.rightRotate(root)
if balanceFactor < -1 and self.getBalance(root.right) <= 0:
return self.leftRotate(root)
if balanceFactor > 1 and self.getBalance(root.left) < 0:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
if balanceFactor < -1 and self.getBalance(root.right) > 0:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
def leftRotate(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
return y
def rightRotate(self, y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
x.height = 1 + max(self.getHeight(x.left), self.getHeight(x.right))
return x
def getHeight(self, root):
if not root:
return 0
return root.height
def getBalance(self, root):
if not root:
return 0
return self.getHeight(root.left) - self.getHeight(root.right)
def getMinValueNode(self, root):
if root is None or root.left is None:
return root
return self.getMinValueNode(root.left)
def preOrder(self, root):
if not root:
return
print("{0} ".format(root.key), end="")
self.preOrder(root.left)
self.preOrder(root.right)
# 创建AVL树并插入节点
avl = AVLTree()
root = None
keys = [10, 20, 30, 40, 50, 25]
for key in keys:
root = avl.insert(root, key)
# 打印AVL树
print("Preorder traversal of the constructed AVL tree is")
avl.preOrder(root)
# 删除节点
root = avl.delete(root, 10)
# 打印AVL树
print("\nPreorder traversal after deletion of 10")
avl.preOrder(root)
总结
本文详细解析了AVL树的构建技巧,并通过实例展示了插入和删除操作。通过学习本文,读者可以轻松入门AVL树的构建。在实际应用中,AVL树因其高效的查找、插入和删除操作而被广泛应用于各种场景。
