二叉搜索树

二叉搜索树(Binary Search Tree, BST)是具有以下特性的二叉树： 左子树中的所有节点键值小于父节点的键值 右子树中的所有节点键值大于父节点的键值 左右子树本身也必须是二叉搜索树 这些特性使得二叉搜索树成为一种高效的数据结构，特别适合用于搜索、插入和删除操作。 二叉搜索树的操作复杂度 二叉搜索树各种操作的时间复杂度如下： 操作 平均情况 最坏情况 插入 O(log n) O(n) 查找 O(log n) O(n) 删除 O(log n) O(n) 最小值 O(log n) O(n) 最大值 O(log n) O(n) 前驱 O(log n) O(n) 后继 O(log n) O(n) 值得注意的是，平均情况指的是在平衡树上执行操作所需的时间，而最坏情况则是在非平衡树上执行操作所需的时间。当树不平衡时（例如所有节点都在一侧），BST的性能会大幅下降。 Python实现二叉搜索树 让我们用Python来实现一个二叉搜索树。首先，我们需要定义两个基本类：BinarySearchTree和Node。 基本结构 首先，我们定义一个空的BinarySearchTree类： class BinarySearchTree: def __init__(self): self.root = None self.size = 0 def length(self): return self.size def __len__(self): return self.size 接下来，我们定义一个Node类，并实现一些辅助方法： class Node: def __init__(self, key, val, left=None, right=None, parent=None): self.key = key self.payload = val self.leftChild = left self.rightChild = right self.parent = parent def has_left_child(self): return self.leftChild def has_right_child(self): return self.rightChild def is_left_child(self): return self.parent and self.parent.leftChild == self def is_right_child(self): return self.parent and self.parent.rightChild == self def is_root(self): return not self.parent def is_leaf(self): return not (self.rightChild or self.leftChild) def has_any_children(self): return self.rightChild or self.leftChild def has_both_children(self): return self.rightChild and self.leftChild 插入操作 有了基本结构后，我们可以实现插入操作。插入方法put()会检查树是否已有根节点。如果没有，它会创建一个新节点并将其设为根节点；如果已有根节点，则调用私有的递归辅助函数_put()来按照二叉搜索树的属性搜索树并插入新节点： ...