当前位置：首页 > news >正文

06_自平衡二叉搜索树

news 2025/5/24 19:54:29

菜鸟：老鸟，我最近在项目中遇到一个问题。我们需要频繁地插入、删除和查找数据，但我发现数据结构的操作速度变得很慢。你有什么建议吗？

老鸟：这个问题很常见。你目前用的是什么数据结构？

菜鸟：我用的是普通的二叉搜索树（BST）。

老鸟：普通的BST在最坏情况下会退化成链表，导致操作时间复杂度变成O(n)。你可以试试自平衡二叉搜索树（AVL树或红黑树），它们能保持树的高度在O(log n)，从而提高性能。

渐进式介绍概念

菜鸟：自平衡二叉搜索树？听起来很复杂，能详细说说吗？

老鸟：当然。自平衡二叉搜索树是一种特殊的二叉搜索树，它通过在插入和删除节点时进行旋转操作来保持树的平衡，以确保树的高度始终在O(log n)。今天我们以AVL树为例来讲解。

菜鸟：AVL树是怎么保持平衡的？

老鸟：AVL树在每个节点上保存一个平衡因子（左右子树的高度差），并在需要时进行旋转操作来保持平衡。

代码示例与分析

插入操作

老鸟：让我们从插入操作开始，先看一段代码：

class Node:def __init__(self, key):self.key = keyself.left = Noneself.right = Noneself.height = 1class 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.get_height(root.left), self.get_height(root.right))balance = self.get_balance(root)# Left Left Caseif balance > 1 and key < root.left.key:return self.right_rotate(root)# Right Right Caseif balance < -1 and key > root.right.key:return self.left_rotate(root)# Left Right Caseif balance > 1 and key > root.left.key:root.left = self.left_rotate(root.left)return self.right_rotate(root)# Right Left Caseif balance < -1 and key < root.right.key:root.right = self.right_rotate(root.right)return self.left_rotate(root)return rootdef left_rotate(self, z):y = z.rightT2 = y.lefty.left = zz.right = T2z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))return ydef right_rotate(self, z):y = z.leftT3 = y.righty.right = zz.left = T3z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))return ydef get_height(self, root):if not root:return 0return root.heightdef get_balance(self, root):if not root:return 0return self.get_height(root.left) - self.get_height(root.right)

菜鸟：看起来有点复杂，能解释一下吗？

老鸟：好的。首先，我们定义了一个节点类Node，它包含键值、高度和左右子节点。然后我们定义了AVLTree类，包含插入操作、左右旋转操作和获取高度及平衡因子的方法。

旋转操作

菜鸟：旋转操作是干什么用的？

老鸟：旋转操作用于调整树的结构以保持平衡。左旋转和右旋转是基本的旋转操作：

左旋转：用于处理右重的情况。
右旋转：用于处理左重的情况。

问题与优化

菜鸟：插入操作已经很清楚了，那删除操作呢？

老鸟：删除操作与插入操作类似，也需要调整平衡。具体代码如下：

def delete(self, root, key):if not root:return rootelif 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.rightroot = Nonereturn tempelif root.right is None:temp = root.leftroot = Nonereturn temptemp = self.get_min_value_node(root.right)root.key = temp.keyroot.right = self.delete(root.right, temp.key)if root is None:return rootroot.height = 1 + max(self.get_height(root.left), self.get_height(root.right))balance = self.get_balance(root)if balance > 1 and self.get_balance(root.left) >= 0:return self.right_rotate(root)if balance > 1 and self.get_balance(root.left) < 0:root.left = self.left_rotate(root.left)return self.right_rotate(root)if balance < -1 and self.get_balance(root.right) <= 0:return self.left_rotate(root)if balance < -1 and self.get_balance(root.right) > 0:root.right = self.right_rotate(root.right)return self.left_rotate(root)return rootdef get_min_value_node(self, root):if root is None or root.left is None:return rootreturn self.get_min_value_node(root.left)