Python递归实现AVL树数据结构
AVL树是一种自平衡二叉搜索树，它的平衡性能保证了插入、删除和查找等操作均具备较好的时间复杂度。在本文中，我们将使用Python实现AVL树数据结构，并提供详细的代码演示。
AVL树节点定义
首先，我们需要定义AVL树节点类。对于每个节点，我们需要保存它的值、左右子节点和平衡因子bf（即它的左子树高度与右子树高度之差）。
class AVLNode:
def init(self, val):
self.val = val
self.left = None
self.right = None
self.bf = 0
AVL树插入操作
AVL树插入操作分为两个部分：普通二叉搜索树插入操作和平衡调整。普通二叉搜索树插入操作与普通二叉搜索树相同。
def insert(root, val):
if root is None:
return AVLNode(val)
if val < root.val:
root.left = insert(root.left, val)
else:
root.right = insert(root.right, val)
root.bf = height(root.left) - height(root.right) # 计算平衡因子
root = balance(root) # 执行平衡调整
return root
注意，在每次插入操作后，我们需要计算该节点的平衡因子，以便后续进行平衡调整。
AVL树删除操作
AVL树的删除操作同样分为两个部分：普通二叉搜索树删除操作和平衡调整。普通二叉搜索树删除操作与普通二叉搜索树相同。
def delete(root, val):
if root is None:
return None
if val < root.val:
root.left = delete(root.left, val)
elif val > root.val:
root.right = delete(root.right, val)
else:
if root.left is None and root.right is None:
root = None
elif root.left is None or root.right is None:
root = root.left if root.left else root.right
else:
min_node = find_min(root.right)
root.val = min_node.val
root.right = delete(root.right, min_node.val)
if root:
root.bf = height(root.left) - height(root.right) # 计算平衡因子
root = balance(root) # 执行平衡调整
return root
同样需要注意，在每次删除操作后，我们需要计算该节点的平衡因子，以便后续进行平衡调整。
AVL树平衡调整
AVL树平衡调整是AVL树实现的核心。在每次插入、删除操作后，如果某个节点的平衡因子不为-1、0或1，即该节点不平衡，我们需要对该节点进行平衡调整。平衡调整一共有四种情况，分别是LL、RR、LR和RL。
左左（LL）旋转：当插入或删除一个节点后，某个节点的平衡因子为2，且其左子节点的平衡因子为1或0时执行。
def left_left_rotate(root):
left = root.left
root.left = left.right
left.right = root
root.bf = height(root.left) - height(root.right)
left.bf = height(left.left) - height(left.right)
return left
右右（RR）旋转：当插入或删除一个节点后，某个节点的平衡因子为-2，且其右子节点的平衡因子为-1或0时执行。
def right_right_rotate(root):
right = root.right
root.right = right.left
right.left = root
root.bf = height(root.left) - height(root.right)
right.bf = height(right.left) - height(right.right)
return right
左右（LR）旋转：当插入或删除一个节点后，某个节点的平衡因子为2，且其左子节点的平衡因子为-1时执行。该操作等价于先对root.left进行右右旋转，再对root进行左左旋转。
def left_right_rotate(root):
root.left = right_right_rotate(root.left)
return left_left_rotate(root)
右左（RL）旋转：当插入或删除一个节点后，某个节点的平衡因子为-2，且其右子节点的平衡因子为1时执行。该操作等价于先对root.right进行左左旋转，再对root进行右右旋转。
def right_left_rotate(root):
root.right = left_left_rotate(root.right)
return right_right_rotate(root)
AVL树整体平衡调整代码如下：
def balance(root):
if root.bf == -2:
if root.right.bf == -1:
root = right_right_rotate(root)
else:
root = right_left_rotate(root)
elif root.bf == 2:
if root.left.bf == 1:
root = left_left_rotate(root)
else:
root = left_right_rotate(root)
return root
AVL树高度计算代码
AVL树高度计算代码与普通二叉搜索树相同。
def height(root):
if root is None:
return -1
return max(height(root.left), height(root.right)) + 1
完整代码演示
下面是完整的AVL树数据结构实现代码，内附字符串的范例：
class AVLNode:
def init(self, val):
self.val = val
self.left = None
self.right = None
self.bf = 0
def insert(root, val):
if root is None:
return AVLNode(val)
if val < root.val:
root.left = insert(root.left, val)
else:
root.right = insert(root.right, val)
root.bf = height(root.left) - height(root.right)
root = balance(root)
return root
def delete(root, val):
if root is None:
return None
if val < root.val:
root.left = delete(root.left, val)
elif val > root.val:
root.right = delete(root.right, val)
else:
if root.left is None and root.right is None:
root = None
elif root.left is None or root.right is None:
root = root.left if root.left else root.right
else:
min_node = find_min(root.right)
root.val = min_node.val
root.right = delete(root.right, min_node.val)
if root:
root.bf = height(root.left) - height(root.right)
root = balance(root)
return root
def find_min(root):
while root.left is not None:
root = root.left
return root
def left_left_rotate(root):
left = root.left
root.left = left.right
left.right = root
root.bf = height(root.left) - height(root.right)
left.bf = height(left.left) - height(left.right)
return left
def left_right_rotate(root):
root.left = right_right_rotate(root.left)
return left_left_rotate(root)
def right_right_rotate(root):
right = root.right
root.right = right.left
right.left = root
root.bf = height(root.left) - height(root.right)
right.bf = height(right.left) - height(right.right)
return right
def right_left_rotate(root):
root.right = left_left_rotate(root.right)
return right_right_rotate(root)
def balance(root):
if root.bf == -2:
if root.right.bf == -1:
root = right_right_rotate(root)
else:
root = right_left_rotate(root)
elif root.bf == 2:
if root.left.bf == 1:
root = left_left_rotate(root)
else:
root = left_right_rotate(root)
return root
def height(root):
if root is None:
return -1
return max(height(root.left), height(root.right)) + 1
if name == 'main':
root = None
data_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'pidancode.com', '皮蛋编程']
for data in data_list:
root = insert(root, data)
print(height(root.left), height(root.right), root.bf, root.val)
print(height(root.left.left), height(root.left.right), root.left.bf, root.left.val, root.left.right.val)
print(height(root.right.left), height(root.right.right), root.right.bf, root.right.val, root.right.left.val)
root = delete(root, 'pidancode.com')
root = delete(root, '皮蛋编程')
print(height(root.left), height(root.right), root.bf, root.val)
print(height(root.left.left), height(root.left.right), root.left.bf, root.left.val, root.left.right.val)
print(height(root.right.left), height(root.right.right), root.right.bf, root.right.val, root.right.left.val)
这段代码将输入26个小写字母和两个字符串'pidancode.com'和'皮蛋编程'并插入到AVL树中。然后删除'pidancode.com'和'皮蛋编程'两个字符串，并输出AVL树当前的状态。我们可以通过打印输出语句了解AVL树的平衡性。
相关文章