数学重学 - 18 树与递归结构

这是 数学重学路线图 阶段三的子页面

📌 前置知识：17-图论基础

本页核心：树是一种特殊的图（连通无环），几乎所有数据库和文件系统都建立在树的数学性质之上

---

一、树是什么？——从直觉开始

直觉比喻：

家谱：一个祖先向下分支，没有”表亲结婚”（无环）

文件目录：根目录 → 子目录 → 文件，每个文件只有一个父目录

公司组织架构：CEO → VP → 经理 → 员工

1.1 基本术语

根（Root）：树的顶部节点，没有父节点

叶子（Leaf）：没有子节点的节点

内部节点：既非根也非叶子的节点

深度（Depth）：从根到该节点的边数（根的深度=0）

高度（Height）：从该节点到最远叶子的边数（叶子高度=0）

树的高度：根节点的高度

度（Degree）：一个节点的子节点数

1.2 树的数学定义

树是一个连通无环图 G=(V,E)，其中 |E| = |V| - 1

任意两个节点之间恰好一条路径

删任一条边 → 不连通；加任一条边 → 产生环

---

二、二叉树的数学性质

2.1 什么是二叉树

每个节点最多两个子节点（左子、右子）

最基础也最重要的树结构

2.2 关键性质

性质1：第k层最多 2^(k-1) 个节点（根是第1层）

第1层：2^0 = 1个（根）

第2层：2^1 = 2个

第3层：2^2 = 4个

…

性质2：高度h的二叉树最多 2^h - 1 个节点

即满二叉树：1 + 2 + 4 + … + 2^(h-1) = 2^h - 1

性质3：n个节点的完全二叉树高度 = ⌊log₂n⌋ + 1

这就是为什么基于树的操作是 O(log n)

性质4：叶子节点数 n₀ 与度为2的节点数 n₂ 的关系：n₀ = n₂ + 1

Python验证这些性质

import math

# 性质验证
for h in range(1, 8):
max_nodes = 2**h - 1
print(f"高度{h}: 最多{max_nodes}个节点")

print()
for n in [7, 15, 100, 1000, 1000000, 10000000]:
height = math.floor(math.log2(n)) + 1
print(f"n={n:>8}: 完全二叉树高度={height}")

# n=       7: 完全二叉树高度=3
# n=      15: 完全二叉树高度=4
# n=     100: 完全二叉树高度=7
# n=    1000: 完全二叉树高度=10
# n= 1000000: 完全二叉树高度=20
# n=10000000: 完全二叉树高度=24
# 1000万个节点，只需要24层！这就是log的力量

---

三、完全二叉树与堆

3.1 完全二叉树

除最后一层外，每层都满；最后一层的节点从左到右连续

可以用数组存储，不需要指针：

根在索引1（或0）

索引i的节点：

父节点：i // 2

左子节点：2 * i

右子节点：2 * i + 1

直觉比喻：像把树”压平”放进数组，父子关系用数学公式算

3.2 堆（Heap）

最大堆：父节点 ≥ 子节点 → 根是最大值

最小堆：父节点 ≤ 子节点 → 根是最小值

核心操作：

插入：放到末尾，上浮（sift up）—— O(log n)

删除最值：用末尾替换根，下沉（sift down）—— O(log n)

获取最值：直接看根 —— O(1)

3.3 应用

堆排序：O(n log n)，原地排序

优先队列：每次取出优先级最高/最低的元素

Top-K问题：维护大小为K的最小堆

Python实现二叉最小堆

class MinHeap:
"""最小堆实现"""
def __init__(self):
    self.heap = [0]  # 索引0占位，实际元素从1开始
    self.size = 0

def _parent(self, i): return i // 2
def _left(self, i):   return 2 * i
def _right(self, i):  return 2 * i + 1

def _swap(self, i, j):
    self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

def _sift_up(self, i):
    """上浮：新元素与父节点比较"""
    while self._parent(i) > 0:
        if self.heap[i] < self.heap[self._parent(i)]:
            self._swap(i, self._parent(i))
        i = self._parent(i)

def _sift_down(self, i):
    """下沉：与较小的子节点交换"""
    while self._left(i) <= self.size:
        # 找较小的子节点
        smaller = self._left(i)
        if (self._right(i) <= self.size and
                self.heap[self._right(i)] < self.heap[smaller]):
            smaller = self._right(i)
        
        if self.heap[i] > self.heap[smaller]:
            self._swap(i, smaller)
        else:
            break
        i = smaller

