主题
第四章 树、二叉搜索树与堆
1. 为什么树结构重要
当数据关系不再只是前后顺序，而是呈现“一个节点下面挂多个子节点”的层次结构时，线性结构就不够用了。树结构能自然表达：
- 文件目录。
- 组织架构。
- 表达式语法树。
- 数据库索引。
- 搜索决策过程。
树之所以在计算机系统里极其重要，是因为它同时兼顾了两点：
- 能表达层次关系。
- 能在合适约束下支持高效查找、插入和最值维护。
2. 树的基本术语
在这棵树中：
8是根节点。3和10是8的子节点。1、6、14是叶子节点。- 从根到某个节点的边数称为该节点深度。
- 从某个节点到其最深叶子的最长路径，可用于定义高度。
这些术语不是为了背诵，而是为了后续准确讨论遍历、平衡、堆序性质和搜索路径。
3. 树的遍历：理解递归结构的第一步
对二叉树最经典的三种深度优先遍历是：
- 前序：根 -> 左 -> 右
- 中序：左 -> 根 -> 右
- 后序：左 -> 右 -> 根
3.1 Go 中的二叉树节点定义
go
package tree
type Node struct {
Key int
Left *Node
Right *Node
}3.2 前序与中序遍历
go
package tree
func Preorder(root *Node, out *[]int) {
if root == nil {
return
}
*out = append(*out, root.Key)
Preorder(root.Left, out)
Preorder(root.Right, out)
}
func Inorder(root *Node, out *[]int) {
if root == nil {
return
}
Inorder(root.Left, out)
*out = append(*out, root.Key)
Inorder(root.Right, out)
}树遍历是理解递归的绝佳载体，因为每个子树本身又是一棵树。递归写法短，不代表它“简单”；它只是把树的自相似结构直接映射到了函数定义上。
4. 二叉搜索树：利用有序性做查找
二叉搜索树（BST, Binary Search Tree）最核心的不变量是：
- 任意节点左子树所有键都小于该节点键值。
- 任意节点右子树所有键都大于该节点键值。
这条规则让查找过程像“在树里做二分”。
查找 6 时，路径是 8 -> 3 -> 6。如果树保持较平衡，路径长度大约是树高，因此查找、插入、删除平均可做到 O(log n)。
4.1 BST 查找与插入
go
package tree
func Search(root *Node, key int) *Node {
cur := root
for cur != nil {
if key == cur.Key {
return cur
}
if key < cur.Key {
cur = cur.Left
} else {
cur = cur.Right
}
}
return nil
}
func Insert(root *Node, key int) *Node {
if root == nil {
return &Node{Key: key}
}
if key < root.Key {
root.Left = Insert(root.Left, key)
} else if key > root.Key {
root.Right = Insert(root.Right, key)
}
return root
}4.2 删除为什么更难
BST 删除要区分三种情况：
- 删除叶子节点：直接删。
- 删除只有一个孩子的节点：用孩子顶上来。
- 删除有两个孩子的节点：通常用中序后继或中序前驱替代。
这说明数据结构难点常常不在“主流程”，而在边界条件和不变量维护。
5. BST 为什么会退化
如果按 1,2,3,4,5 这样的有序序列依次插入，BST 会退化成链表。
此时查找复杂度从期望的 O(log n) 退化为 O(n)。这就是为什么平衡树思想重要。AVL 树、红黑树、Treap、B 树家族，都是在解决“如何防止搜索树退化”。
本章不展开完整平衡树实现，但必须建立一个清晰认识：搜索树的高效不是天赐的，而是通过额外约束维护出来的。
6. 堆：不是有序树，而是“局部有序”的完全二叉树
堆（Heap）与 BST 很容易混淆。它们都是树，但目标不同：
- BST 追求按键查找路径可快速缩小范围。
- 堆只保证父节点与子节点之间的局部顺序，例如最小堆要求父节点小于等于孩子。
所以堆适合：
- 快速取最小值或最大值。
- 实现优先队列。
- 堆排序。
6.1 堆为什么常用数组表示
完全二叉树天然适合顺序存储。若根下标为 0：
- 左孩子下标为
2*i+1 - 右孩子下标为
2*i+2 - 父节点下标为
(i-1)/2
不需要额外指针，就能通过下标关系表达树。
7. 用 Go 实现一个最小堆
go
package heap
import "fmt"
type MinHeap struct {
data []int
}
func (h *MinHeap) Len() int {
return len(h.data)
}
func (h *MinHeap) Peek() (int, error) {
if len(h.data) == 0 {
return 0, fmt.Errorf("heap is empty")
}
return h.data[0], nil
}
func (h *MinHeap) Push(x int) {
h.data = append(h.data, x)
h.up(len(h.data) - 1)
}
func (h *MinHeap) Pop() (int, error) {
if len(h.data) == 0 {
return 0, fmt.Errorf("heap is empty")
}
top := h.data[0]
last := len(h.data) - 1
h.data[0] = h.data[last]
h.data = h.data[:last]
if len(h.data) > 0 {
h.down(0)
}
return top, nil
}
func (h *MinHeap) up(i int) {
for i > 0 {
p := (i - 1) / 2
if h.data[p] <= h.data[i] {
break
}
h.data[p], h.data[i] = h.data[i], h.data[p]
i = p
}
}
func (h *MinHeap) down(i int) {
n := len(h.data)
for {
left := 2*i + 1
right := 2*i + 2
smallest := i
if left < n && h.data[left] < h.data[smallest] {
smallest = left
}
if right < n && h.data[right] < h.data[smallest] {
smallest = right
}
if smallest == i {
break
}
h.data[i], h.data[smallest] = h.data[smallest], h.data[i]
i = smallest
}
}7.1 为什么堆插入和删除是 O(log n)
因为每次上浮或下沉最多沿树高移动，而完全二叉树高度大约是 log n。这就是堆作为优先队列的核心优势：插入不慢，取最值也快。
8. 树结构之间的分工
| 结构 | 核心不变量 | 擅长操作 |
|---|---|---|
| 普通树 | 层次关系 | 表达目录、语法、组织结构 |
| BST | 左小右大 | 查找、插入、删除 |
| 平衡搜索树 | 额外平衡约束 | 保证 O(log n) 级操作 |
| 堆 | 父子局部有序 | 快速取最值、优先队列 |
注意：堆不是用来高效查找任意元素的，BST 也不是用来最快取最值的。不同树的规则不同，服务目标也不同。
9. 本章小结
这一章的关键不是“树有几个术语”，而是：
- 树结构引入了层次关系。
- 递归遍历是因为子树天然自相似。
- BST 通过全局有序规则支持查找。
- 堆通过局部有序规则支持最值维护。
- 高性能树结构的本质，是维护不变量。
下一章进入哈希表后，你会看到另一条完全不同的思路：不靠比较路径，而靠映射直接定位。
10. 继续深入
如果你已经理解了 BST 为什么会退化、堆为什么只维护局部有序，那么下一步就该进入真正的平衡树体系：
- AVL 树如何通过高度平衡约束把树高压住。
- 红黑树为什么放宽平衡条件，却仍能把高度控制在对数级。
- B 树 / B+ 树为什么在外存系统里比普通二叉树更重要。
进阶内容见：树结构进阶：AVL、红黑树与多路平衡树