2.6 树与有序结构

学习目标

学完这一节，你能：

• 解释树结构适合表达层级和有序关系
• 说清二叉搜索树的基本不变量
• 理解树的高度为什么决定查找复杂度
• 区分哈希查询和有序查询
• 在 Python 中使用 bisect 理解有序数组的查找和插入成本
• 审查 agent 是否为了"高级"而过度实现树

---

有些数据不只是集合

哈希表很适合回答：

这个 key 是否存在？

但有些问题需要顺序：

• 找所有分数在 80 到 90 之间的学生
• 找不超过预算的最高价格
• 找某个时间点之后的第一场会议
• 按字典序列出所有前缀匹配的词

这些问题不只是"有没有"，而是"大小关系如何"。

这时，数据结构需要维护某种有序性。

---

树的直觉

树由节点和边组成，有一个根节点，每个节点可以有若干子节点。

生活中常见的树结构：

• 文件夹和子文件夹
• 公司组织架构
• 课程章节目录
• 评论区的回复层级

本节重点看一种特殊树：二叉搜索树。它的每个节点最多有两个子节点，并满足一个不变量：

左子树里的所有值 < 当前节点的值 < 右子树里的所有值

例如：

        8
      /   \
     3     10
    / \      \
   1   6      14

如果要查找 6：

1. 和 8 比，6 更小，去左边。
2. 和 3 比，6 更大，去右边。
3. 找到 6。

每次比较都能排除一边。

---

中序遍历：树中的顺序

二叉搜索树还有一个重要性质：按"左子树、当前节点、右子树"的顺序遍历，会得到递增序列。

def inorder(node):
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)

这段写法为了讲清概念，使用了列表拼接；实际大树上更适合用生成器或传入结果列表，避免反复复制。

中序遍历说明了二叉搜索树为什么不只是"能查找"，还和有序输出、范围查询有关。

---

高度决定成本

二叉搜索树查找成本取决于树的高度 h。

查找、插入、删除：O(h)

如果树比较平衡，高度大约是 log n，操作就快。
如果树退化成一条链，高度就是 n，操作就和链表差不多。

退化例子：

1
 \
  2
   \
    3
     \
      4

这就是为什么真实系统通常需要平衡树。平衡树会在插入和删除时调整结构，让高度保持在对数级别。

本章不展开具体平衡树的调整规则。现在要掌握的是判断力：

如果你依赖树来获得 O(log n) 操作，就必须确认它是否会保持平衡。

---

Python 中先用 bisect 理解有序结构

Python 标准库没有直接提供通用平衡搜索树。但可以用 bisect 在有序列表中查找插入位置：

import bisect

scores = [60, 75, 82, 90, 97]

pos = bisect.bisect_left(scores, 82)
print(pos)  # 2

查找插入位置是二分过程，复杂度是 Θ(log n)。

但真正插入时，列表要移动元素：

bisect.insort(scores, 88)

插入位置查找是 Θ(log n)，移动元素是 Θ(n)，所以整体仍然是 Θ(n)。

这很重要：有序列表的查找位置快，不代表插入整体快。

---

范围查询的结构信号

如果需求里出现下面这些表达，通常说明只用哈希表不够：

大于某个值的最小元素
小于某个值的最大元素
区间 [low, high] 内的所有元素
按顺序取前 100 个
找某个时间之后的第一条记录

这些需求都依赖顺序关系。

如果数据很小，直接排序或扫描可能足够。
如果数据很大、查询频繁，就要考虑维护有序结构或数据库索引。

本节不要求你手写复杂平衡树，但要求你识别：

精确查询 -> 哈希表通常自然
范围查询 -> 需要有序结构或索引

---

哈希表和有序结构的选择

需求	更自然的结构
判断 id 是否存在	set
按 id 找对象	dict
按分数范围查询	有序结构
找大于某值的最小元素	有序结构
只需要去重，不需要顺序	set
需要按插入顺序展示	list + set 组合

如果任务只需要精确 key 查找，哈希表通常更简单。
如果任务需要范围、前驱、后继、排序遍历，就要考虑有序结构。

---

审查 agent 输出

假设 agent 说：

为了查询用户信息，我会实现一个二叉搜索树，因为树的查询是 O(log n)。

