二叉搜索树
复习
- 二叉树与递归遍历：前序、中序、后序
- 顺序查找与二分查找：有序才能二分
- 树：用父子关系表示层次
TL;DR
- 二叉搜索树要求左子树都小、右子树都大
- 查找时可以像二分一样排除一半
- 中序遍历能得到有序序列
- 理想情况下，查找是
O(log n)
正文
普通的二叉树只是有了形状，还没有“规律”。如果给节点之间加上一条大小规则，它就能用来高效查找了。这样的树，叫二叉搜索树（BST，Binary Search Tree）。
一条简单的规则
二叉搜索树要求：对任意一个节点，它的左子树里所有值都比它小，右子树里所有值都比它大。
这条规则让整棵树“有序”。回想二分查找为什么快——因为能根据大小关系排除一半。二叉搜索树把这套逻辑搬到了树上：
- 要找的值比当前节点小？往左走
- 比当前节点大？往右走
每往下走一层，就排除掉一大半，所以平均只需要 O(log n) 次比较。
中序就是有序
还记得上一章说中序遍历能“得到有序序列”吗？在二叉搜索树里，这条性质体现得淋漓尽致。
中序遍历的顺序是“左 → 根 → 右”。而在 BST 里，左子树都比根小、右子树都比根大，所以按这个顺序访问，得到的恰好是从小到大排好的序列。
这可不是巧合，而是“有序规则”和“中序遍历”共同作用的必然结果。要检查一棵树是不是合法的二叉搜索树，跑一遍中序遍历，看看是否递增，就知道了。
插入也遵循同一条规则
往 BST 里插入新值，同样从根出发：小就往左、大就往右，一路走到空位，把新节点挂在那里。查找、插入都走同一条路，逻辑统一。
不过，这一切都建立在“树比较平衡”的前提下。如果树长歪了，O(log n) 就保不住了——这正是下一章要面对的问题。
思考题 1
二叉搜索树的“有序”体现在哪里？
思考题 2
为什么二叉搜索树的查找可以像二分查找一样排除一半？
小结
知识点
- 二叉搜索树：左子树都小、右子树都大
- 查找沿大小规则走，平均
O(log n) - 中序遍历得到有序序列
- 插入同样按大小规则走到空位
参考资料
- Wikipedia(zh)：二叉搜索树：满足有序性质的二叉树
- Wikipedia(zh)：树的遍历：中序遍历得到有序序列
思考题答案（仅供参考）
思考题 1
体现在“左子树都比根小、右子树都比根大”这条规则上。正因如此，中序遍历访问的顺序恰好是从小到大，整棵树对大小关系形成了有序的组织。
思考题 2
因为每个节点都把取值范围分成了“比它小”和“比它大”两部分。查找时根据目标与当前节点的大小关系，就能决定只往左或只往右，从而排除掉另一半子树，过程和二分查找的“砍一半”本质一致。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