Ch14 §03 树 · 讲解稿¶

章节定位: 树形结构 + 层次组织。教"层次 + 递归": 二叉树 / BST / AVL / 红黑树 / Trie / 堆 / 树状数组。承接: §02 链表 → §03 树 (非线性) 走向: §04 图 / §05 排序篇幅: ~3800 字 / 阅读 11 分钟 / 讲解 22-25 分钟

一 · 一句话总览¶

树 = 层次结构 + 递归。覆盖: 二叉树遍历 / BST (查找) / 平衡树 (AVL/红黑) / Trie (前缀) / 堆 (优先队列)。AI 系统: AST, 决策树 (Ch05), 数据库索引, BPE token trie。

二 · 章节主线 (5 段)¶

第 1 段 · 二叉树与遍历 (8 分钟)¶

3.1.1 节点定义¶

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

3.1.2 四种遍历¶

顺序	递归	栈序
前序	根 → 左 → 右	根左右
中序	左 → 根 → 右	左根右
后序	左 → 右 → 根	左右根
层序	BFS, 队列	-

def preorder(node):
    if not node: return
    yield node.val
    yield from preorder(node.left)
    yield from preorder(node.right)

def inorder(node):
    if not node: return
    yield from inorder(node.left)
    yield node.val
    yield from inorder(node.right)

def level_order(root):
    if not root: return []
    result = []
    q = deque([root])
    while q:
        node = q.popleft()
        result.append(node.val)
        if node.left: q.append(node.left)
        if node.right: q.append(node.right)
    return result

3.1.3 经典问题¶

最大深度
验证 BST
最近公共祖先 (LCA)
之字形遍历

3.1.4 重建二叉树¶

前序 + 中序 → 唯一二叉树。

def build(pre, ino):
    if not pre: return None
    root = TreeNode(pre[0])
    idx = ino.index(pre[0])
    root.left = build(pre[1:idx+1], ino[:idx])
    root.right = build(pre[idx+1:], ino[idx+1:])
    return root

第 2 段 · 二叉搜索树 BST (10 分钟)¶

3.2.1 性质¶

左子树 < 根 < 右子树 (中序有序)。

3.2.2 查找¶

def search(root, val):
    if not root or root.val == val: return root
    if val < root.val: return search(root.left, val)
    return search(root.right, val)

3.2.3 插入¶

def insert(root, val):
    if not root: return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

3.2.4 删除 (3 情况)¶

叶子: 直接删
一子: 替换
两子: 找后继 (右子最小) 或前驱, 替换后删

3.2.5 复杂度¶

平均 \(O(\log n)\) (平衡), 最坏 \(O(n)\) (退化成链表)。

第 3 段 · 平衡树: AVL 与红黑 (8 分钟)¶

3.3.1 为什么需要¶

BST 退化为链表 → \(O(n)\)。平衡树维持高度 \(\sim O(\log n)\)。

3.3.2 AVL 树¶

平衡条件: \(|\text{height}(left) - \text{height}(right)| \leq 1\)

操作: 旋转 (左旋 / 右旋 / 左右 / 右左)。

3.3.3 红黑树 (C++ std::map / Java TreeMap)¶

5 性质: 1. 节点红 / 黑 2. 根黑 3. 叶 (NIL) 黑 4. 红节点子黑 5. 黑高一致

操作: 变色 + 旋转。\(O(\log n)\)。

3.3.4 对比¶

维度	AVL	红黑
严格度	高	中
查找	稍快	稍慢
插入删除	慢 (旋转多)	快 (旋转少)
应用	数据库	通用 (C++/Java)

第 4 段 · Trie / 堆 / 高级 (8 分钟)¶

3.4.1 Trie (前缀树)¶

每个节点是字符, 子节点哈希。共享前缀, 用于自动补全 / BPE。

class Trie:
    def __init__(self):
        self.root = {}
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node['#'] = True  # 终止标志
    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node: return False
            node = node[ch]
        return '#' in node
    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node: return False
            node = node[ch]
        return True

3.4.2 堆 (heap)¶

完全二叉树 + 父 ≤ 子 (最小堆)。数组实现: 父 \(i\), 子 \(2i+1, 2i+2\)。

import heapq
heap = [3, 1, 4, 1, 5]
heapq.heapify(heap)  # O(n)
heapq.heappush(heap, 2)  # O(log n)
heapq.heappop(heap)  # 1, O(log n)
heapq.nlargest(3, heap)  # [5, 4, 3]

3.4.3 堆应用¶

优先队列
Top K 问题
Dijkstra (§04)
优先级经验回放 (Ch06)

3.4.4 树状数组 (BIT)¶

支持 prefix sum + point update, 都 \(O(\log n)\)。代码比线段树简单。

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i
    def query(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

3.4.5 线段树¶

区间查询 / 更新 \(O(\log n)\)。比 BIT 强大但复杂。

第 5 段 · 实战与陷阱 (8 分钟)¶

3.5.1 B 树 / B+ 树¶

磁盘友好, 每个节点多键。数据库索引。

3.5.2 Splay 树¶

刚访问的移到根 (摊销 \(O(\log n)\))。用于缓存。

3.5.3 跳表¶

多层链表, 概率平衡。比平衡树简单, Redis zset 底层。

3.5.4 决策树 (Ch05)¶

非二叉, 但遍历思想同。

3.5.5 陷阱¶

递归栈深: 大树用迭代。
AVL 频繁旋转: 写多读少别用。
Trie 内存: 字符集大时耗内存, 压缩 Trie。
堆不是有序: 只保证堆顶, 全部有序需 heap sort。
BST 删除: 三情况别漏。

三 · 易错点 (5 条)¶

BST 中序: 是有序序列。
平衡树高度: \(O(\log n)\), 不是 \(O(n)\)。
Trie 与哈希: Trie 共享前缀快, 哈希通用。
堆找最大: 用最大堆, 或取反存最小堆。
删除 BST 两子节点: 用后继 / 前驱替换。

四 · 跨章连接¶

章节	关联
Ch07 §04 Transformer	BPE = trie
Ch05 §05 决策树	树形模型
Ch13 §03 文件系统	ext4 = B 树
Ch12 §03 GNN	K-D Tree

五 · 自测 5 题¶

二叉树四种遍历?
BST 中序遍历结果?
AVL 与红黑树差别?
Trie 应用场景?
堆插入复杂度?

六 · 一句话总结¶

树 = 层次结构 + 递归。BST 查找 / 平衡树维护 / Trie 前缀 / 堆优先。Ch14 §04 进入图算法。

七 · 板书建议¶

[板书 1: 遍历]
   前 / 中 / 后 / 层序
   递归 + 栈

[板书 2: BST]
   左 < 根 < 右
   中序有序

[板书 3: 平衡]
   AVL 严格 / 红黑近似
   5 性质

[板书 4: 堆]
   完全二叉树 + 父≤子
   数组实现

八 · 参考资料¶

Cormen et al., CLRS Ch 12-13 (树)
Sedgewick, "Algorithms"
Ch07 §04 Transformer (BPE)
Ch05 §05 决策树