08 - 二叉树与二叉搜索树
上一章的树，每个节点能有任意多个孩子。这一章我们看一种加了限制的树——每个节点最多两个孩子，以及在它基础上一个能「快速查找」的经典设计：二叉搜索树。
二叉树：每个节点最多两个孩子
二叉树（Binary Tree） 就是限定「每个节点最多有两个孩子」的树，分别叫左孩子和右孩子：
[A]
/ \
[B] [C]
/ \ \
[D] [E] [F]为什么专门研究「最多两个孩子」这种？因为它结构简单又足够强大——「左 / 右」二选一的分叉，正好能对应「小 / 大」「是 / 否」这类二分判断，是很多高效算法的基础。绝大多数实用的树，都是二叉树或它的变体。
二叉搜索树：给二叉树定个「大小规矩」
光是二叉树还看不出查找快在哪。真正的魔法来自加一条规矩，就成了二叉搜索树（BST，Binary Search Tree）：
对每个节点：它左边子树里所有的值，都比它小；右边子树里所有的值，都比它大。
举个例子，这样排列：
[8]
/ \
[3] [10]
/ \ \
[1] [6] [14]
/ \ /
[4] [7] [13]（把上图当示意：8 的左边全是比 8 小的，右边全是比 8 大的；每个节点都满足这条规矩。）
查找为什么变快：每一步排除一半
有了「左小右大」这条规矩，查一个数就像猜数字游戏。假设要找 7：
- 从根 8 开始：7 < 8 → 右边一整棵子树全是比 8 大的，直接不用看了，往左走。
- 到 3：7 > 3 → 往右走（左边比 3 小的全排除）。
- 到 6：7 > 6 → 往右走。
- 到 7：找到了！
看到了吗？每比较一次，就砍掉大约一半的数据不用看。 这正是第 02 章说的 O(log n)——100 万个数据，也就查 20 来次。
就像查字典：翻到中间，发现要找的字在后半本，前半本直接扔掉不看；再翻中间，又扔掉一半……很快锁定。BST 把这种「折半」的智慧固化进了结构里。
- 查找、插入、删除：理想情况 O(log n) —— 又快，又能保持数据有序（这正是哈希表做不到的）。
它顺便解决了哈希表的软肋
回忆第 06 章，哈希表查得快但数据无序。二叉搜索树弥补了这点：
- 它能快速查找（虽然比哈希表的 O(1) 稍慢，是 O(log n)）；
- 但它天然有序——按「左→根→右」的顺序遍历，出来的正好是从小到大排好的！所以要「范围查询」（找出 5 到 10 之间所有的数）、「找最小/最大」，BST 轻松搞定，哈希表却无能为力。
致命隐患：可能「长歪」退化成链表
BST 有个大问题。如果你按已经排好序的顺序依次插入 1、2、3、4、5，会发生什么？
[1]
\
[2]
\
[3]
\
[4]
\
[5]每个新数都比前一个大，全挂在右边，树退化成了一条线（链表）！这时候查找又变回了 O(n)，「折半」的优势荡然无存。
这就像一棵长歪了的树，全往一边倒。问题的根源是树的左右两边不平衡。
怎么解决这个「长歪」的问题？答案就是下一章的主角——平衡树，它会在插入时自动「掰正」，始终保持左右均衡。
小结
- 二叉树：每个节点最多两个孩子（左、右），结构简单又强大，是很多算法的基础。
- 二叉搜索树（BST）：加一条规矩——左子树都比它小、右子树都比它大。
- 查找像猜数字/查字典，每比较一次排除一半，理想下查找/插入/删除都是 O(log n)。
- 相比哈希表，BST 慢一点但天然有序，擅长范围查询、找最值。
- 隐患：按有序数据插入会让树长歪退化成链表（O(n)），根源是不平衡——下一章的平衡树来解决。
下一章 → 09 - 平衡树与 B 树：数据库为什么用它 ｜ 回到 README 目录