def push(self, val):
    """插入元素 O(log n)"""
    self.heap.append(val)
    self.size += 1
    self._sift_up(self.size)

def pop(self):
    """弹出最小值 O(log n)"""
    if self.size == 0:
        raise IndexError("heap is empty")
    min_val = self.heap[1]
    self.heap[1] = self.heap[self.size]
    self.heap.pop()
    self.size -= 1
    if self.size > 0:
        self._sift_down(1)
    return min_val

def peek(self):
    """查看最小值 O(1)"""
    return self.heap[1] if self.size > 0 else None

# 演示
h = MinHeap()
for val in [5, 3, 8, 1, 2, 7, 4, 6]:
h.push(val)

print("堆排序结果: ", end='')
while h.size > 0:
print(h.pop(), end=' ')
# 输出: 1 2 3 4 5 6 7 8
print()

Top-K问题

import heapq

def top_k_largest(nums, k):
"""找出前K个最大元素（用大小为K的最小堆）"""
# 维护一个大小为K的最小堆
# 堆顶是当前K个最大值中的最小值
return heapq.nlargest(k, nums)

# 等价的手动实现
def top_k_manual(nums, k):
min_heap = []
for num in nums:
    if len(min_heap) < k:
        heapq.heappush(min_heap, num)
    elif num > min_heap[0]:
        heapq.heapreplace(min_heap, num)
return sorted(min_heap, reverse=True)

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7]
print(f"Top 5: {top_k_manual(data, 5)}")
# Top 5: [9, 9, 8, 7, 6]

---

四、二叉搜索树（BST）

4.1 定义

左子树所有节点 < 根 < 右子树所有节点

中序遍历 → 有序序列

4.2 操作复杂度

查找、插入、删除：平均 O(log n)

最坏情况（退化为链表）：O(n)

这就是为什么需要平衡树

4.3 为什么需要平衡

插入有序数据 [1,2,3,4,5] → BST变成一条链，高度=n

平衡树保证高度始终 O(log n)

4.4 常见平衡树

AVL树：严格平衡，任何节点左右子树高度差 ≤ 1

查找快，但插入/删除时旋转多

红黑树：近似平衡，高度 ≤ 2×log₂(n+1)

Java TreeMap/TreeSet, Linux CFS调度器

插入/删除旋转少，工程中更常用

直觉比喻：

AVL像一个强迫症整理员：每次都要完美对称

红黑树像一个务实整理员：差不多就行，别太歪就好

---

五、B树/B+树——数据库索引的核心

5.1 为什么不用二叉树做数据库索引？

磁盘IO是瓶颈：每次访问一个节点 = 一次磁盘IO

二叉树高度 = log₂n，n=1000万时高度≈24 → 24次IO太慢

需要一种又矮又胖的树 → B/B+树

5.2 B树核心思想

每个节点可以有很多个子节点（高扇出）

阶为m的B树：每个节点最多m个子节点，最多m-1个键

高度 = log_m(n)，m很大时高度极低

5.3 B+树（数据库最常用）

与B树的区别：

所有数据都在叶子节点

叶子节点用链表串联 → 支持高效范围查询

内部节点只存键，不存数据 → 一个节点能装更多键 → 更矮

直觉比喻：

B+树像一本书：内部节点是目录，叶子节点是正文

查单条 → 从目录翻到正文（3-4次翻页）

范围查询 → 翻到起始页后顺着读就行（链表）

5.4 高度计算

MySQL InnoDB：页大小16KB，假设每个键+指针≈10字节

单个节点可存约 16KB/10B ≈ 1600 个键

高度估算：

高度	最多记录数	场景
1	1,600	小表
2	1,600² ≈ 256万	中等表
3	1,600³ ≈ 40亿	大表

结论：1000万条记录的索引，高度只有3层 = 3次磁盘IO

Python计算B+树高度

import math

def bplus_tree_height(n_records, page_size_kb=16, key_ptr_bytes=10):
"""估算B+树高度"""
fanout = (page_size_kb * 1024) // key_ptr_bytes
if n_records <= 0:
    return 0
