数据结构与算法 / 系统课时
二叉搜索树的有序性质
二叉搜索树的有序性质
二叉搜索树把节点值的大小关系编码到树结构中,使查找和插入能够持续排除一侧子树。本课通过一个完整示例实现插入、查找、中序遍历与合法性验证,并说明树高为何决定实际性能。
学习目标
- 理解二叉搜索树对整棵左右子树的有序约束
- 能实现无重复值搜索树的插入、查找和中序遍历
- 能分析平均情况、最坏情况与重复值策略
结构约束
对于不允许重复值的二叉搜索树,任意节点左子树中的所有值都小于该节点,右子树中的所有值都大于该节点。这个约束作用于整棵子树,而不只是直接子节点。
查找目标时,目标较小就进入左子树,较大就进入右子树;插入沿相同路径下降,直到遇到空位置。中序遍历会依次访问左子树、当前节点和右子树,因此结果严格递增。

主示例
下面的插入函数始终返回修改后的子树根,因此既能处理空树,也能让父节点正确接回新子树。示例同时使用上下界验证整棵树,避免只比较父子节点造成误判。
python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
elif value > root.value:
root.right = insert(root.right, value)
# 本示例拒绝重复值,因此相等时保持原树不变
return root
def contains(root, target):
current = root
while current is not None:
if target == current.value:
return True
current = current.left if target < current.value else current.right
return False
def inorder(root):
if root is None:
return []
return inorder(root.left) + [root.value] + inorder(root.right)
def is_valid_bst(root, lower=None, upper=None):
if root is None:
return True
if lower is not None and root.value <= lower:
return False
if upper is not None and root.value >= upper:
return False
return (
is_valid_bst(root.left, lower, root.value)
and is_valid_bst(root.right, root.value, upper)
)
root = None
for value in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
root = insert(root, value)
print("中序结果:", inorder(root))
print("查找 7:", contains(root, 7))
print("查找 9:", contains(root, 9))
print("结构合法:", is_valid_bst(root))预期输出:
text
中序结果: [1, 3, 4, 6, 7, 8, 10, 13, 14]
查找 7: True
查找 9: False
结构合法: True性能与边界
查找和插入的时间复杂度都是 ,其中 为树高。随机或较均匀的数据通常使树高接近 ;若按升序连续插入,树可能退化成链表,最坏复杂度变为 。中序遍历与合法性验证都需要访问全部节点,时间复杂度为 。
重复值没有唯一处理方式,可以拒绝、在节点中累计计数,或约定固定放到某一侧。无论选择哪种策略,插入、删除和验证规则都必须保持一致。
按自己的节奏,确认真正理解。