python实现二叉搜索树(AVL树)简单样例

一、二叉搜索树

class TreeNode:def __init__(self, value):self.value = valueself.left = Noneself.right = Noneclass BinarySearchTree:def __init__(self):self.root = Nonedef insert(self, value):if self.root is None:self.root = TreeNode(value)else:self._insert(self.root, value)def _insert(self, node, value):if value < node.value:if node.left is None:node.left = TreeNode(value)else:self._insert(node.left, value)else:if node.right is None:node.right = TreeNode(value)else:self._insert(node.right, value)def search(self, value):return self._search(self.root, value)def _search(self, node, value):if node is None or node.value == value:return nodeif value < node.value:return self._search(node.left, value)return self._search(node.right, value)# 使用二叉搜索树
bst = BinarySearchTree()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(2)
bst.insert(4)# 搜索节点
found_node = bst.search(4)
if found_node:print(f'Node with value {found_node.value} found')
else:print('Node not found')

二、AVL树（平衡二叉搜索树）

AVL树是一种平衡二叉搜索树，它在插入和删除节点后会自动调整树的高度以保持平衡。以下是一个简单的AVL树实现：

class TreeNode:def __init__(self, key):self.key = keyself.left = Noneself.right = Noneself.height = 1class AVLTree:def insert(self, root, key):if not root:return TreeNode(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)# 左左情况if balance > 1 and key < root.left.key:return self.right_rotate(root)# 右右情况if balance < -1 and key > root.right.key:return self.left_rotate(root)# 左右情况if balance > 1 and key > root.left.key:root.left = self.left_rotate(root.left)return self.right_rotate(root)# 右左情况if 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)def pre_order(self, root):if not root:returnprint("{0} ".format(root.key), end="")self.pre_order(root.left)self.pre_order(root.right)# 使用AVL树
my_tree = AVLTree()
root = None
nums = [10, 20, 30, 40, 50, 25]for num in nums:root = my_tree.insert(root, num)print("Preorder traversal of the AVL tree is:")
my_tree.pre_order(root)