height = math.ceil(math.log(n_records) / math.log(fanout))
return max(1, height)

print("=== B+树高度估算 (16KB页, 10字节/键) ===")
for n in [1000, 10000, 1_000_000, 10_000_000, 100_000_000, 1_000_000_000]:
h = bplus_tree_height(n)
print(f"记录数={n:>13,}: 高度={h}")

# 记录数=        1,000: 高度=1
# 记录数=       10,000: 高度=2
# 记录数=    1,000,000: 高度=2
# 记录数=   10,000,000: 高度=3
# 记录数=  100,000,000: 高度=3
# 记录数=1,000,000,000: 高度=3

# 对比二叉树
print("\n=== 如果用二叉树 ===")
for n in [1000, 10_000_000]:
h_binary = math.ceil(math.log2(n))
h_bplus = bplus_tree_height(n)
print(f"n={n:>10,}: 二叉树高度={h_binary}, B+树高度={h_bplus}")
# n=     1,000: 二叉树高度=10, B+树高度=1
# n=10,000,000: 二叉树高度=24, B+树高度=3

---

六、大数据应用

6.1 LSM树（Log-Structured Merge Tree）

用在：LevelDB, RocksDB, HBase, Cassandra

核心思想：写入先进内存（MemTable），满了就写磁盘（SSTable），后台合并

优点：写入极快（顺序写磁盘）

缺点：读取可能慢（多层查找）

与B+树对比：

B+树：读优化，写时需要随机IO更新索引

LSM树：写优化，读时可能需要查多层

6.2 Merkle树（哈希树）

每个叶子节点存数据的哈希，非叶子节点存子节点哈希的哈希

只比较根哈希就能判断两棵树的数据是否完全相同

如果不同，可以 O(log n) 定位到差异的叶子节点

用途：

区块链：验证交易完整性

IPFS：内容寻址

数据库同步：Cassandra用Merkle树做副本对比

简单Merkle树实现

import hashlib

def sha256(data):
"""计算SHA-256哈希"""
return hashlib.sha256(data.encode()).hexdigest()[:16]  # 截短方便展示

class MerkleTree:
"""简易Merkle树"""
def __init__(self, data_blocks):
    self.leaves = [sha256(block) for block in data_blocks]
    self.root = self._build(self.leaves)

def _build(self, nodes):
    """递归构建Merkle树，返回根哈希"""
    if len(nodes) == 1:
        return nodes[0]
    if len(nodes) % 2 == 1:
        nodes.append(nodes[-1])  # 奇数个节点，复制最后一个
    
    parent_level = []
    for i in range(0, len(nodes), 2):
        combined = sha256(nodes[i] + nodes[i+1])
        parent_level.append(combined)
    
    return self._build(parent_level)

# 演示
blocks_a = ["tx1: Alice->Bob 10BTC", "tx2: Bob->Carol 5BTC",
        "tx3: Carol->Dave 3BTC", "tx4: Dave->Eve 1BTC"]
blocks_b = ["tx1: Alice->Bob 10BTC", "tx2: Bob->Carol 5BTC",
        "tx3: Carol->Dave 3BTC", "tx4: Dave->Eve 1BTC"]
blocks_c = ["tx1: Alice->Bob 10BTC", "tx2: Bob->Carol 5BTC",
        "tx3: Carol->Dave 3BTC", "tx4: TAMPERED!!!"]

tree_a = MerkleTree(blocks_a)
tree_b = MerkleTree(blocks_b)
tree_c = MerkleTree(blocks_c)

print(f"Tree A root: {tree_a.root}")
print(f"Tree B root: {tree_b.root}")
print(f"Tree C root: {tree_c.root}")
print(f"A == B ? {tree_a.root == tree_b.root}")  # True
print(f"A == C ? {tree_a.root == tree_c.root}")  # False（篡改被检测到）

---

七、安全应用

7.1 Merkle树数据完整性

下载大文件时只需先获取根哈希（可信来源）

分块下载，逐步验证 → 发现被篡改的块

Git也用类似机制：每个commit的hash依赖父commit和文件树

7.2 证书链（Certificate Chain）

根CA → 中间CA → 终端证书，形成一棵信任树

验证证书 = 从叶子到根的路径验证