这句话有三个需要审查的地方：

1. 查询是按用户 id 精确查询，还是按范围查询？
2. 如果只是按 id 查，dict 是否更简单？
3. 它实现的是普通二叉搜索树，还是能保持平衡的树？

如果 agent 手写了一个普通 BST，却声称最坏查询是 O(log n)，这是错误的。普通 BST 最坏可以退化到 O(n)。

更好的提示词是：

请比较 dict、有序列表 + bisect、平衡树三种方案。
需求是：
1. 按用户 id 查询：每天 100 万次
2. 按注册时间范围查询：每天 1000 次
3. 插入新用户：每天 1 万次

请说明每种方案的时间复杂度、空间代价、实现复杂度，以及是否建议手写。

这样 agent 必须围绕操作需求做取舍，而不是只抛出结构名。

---

方案比较表

同一个"查找"任务，可能有多种结构。专业判断要把操作放在一起比较。

结构	精确查询	插入删除	范围查询	顺序遍历	适合场景
dict / set	期望 Θ(1)	期望 Θ(1)	不擅长	不按大小顺序	精确 key 查询
有序列表 + bisect	Θ(log n) 查位置	Θ(n)	可用	很方便	更新少、查询多
平衡的搜索树	O(log n)	O(log n)	擅长	擅长	大规模动态有序数据
普通 BST	平衡时快	取决于高度	可用	可用	教学和小规模，不保证最坏

Python 标准库没有直接给出通用平衡搜索树。工程中遇到大规模动态有序查询，常见选择是数据库索引、专门的库，或重新审视是否真的需要在线维护顺序。

---

用本节知识解决：按时间段导出问题

课堂系统课后要导出问题记录。最简单的导出是全部导出，这用 list 顺序遍历就够了。

但如果老师提出新需求：

导出 10:00 到 10:15 之间提交的问题。

这就变成范围查询。

如果问题数量很少，直接扫描全部记录很简单：

def export_between(questions, start_time, end_time):
    result = []
    for q in questions:
        if start_time <= q["time"] <= end_time:
            result.append(q)
    return result

这段代码是 Θ(n)。如果一节课只有几百条问题，完全可以接受。

如果平台同时服务很多课堂，每天有几百万条记录，并且范围导出很频繁，就不能每次全表扫描。你需要让数据按时间保持有序，或者交给数据库索引。

用当前知识，可以先理解一个简化版：如果 times 是已经排好序的提交时间列表，可以用 bisect 找到区间边界。

import bisect

def find_time_range(times, start_time, end_time):
    left = bisect.bisect_left(times, start_time)
    right = bisect.bisect_right(times, end_time)
    return left, right

找边界是 Θ(log n)，取出区间内的 k 条记录还要 Θ(k)。如果还要频繁插入新记录到中间，有序列表会移动元素，成本又回到 Θ(n)。

这就是现实决策：

小规模：直接扫描，简单可靠。
记录追加且基本按时间顺序：列表保存，导出时可利用顺序。
大规模频繁范围查询：需要有序索引或数据库支持。

Agent 如果一上来手写复杂树，可能过度设计；如果永远只写线性扫描，也可能无法支撑真实规模。

---

本节要点

• 树适合表达层级结构，也可以维护有序关系。
• 二叉搜索树的不变量是左小右大。
• BST 操作复杂度是 O(h)，h 是树高。
• 平衡时高度约 log n，退化时高度可能是 n。
• Python 的 bisect 能在有序列表中快速找位置，但插入仍可能移动 Θ(n) 个元素。
• 审查 agent 时，要问它是否真的需要有序结构，以及它的树是否保持平衡。

---

课堂练习

你要实现一个图书查询功能：

1. 按 ISBN 精确查一本书。
2. 按价格区间查书。
3. 按出版年份从小到大浏览。

请回答：

1. 这三个需求是否适合同一个 dict 完成？
2. 哪些需求需要有序结构？
3. 如果 agent 推荐普通二叉搜索树，你要追问什么？
4. 如果数据几乎不更新，是否可以用排序列表加 bisect？

---

课后测验

📝 课后测验

得分：0 / 0

---

上一节：2.5 集合与字典：哈希表

下一节：2.7 优先队列与堆