数据结构与算法 / 系统课时

二叉搜索树的有序性质

二叉搜索树的有序性质

二叉搜索树把节点值的大小关系编码到树结构中,使查找和插入能够持续排除一侧子树。本课通过一个完整示例实现插入、查找、中序遍历与合法性验证,并说明树高为何决定实际性能。

学习目标

  • 理解二叉搜索树对整棵左右子树的有序约束
  • 能实现无重复值搜索树的插入、查找和中序遍历
  • 能分析平均情况、最坏情况与重复值策略

结构约束

对于不允许重复值的二叉搜索树,任意节点左子树中的所有值都小于该节点,右子树中的所有值都大于该节点。这个约束作用于整棵子树,而不只是直接子节点。

查找目标时,目标较小就进入左子树,较大就进入右子树;插入沿相同路径下降,直到遇到空位置。中序遍历会依次访问左子树、当前节点和右子树,因此结果严格递增。

二叉搜索树有序结构与查找路径

主示例

下面的插入函数始终返回修改后的子树根,因此既能处理空树,也能让父节点正确接回新子树。示例同时使用上下界验证整棵树,避免只比较父子节点造成误判。

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

性能与边界

查找和插入的时间复杂度都是 O(h)O(h),其中 hh 为树高。随机或较均匀的数据通常使树高接近 log⁡n\log n;若按升序连续插入,树可能退化成链表,最坏复杂度变为 O(n)O(n)。中序遍历与合法性验证都需要访问全部节点,时间复杂度为 O(n)O(n)。

重复值没有唯一处理方式,可以拒绝、在节点中累计计数,或约定固定放到某一侧。无论选择哪种策略,插入、删除和验证规则都必须保持一致。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

二叉搜索树的有序性质

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通