# 证书链验证的简化模型
cert_chain = {
"root_ca": {
    "subject": "DigiCert Root CA",
    "issuer": None,  # 自签名
    "signed": ["intermediate_ca"]
},
"intermediate_ca": {
    "subject": "DigiCert Intermediate CA",
    "issuer": "root_ca",
    "signed": ["leaf_cert"]
},
"leaf_cert": {
    "subject": "*.example.com",
    "issuer": "intermediate_ca",
    "signed": []
}
}

def verify_chain(cert_chain, leaf, trusted_roots):
"""验证证书链"""
current = leaf
chain = [current]

while cert_chain[current]["issuer"] is not None:
    issuer = cert_chain[current]["issuer"]
    if issuer not in cert_chain:
        return False, chain, "签发者未知"
    chain.append(issuer)
    current = issuer

if current in trusted_roots:
    return True, chain, "验证通过"
return False, chain, "根证书不受信任"

ok, chain, msg = verify_chain(cert_chain, "leaf_cert", {"root_ca"})
print(f"验证结果: {msg}")
print(f"证书链: {' → '.join(chain)}")
# 验证结果: 验证通过
# 证书链: leaf_cert → intermediate_ca → root_ca

---

八、后端应用

8.1 Trie树（前缀树）——路由匹配

每个节点代表一个字符（或路径段）

共享公共前缀 → 节省空间

用途：URL路由匹配、自动补全、IP路由表

class TrieNode:
def __init__(self):
    self.children = {}
    self.handler = None  # 路由处理函数

class URLRouter:
"""简易URL路由器（Trie实现）"""
def __init__(self):
    self.root = TrieNode()

def add_route(self, path, handler):
    """注册路由"""
    node = self.root
    for segment in path.strip('/').split('/'):
        if segment not in node.children:
            node.children[segment] = TrieNode()
        node = node.children[segment]
    node.handler = handler

def match(self, path):
    """匹配路由"""
    node = self.root
    for segment in path.strip('/').split('/'):
        if segment in node.children:
            node = node.children[segment]
        elif '*' in node.children:
            node = node.children['*']
        else:
            return None
    return node.handler

# 演示
router = URLRouter()
router.add_route("/api/users", "list_users")
router.add_route("/api/users/profile", "get_profile")
router.add_route("/api/orders", "list_orders")
router.add_route("/api/orders/detail", "order_detail")

test_paths = ["/api/users", "/api/users/profile",
          "/api/orders", "/api/orders/detail", "/api/unknown"]
for path in test_paths:
result = router.match(path)
print(f"  {path:30s} → {result}")

8.2 优先队列调度

任务调度器用最小堆按优先级/截止时间排序

每次取出最紧急的任务处理

import heapq
import time

class TaskScheduler:
"""基于堆的任务调度器"""
def __init__(self):
    self.tasks = []  # 最小堆: (priority, timestamp, task_name)
    self.counter = 0

def add_task(self, task_name, priority):
    """添加任务，priority越小越优先"""
    self.counter += 1
    heapq.heappush(self.tasks, (priority, self.counter, task_name))

def get_next_task(self):
    """获取最高优先级的任务"""
    if self.tasks:
        priority, _, task_name = heapq.heappop(self.tasks)
        return task_name, priority
    return None

scheduler = TaskScheduler()
scheduler.add_task("普通日志处理", priority=5)
scheduler.add_task("安全告警处理", priority=1)
scheduler.add_task("数据备份", priority=3)
scheduler.add_task("紧急漏洞修复", priority=0)
scheduler.add_task("报表生成", priority=4)

print("任务执行顺序:")
while True:
result = scheduler.get_next_task()
if result is None:
    break
name, pri = result
print(f"  [优先级{pri}] {name}")
# [优先级0] 紧急漏洞修复
# [优先级1] 安全告警处理
# [优先级3] 数据备份
# [优先级4] 报表生成
# [优先级5] 普通日志处理

---

九、递归思维与树的遍历

9.1 为什么树和递归天生一对

树本身就是递归定义的：一棵树 = 根 + 若干子树

处理一棵树 = 处理根 + 递归处理每棵子树

9.2 三种遍历顺序

前序：根 → 左 → 右（先处理自己）

中序：左 → 根 → 右（BST得到有序序列）

后序：左 → 右 → 根（先处理子树，最后处理自己——适合”先算子问题”）

