外观
14 - 二叉搜索树:有序数据如何同时支持查询与更新
前置阅读:13 - 二叉树遍历与层级结构、08 - 排序算法怎么选。
数据库索引不是普通 BST,差异见数据库 11 - B+ Tree 索引原理。精确查找与范围查询的取舍可对比Hash 表原理与工程应用。
摘要
如果需要判断某个编号是否存在,还要按编号列出一段区间内的数据,索引就需要保留键的顺序;数据持续变化时,还要能插入和删除。二叉搜索树把这些操作组织在同一棵树上,但操作耗时取决于树高,不是用了树就一定快。
本文先解释节点之间的有序关系,再推演查询、插入、删除和范围搜索,最后讨论普通树的退化问题及工程中的结构选择。
1. 有序不变量
**二叉搜索树(Binary Search Tree,BST)**是一种带排序规则的二叉树:每个节点最多有两个子节点,并保存用于比较的键(Key)。本文只保存整数键,不保存额外业务值;left、right 是左右子节点的引用,null 表示没有节点。
它要求对每个节点都成立:左子树中的所有键小于当前键,右子树中的所有键大于当前键。这个在每次更新后都必须保持的条件叫作有序不变量。只检查直接孩子不够:根为 5 时,左孩子可以是 3,但 3 的右孩子若为 6,就违反了根节点的约束。
例如以 5 为根,左子树保存 2、3、4,右子树保存 6、7、8。查找 6 时,先与 5 比较,就能排除整个左子树。后续每次比较都用同样的规则缩小搜索范围。
重复键是覆盖关联值、累加计数,还是另设节点,必须由实现明确。本文代码在键相等时直接返回原节点,因此重复插入不会增加节点,相当于整数集合。若允许重复键分开存放,就需要重新约定相等键放在哪一侧,不能直接沿用这里的严格大小关系。
2. 查询与插入
下面是需要放入 Java 类中的局部片段。查询沿一条路径向下走:相等就返回成功,小于当前键就进入左子树,否则进入右子树;走到 null 表示不存在。插入沿同样的路径寻找空位置,再创建节点。
java
static class Node {
int key;
Node left, right;
Node(int key) {
this.key = key;
}
}
static Node insert(Node root, int key) {
if (root == null) return new Node(key);
if (key < root.key) root.left = insert(root.left, key);
else if (key > root.key) root.right = insert(root.right, key);
return root;
}
static boolean contains(Node root, int key) {
while (root != null) {
if (key == root.key) return true;
root = key < root.key ? root.left : root.right;
}
return false;
}insert 返回更新后的子树根,父节点必须用返回值重新连接对应孩子;整棵树也应写成 root = insert(root, key),否则向空树插入时会丢失新根。
设不同键的数量为 n,树高 h 按根到最深叶子路径上的节点数计算,空树为 0。每一步只比较一个节点,因此查询和插入的时间上界为 O(h)(忽略常数倍的增长量级)。当高度保持在 O(log n) 时,操作才有对数级上界;退化成单链时,树高为 n,最坏时间为 O(n)。递归插入还需要 O(h) 调用栈空间,迭代查询只需常数辅助空间。
3. 删除三种情况
删除时先按查询规则定位目标,再根据子节点数量处理:
- 叶子节点没有孩子,父节点指向它的引用可以改为
null。 - 只有一个子节点时,用这个孩子替代目标节点。孩子的整棵子树原本就满足祖先施加的大小约束,因此可以接到目标原来的位置。
- 有两个子节点时,不能直接丢弃任一子树。可以用中序后继或前驱的键替换当前键,再删除被复制键的原节点。
中序后继是中序序列中紧随当前键的节点;当前节点有右子树时,它就是右子树的最小节点,从右孩子出发一直向左即可找到。中序前驱则是左子树的最大节点。后继比左子树所有键都大,又不大于右子树其他键;删除原后继后,替换位置仍满足严格有序关系。后继没有左孩子,删除它只需处理前两种情况,但要保留它可能拥有的右子树。
4. 为什么需要平衡树
按 1,2,3,4,5 插入普通 BST,每个新键都比已有键大,只能不断接到最右侧,最终形成单链。树虽然仍满足有序不变量,查询却无法快速排除大量节点;可见“键有序”和“树高受控”是两个不同条件。
平衡树在更新后调整结构,使高度保持在对数级。AVL 树和红黑树(Red-Black Tree)使用不同的平衡约束,并通过旋转等操作调整结构。旋转是局部改变父子关系,同时保持中序键序列不变,所以不会破坏查找依赖的有序性。本文不实现这些调整算法。
Java TreeMap、TreeSet 使用红黑树实现,具体细节以目标 JDK 源码为准。
SortedMap 是按键排序的映射接口,NavigableMap 在此基础上提供寻找相邻键等导航操作。排序、范围视图和基本操作语义属于公开契约;红黑树节点布局、旋转细节属于具体 JDK 实现。业务应使用容器提供的接口,不依赖内部节点颜色或树形结构。
5. 完整可运行示例:插入、查询、删除与范围搜索
下面的完整类对应文件名 BstDemo.java。N 是前面节点模型的简写:k 为键,l、r 为左右孩子;put、has 分别对应插入和查询。range 把闭区间 [lo, hi] 内的键追加到调用方提供的非空列表,不会清空已有内容。示例假设树有限、无环,操作期间没有并发修改。
java
import java.util.*;
/**
* 可运行示例:二叉搜索树:有序数据如何同时支持查询与更新。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class BstDemo {
static class N {
int k;
N l, r;
N(int k) {
this.k = k;
}
}
static N put(N n, int k) {
if (n == null) return new N(k);
// 根据左小右大的不变量,只进入可能包含目标的一侧。
if (k < n.k) n.l = put(n.l, k);
else if (k > n.k) n.r = put(n.r, k);
return n;
}
static boolean has(N n, int k) {
while (n != null) {
if (k == n.k) return true;
n = k < n.k ? n.l : n.r;
}
return false;
}
static N delete(N n, int k) {
if (n == null) return null;
if (k < n.k) n.l = delete(n.l, k);
else if (k > n.k) n.r = delete(n.r, k);
else {
// 只有零个或一个子节点时,直接用非空子树替代当前节点。
if (n.l == null) return n.r;
if (n.r == null) return n.l;
// 两个子节点时,选择右子树最小节点作为中序后继。
N s = n.r;
while (s.l != null) s = s.l;
n.k = s.k;
n.r = delete(n.r, s.k);
}
return n;
}
static void range(N n, int lo, int hi, List<Integer> out) {
if (n == null) return;
// 当前 Key 已不大于下界时,左子树全部可以剪掉。
if (n.k > lo) range(n.l, lo, hi, out);
if (n.k >= lo && n.k <= hi) out.add(n.k);
if (n.k < hi) range(n.r, lo, hi, out);
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
N r = null;
for (int v : new int[] { 5, 3, 7, 2, 4, 6, 8 }) r = put(r, v);
System.out.println(has(r, 6));
List<Integer> o = new ArrayList<>();
range(r, 4, 7, o);
System.out.println(o);
r = delete(r, 5);
}
}删除双子节点的推演
这组输入形成以 5 为根、左右孩子为 3 和 7 的树。按代码手工推演,两行预期输出依次为 true 和 [4, 5, 6, 7],不是实测记录。最后一次删除没有打印结果。
删除根 5 时,从右孩子 7 向左找到 6,它是中序后继。n.k = s.k 只把根的键改为 6;随后 n.r = delete(n.r, s.k) 从右子树删除原来的 6,并接回更新后的子树。这一步不能省略,否则会留下重复键。删除后,中序结果预期为 [2, 3, 4, 6, 7, 8]。
delete 和插入一样返回新的子树根,因此调用方需要接住返回值,尤其是删除根节点时。它先定位目标,再寻找和删除后继,总共仍沿有限条树高范围内的路径前进,时间为 O(h),递归调用栈空间为 O(h)。范围搜索还涉及多个结果,不能套用单键操作的复杂度,见下一节。
6. 范围查询
中序遍历按“左子树、当前节点、右子树”的顺序访问。由于左侧所有键更小、右侧所有键更大,递归应用这一顺序就能得到递增序列。范围搜索在此基础上做剪枝,即跳过确定不可能包含结果的分支。
对闭区间 [lo, hi],示例中的三个判断分别表示:
- 仅当当前键大于
lo时进入左子树;否则左子树所有键都小于下界。 - 当前键同时满足
>= lo和<= hi时加入结果,保留两个边界。 - 仅当当前键小于
hi时进入右子树;否则右子树所有键都大于上界。
例如搜索 [4, 7],到达节点 3 时无需查看它的左子树,到达 7 时无需查看它的右子树,但 7 本身仍需输出。
设 lo <= hi,结果包含 m 个键。在整数比较和列表追加按常数成本计时,范围搜索的时间为 O(h + m):除了通往区间边界的路径,还要访问和输出区间内的节点。平衡树中为 O(log n + m),若区间包含所有键,仍需 O(n) 时间。递归辅助空间为 O(h),新增结果另占 O(m) 空间。示例在 lo > hi 时不会追加结果,但调用方仍应明确倒置区间是否属于合法输入。
普通 Hash 表不维护键序,因此不能沿有序分支剪枝;若没有额外索引,列出一个区间内的所有键通常需要扫描整个表。有序索引的价值正是保留这种可用于筛选和顺序输出的关系。
7. BST、B+ Tree 与跳表的边界
- 内存 BST通常以对象节点和引用为主;有序映射(Map)保存键值对,有序集合(Set)只保存元素,需要稳定操作上界时通常使用平衡树容器。
- 数据库 B+ Tree面向页组织数据。页是成块存储和读取的单位;高扇出表示一个内部节点能指向许多孩子,可减少树的层数,从而降低页访问和 I/O 成本。叶子之间的顺序连接适合范围扫描,具体数据库机制见开头引用的文章。
- 跳表在有序链表上增加多级索引,让查找先跳过较长区段,再下到更细的层。在适当的随机层级策略下,它提供期望对数级查找,并支持沿底层链表做范围遍历;“期望”不等于每次操作都有同样的最坏上界。实现和并发更新策略还需另行考虑。
“都是有序索引”不代表它们可以互换。数据所在介质、更新模型、范围扫描和并发协议共同决定结构选择。
8. 验证与排障
- 随机插入后,中序结果应严格递增,并与去重后的参考集合一致;这同时检查有序性和重复键策略。
- 删除后检查不同键的数量、查询结果和有序性;覆盖叶子、单子节点、双子节点、根节点、不存在的键,以及后继带右孩子的情况。
- 检查范围搜索的边界包含、空结果、全量结果和倒置区间,并与参考集合筛选出的结果比较。
- 使用升序和降序输入检查普通 BST 的退化;延迟异常时记录树高和比较次数,元素总数相同的树也可能有不同高度。
- 使用 Java 有序容器时,检查比较器
Comparator的语义。它返回负数、0、正数分别表示小于、同一排序位置、大于;比较结果为 0 的不同业务对象会被有序 Set/Map 视作同一排序位置,必须确认这符合业务对“相同键”的定义。
示例的 main 只演示一组插入、一次成功查询、一次范围搜索和一次双子节点删除,不能当作完整边界测试。
9. 容易踩的坑
- 直接声称 BST 操作是
O(log n),忽略平衡条件。 - 删除双子节点后未正确连接后继子树。
- 认为比较器与
equals的相等语义天然一致。有序容器按比较结果定位键,若两者定义不同,集合或映射的行为可能不符合业务预期。 - 修改已进入有序容器的键中参与比较的字段,却没有删除后重新插入。容器不会因此自动重排节点,后续查询可能沿错误分支前进。
- 递归处理极端退化树,调用深度随树高增长,可能导致栈溢出。
10. 总结
BST 用树形局部有序换取查询、更新和范围遍历的统一能力,但性能取决于树高。
- 普通 BST 只有在高度受控时才接近
O(log n)。 - 中序遍历与范围剪枝是有序树的重要价值。
- 工程上通常使用成熟平衡树容器,而不是自行维护旋转逻辑。
下一篇:Trie 前缀树。数据库页索引继续阅读B+ Tree 索引原理。