层序：按层从上到下（BFS）

Python实现遍历

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

def preorder(node):
"""前序遍历"""
if node is None:
    return []
return [node.val] + preorder(node.left) + preorder(node.right)

def inorder(node):
"""中序遍历"""
if node is None:
    return []
return inorder(node.left) + [node.val] + inorder(node.right)

def postorder(node):
"""后序遍历"""
if node is None:
    return []
return postorder(node.left) + postorder(node.right) + [node.val]

#       4
#      / \
#     2   6
#    / \ / \
#   1  3 5  7
root = TreeNode(4,
TreeNode(2, TreeNode(1), TreeNode(3)),
TreeNode(6, TreeNode(5), TreeNode(7))
)

print(f"前序: {preorder(root)}")   # [4,2,1,3,6,5,7]
print(f"中序: {inorder(root)}")    # [1,2,3,4,5,6,7] ← 有序！
print(f"后序: {postorder(root)}")  # [1,3,2,5,7,6,4]

---

十、练习题

练习1：二叉树性质

一棵完全二叉树有1023个节点，它的高度是多少？有多少个叶子节点？

高度 = ⌊log₂(1023)⌋ + 1 = 9 + 1 = 10

1023 = 2^10 - 1，这是一棵满二叉树

叶子节点 = 2^(10-1) = 512个

练习2：B+树高度

MySQL表有5000万条记录，InnoDB页16KB，每个键+指针占12字节

估算B+树索引的高度

扇出 = 16×1024/12 ≈ 1365

高度1: 1365条

高度2: 1365² ≈ 186万条

高度3: 1365³ ≈ 25.4亿条 > 5000万

答案：高度 = 3（只需3次磁盘IO）

练习3：堆操作

向空的最小堆依次插入 [5, 3, 8, 1, 2]，画出每步的堆状态

然后执行两次pop，结果是什么？

插入5: [5]

插入3: [3, 5]（3上浮）

插入8: [3, 5, 8]

插入1: [1, 3, 8, 5]（1一路上浮到顶）

插入2: [1, 2, 8, 5, 3]（2上浮到3的位置）

pop → 1, 堆变为 [2, 3, 8, 5]

pop → 2, 堆变为 [3, 5, 8]

练习4：Merkle树

你有8个数据块，构建Merkle树需要多少个哈希节点（包括叶子）？

如果第5个数据块被篡改，验证时最多需要比较几个哈希？

叶子8个 + 第二层4个 + 第三层2个 + 根1个 = 15个节点

验证路径长度 = log₂(8) = 3个兄弟节点的哈希（加上根=4次比较）

练习5：编程题

实现一个函数：给定一棵二叉搜索树，判断它是否是合法的BST

def is_valid_bst(node, min_val=float('-inf'), max_val=float('inf')):
"""验证BST合法性：每个节点必须在(min_val, max_val)范围内"""
if node is None:
    return True
if node.val <= min_val or node.val >= max_val:
    return False
return (is_valid_bst(node.left, min_val, node.val) and
        is_valid_bst(node.right, node.val, max_val))

# 测试
valid_tree = TreeNode(4,
TreeNode(2, TreeNode(1), TreeNode(3)),
TreeNode(6, TreeNode(5), TreeNode(7)))

invalid_tree = TreeNode(4,
TreeNode(2, TreeNode(1), TreeNode(5)),  # 5 > 4，非法
TreeNode(6))

print(f"valid_tree是BST? {is_valid_bst(valid_tree)}")    # True
print(f"invalid_tree是BST? {is_valid_bst(invalid_tree)}")  # False

---

十一、本章小结

树 = 连通无环图，n个节点n-1条边

二叉树性质：完全二叉树高度 O(log n)，这是树形结构高效的数学基础

堆 = 完全二叉树+堆序性质，支持 O(log n) 插入和 O(1) 取极值

B+树通过高扇出降低树高，1000万记录只需3层 → 数据库索引的核心

Merkle树用哈希的哈希保证数据完整性 → 区块链和数据同步的基础

Trie树共享前缀 → 路由匹配、自动补全

递归是处理树的天然方式：处理根 + 递归处理子树

➡️ 下一页：19-哈希数学

---

上一章	目录	下一章
17-图论基础	数学重学路线图	19-哈希数学