深入研究树算法：从原理到生产实践

1. 引言

树是计算机科学中最基础且最重要的数据结构之一。从文件系统的目录树到数据库的 B+ 树索引，从编译器的语法树到机器学习的决策树——树结构无处不在。

本文将从原理、图示、代码三个维度，深入探讨几种核心树算法，并结合实际生产场景分析它们的应用。

2. 基础二叉树

2.1 什么是二叉树？

二叉树是一种递归定义的数据结构：

要么为空（空树）
要么由一个根节点和两个不相交的子树（左子树和右子树）组成

结构示意：

graph TD
    A((A)):::root --> B((B))
    A --> C((C))
    B --> D((D)):::leaf
    B --> E((E)):::leaf
    C --> F((F)):::leaf
    
    classDef root fill:#e1f5fe,stroke:#01579b,stroke-width:3px
    classDef leaf fill:#c8e6c9,stroke:#2e7d32,stroke-width:2px

🔵 蓝色 = 根节点，🟢 绿色 = 叶子节点

核心概念：

深度：从根到某节点的边数（根节点深度为 0）
高度：从某节点到最远叶子节点的边数
满二叉树：每个内部节点都有两个子节点
完全二叉树：除最后一层外，每层节点都满，且最后一层从左到右填充

2.2 为什么需要不同的遍历方式？

不同遍历顺序对应不同的应用场景：

表达式树示例：(3 + 4) * 5

graph TD
    M((*)):::op --> P((+)):::op
    M --> N5((5)):::num
    P --> N3((3)):::num
    P --> N4((4)):::num
    
    classDef op fill:#ffecb3,stroke:#ff6f00,stroke-width:2px
    classDef num fill:#e3f2fd,stroke:#1565c0,stroke-width:2px

遍历方式	结果	用途
前序遍历	`* + 3 4 5`	前缀表达式（波兰表示法）
中序遍历	`3 + 4 * 5`	中缀表达式（人类可读）
后序遍历	`3 4 + 5 *`	后缀表达式（便于计算）

2.3 遍历算法原理

前序遍历（DFS）：先访问根，再递归访问左子树、右子树

graph TD
    A1((A<br/>①)):::order --> B1((B<br/>②)):::order
    A1 --> C1((C<br/>⑤)):::order
    B1 --> D1((D<br/>③)):::order
    B1 --> E1((E<br/>④)):::order
    C1 --> F1((F<br/>⑥)):::order
    
    classDef order fill:#fff3e0,stroke:#e65100,stroke-width:2px

访问顺序：A → B → D → E → C → F

中序遍历：先递归左子树，再访问根，最后递归右子树

对于 BST，中序遍历得到有序序列：

graph TD
    R4((4)):::bst --> R2((2)):::bst
    R4 --> R8((8)):::bst
    R2 --> R1((1)):::bst
    R8 --> R6((6)):::bst
    R8 --> R10((10)):::bst
    
    classDef bst fill:#e8f5e9,stroke:#1b5e20,stroke-width:2px

中序：1 → 2 → 4 → 6 → 8 → 10（有序！）

2.4 代码实现

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

# 递归实现
def preorder(root):
    """前序：根 → 左 → 右"""
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def inorder(root):
    """中序：左 → 根 → 右"""
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def postorder(root):
    """后序：左 → 右 → 根"""
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

# 迭代实现（使用显式栈）
def preorder_iterative(root):
    result, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right: stack.append(node.right)
        if node.left: stack.append(node.left)
    return result

def inorder_iterative(root):
    """中序遍历迭代版"""
    result, stack = [], []
    curr = root
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        result.append(curr.val)
        curr = curr.right
    return result

复杂度分析：

时间复杂度：O(n)，每个节点访问一次
空间复杂度：O(h)，h 为树高（递归栈或显式栈）

3. 二叉搜索树（BST）

3.1 核心性质

BST 满足以下性质：

左子树所有节点值 < 根节点值
右子树所有节点值 > 根节点值
左右子树也都是 BST

graph TD
    N8((8)):::node --> N3((3)):::node
    N8 --> N10((10)):::node
    N3 --> N1((1)):::node
    N3 --> N6((6)):::node
    N6 --> N4((4)):::node
    N6 --> N7((7)):::node
    N10 --> N14((14)):::node
    N14 --> N13((13)):::node
    
    classDef node fill:#e3f2fd,stroke:#1565c0,stroke-width:2px

✅ 有效 BST：每个节点的左子树都小于它，右子树都大于它

3.2 操作原理

查找操作：从根开始，比目标小往左走，比目标大往右走

graph TD
    A8((8)):::visited --> A3((3)):::visited
    A8 --> A10((10))
    A3 --> A1((1))
    A3 --> A6((6)):::found
    A6 --> A4((4))
    A6 --> A7((7))
    
    classDef visited fill:#fff3e0,stroke:#e65100,stroke-width:2px
    classDef found fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px

查找 6：8 → 3 → 6（3 步）

插入操作流程：

flowchart LR
    A[开始] --> B{与当前节点比较}
    B -->|小于| C{左子节点存在?}
    B -->|大于| D{右子节点存在?}
    C -->|是| E[移到左子节点]
    C -->|否| F[插入左子节点]
    D -->|是| G[移到右子节点]
    D -->|否| H[插入右子节点]
    E --> B
    G --> B
    F --> I[结束]
    H --> I

删除操作三种情况：

flowchart TD
    A[删除节点] --> B{子节点数量}
    B -->|0个| C[直接删除]
    B -->|1个| D[用子节点替换]
    B -->|2个| E[找后继节点替换]
    E --> F[复制后继值]
    F --> G[删除后继节点]

3.3 复杂度分析

操作	平均情况	最坏情况
查找	O(log n)	O(n)
插入	O(log n)	O(n)
删除	O(log n)	O(n)

最坏情况：树退化为链表

graph LR
    A((1)) --> B((2))
    B --> C((3))
    C --> D((4))
    D --> E((5))
    E --> F((6))
    
    style A fill:#ffcdd2,stroke:#c62828
    style B fill:#ffcdd2,stroke:#c62828
    style C fill:#ffcdd2,stroke:#c62828
    style D fill:#ffcdd2,stroke:#c62828
    style E fill:#ffcdd2,stroke:#c62828
    style F fill:#ffcdd2,stroke:#c62828

⚠️ 退化的 BST 查找 6 需要 6 步，复杂度 O(n)

3.4 代码实现

class BST:
    def __init__(self):
        self.root = None
    
    def search(self, val):
        """迭代查找"""
        curr = self.root
        while curr:
            if val == curr.val:
                return curr
            curr = curr.left if val < curr.val else curr.right
        return None
    
    def insert(self, val):
        """迭代插入"""
        if not self.root:
            self.root = TreeNode(val)
            return
        curr = self.root
        while True:
            if val < curr.val:
                if not curr.left:
                    curr.left = TreeNode(val)
                    return
                curr = curr.left
            else:
                if not curr.right:
                    curr.right = TreeNode(val)
                    return
                curr = curr.right
    
    def delete(self, val):
        self.root = self._delete_node(self.root, val)
    
    def _delete_node(self, node, val):
        if not node:
            return None
        if val < node.val:
            node.left = self._delete_node(node.left, val)
        elif val > node.val:
            node.right = self._delete_node(node.right, val)
        else:
            if not node.left:
                return node.right
            if not node.right:
                return node.left
            successor = self._min_node(node.right)
            node.val = successor.val
            node.right = self._delete_node(node.right, successor.val)
        return node
    
    def _min_node(self, node):
        while node.left:
            node = node.left
        return node

4. 平衡二叉搜索树

4.1 为什么需要平衡？

普通 BST 在数据有序时会退化为链表，导致操作效率下降到 O(n)。

平衡树通过旋转操作，保证树的高度始终在 O(log n) 级别。

4.2 AVL 树

平衡因子 = 左子树高度 - 右子树高度

AVL 树要求：|平衡因子| ≤ 1

平衡的 AVL 树：

graph TD
    AV8((8)):::balanced --> AV4((4)):::balanced
    AV8 --> AV12((12)):::balanced
    AV4 --> AV2((2)):::balanced
    AV4 --> AV6((6)):::balanced
    AV12 --> AV14((14)):::balanced
    
    classDef balanced fill:#c8e6c9,stroke:#2e7d32,stroke-width:2px

不平衡的树：

graph TD
    UB8((8)):::unbalanced --> UB4((4)):::unbalanced
    UB4 --> UB2((2)):::unbalanced
    
    classDef unbalanced fill:#ffcdd2,stroke:#c62828,stroke-width:2px

节点 8 的平衡因子 = +2，不平衡！

四种旋转修复：

graph LR
    subgraph LL型[LL型：右旋]
        LL1[Z] --> LL2[Y]
        LL2 --> LL3[X]
    end
    
    subgraph LL结果[结果]
        LR1[Y] --> LR2[X]
        LR1 --> LR3[Z]
    end
    
    LL型 -->|右旋| LL结果

graph LR
    subgraph RR型[RR型：左旋]
        RR1[Z] --> RR2[Y]
        RR2 --> RR3[X]
    end
    
    subgraph RR结果[结果]
        RRr1[Y] --> RRr2[Z]
        RRr1 --> RRr3[X]
    end
    
    RR型 -->|左旋| RR结果

旋转类型判断：

flowchart TD
    A[检测到不平衡] --> B{左子树高还是右子树高}
    B -->|左子树高| C{插入点在左子树的哪边}
    B -->|右子树高| D{插入点在右子树的哪边}
    C -->|左边| E[LL型：右旋]
    C -->|右边| F[LR型：先左旋再右旋]
    D -->|右边| G[RR型：左旋]
    D -->|左边| H[RL型：先右旋再左旋]

4.3 AVL 代码实现

class AVLNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def height(self, node):
        return node.height if node else 0
    
    def balance_factor(self, node):
        return self.height(node.left) - self.height(node.right) if node else 0
    
    def update_height(self, node):
        node.height = 1 + max(self.height(node.left), self.height(node.right))
    
    def rotate_right(self, y):
        """右旋：用于 LL 型"""
        x = y.left
        T2 = x.right
        x.right = y
        y.left = T2
        self.update_height(y)
        self.update_height(x)
        return x
    
    def rotate_left(self, x):
        """左旋：用于 RR 型"""
        y = x.right
        T2 = y.left
        y.left = x
        x.right = T2
        self.update_height(x)
        self.update_height(y)
        return y
    
    def insert(self, node, val):
        if not node:
            return AVLNode(val)
        if val < node.val:
            node.left = self.insert(node.left, val)
        else:
            node.right = self.insert(node.right, val)
        
        self.update_height(node)
        balance = self.balance_factor(node)
        
        # LL 型
        if balance > 1 and val < node.left.val:
            return self.rotate_right(node)
        # RR 型
        if balance < -1 and val > node.right.val:
            return self.rotate_left(node)
        # LR 型
        if balance > 1 and val > node.left.val:
            node.left = self.rotate_left(node.left)
            return self.rotate_right(node)
        # RL 型
        if balance < -1 and val < node.right.val:
            node.right = self.rotate_right(node.right)
            return self.rotate_left(node)
        
        return node

4.4 红黑树简介

红黑树是另一种平衡树，在 Java TreeMap、C++ std::map 中广泛使用。

五条性质：

每个节点是红色或黑色
根节点是黑色
叶子节点（NIL）是黑色
红色节点的子节点必须是黑色（不能连续红）
从任一节点到其叶子的所有路径，黑色节点数量相同

graph TD
    RB10((10)):::black --> RB5((5)):::red
    RB10 --> RB15((15)):::red
    RB5 --> RB3((3)):::black
    RB5 --> RB7((7)):::black
    RB15 --> RB12((12)):::black
    RB15 --> RB20((20)):::black
    
    classDef black fill:#424242,stroke:#212121,stroke-width:2px,color:#fff
    classDef red fill:#ef5350,stroke:#b71c1c,stroke-width:2px,color:#fff

特点：通过颜色规则，保证最长路径不超过最短路径的 2 倍

5. B 树与 B+ 树

5.1 为什么需要 B 树？

BST 的问题是每个节点只存一个值，树很高。对于磁盘存储，每次访问一个节点可能需要一次磁盘 I/O，树越高，I/O 次数越多。

B 树是"矮胖"的多路树，每个节点存储多个键，减少树的高度。

5.2 B 树结构

m 阶 B 树的性质：

每个节点最多 m 个子节点，m-1 个键
根节点至少 2 个子节点
非根非叶节点至少 ⌈m/2⌉ 个子节点
所有叶子节点在同一层

3 阶 B 树示例：

graph TD
    subgraph Level1[根节点]
        ROOT["[30 | 70]"]
    end
    
    subgraph Level2[叶子层]
        L1["[10 | 20]"]
        L2["[50 | 60]"]
        L3["[80 | 90]"]
    end
    
    ROOT --> L1
    ROOT --> L2
    ROOT --> L3
    
    style ROOT fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    style L1 fill:#fff3e0,stroke:#e65100,stroke-width:2px
    style L2 fill:#fff3e0,stroke:#e65100,stroke-width:2px
    style L3 fill:#fff3e0,stroke:#e65100,stroke-width:2px

高度 2，最多存储 3² - 1 = 8 个键

5.3 B+ 树 vs B 树

graph TD
    subgraph B树["B 树（数据在所有节点）"]
        B1["[30 | 70] + 数据"]
        B2["[10] + 数据"]
        B3["[50] + 数据"]
        B4["[80] + 数据"]
        B1 --> B2
        B1 --> B3
        B1 --> B4
    end
    
    subgraph B+树["B+ 树（数据只在叶子）"]
        BP1["[30 | 70] 索引"]
        BP2["[10 | 20] 数据"]
        BP3["[50 | 60] 数据"]
        BP4["[80 | 90] 数据"]
        BP1 --> BP2
        BP1 --> BP3
        BP1 --> BP4
        BP2 <-."链表连接".-> BP3 <-."链表连接".-> BP4
    end

B+ 树优势：

范围查询：只需遍历叶子链表
更多索引：非叶节点不存数据，可存更多索引

5.4 生产场景：MySQL InnoDB

graph LR
    subgraph 性能估算
        A["页大小: 16KB"]
        B["主键: 8字节"]
        C["指针: 6字节"]
        D["每页索引: ~1170"]
        E["3层容量: ~2000万行"]
        F["查询: 最多3次I/O"]
    end
    
    A --> D
    B --> D
    C --> D
    D --> E
    E --> F
    
    style F fill:#c8e6c9,stroke:#2e7d32,stroke-width:2px

6. 字典树（Trie）

6.1 原理

Trie 是专门用于字符串存储和查找的树结构。

核心思想：用边代表字符，从根到某节点的路径代表一个字符串。

graph TD
    ROOT((root)) --> A(a)
    ROOT --> B(b)
    A --> P1(p)
    P1 --> P2(p✓)
    P2 --> L1(l)
    L1 --> E(e✓)
    L1 --> Y(y✓)
    B --> A2(a)
    A2 --> T(t✓)
    A2 --> L2(l)
    L2 --> L3(l✓)
    
    style ROOT fill:#e0e0e0,stroke:#616161
    style P2 fill:#c8e6c9,stroke:#2e7d32
    style E fill:#c8e6c9,stroke:#2e7d32
    style Y fill:#c8e6c9,stroke:#2e7d32
    style T fill:#c8e6c9,stroke:#2e7d32
    style L3 fill:#c8e6c9,stroke:#2e7d32

存储单词：{app✓, apple✓, apply✓, bat✓, ball✓}
✓ = 单词结束标记

查找过程：

flowchart LR
    A["查找 'apple'"] --> B["a → p → p → l → e"]
    B --> C{有结束标记?}
    C -->|是| D["✓ 找到"]
    C -->|否| E["✗ 不存在"]

6.2 复杂度分析

操作	时间复杂度	说明
插入	O(m)	m 为字符串长度
查找	O(m)	m 为字符串长度
前缀匹配	O(m + k)	k 为匹配结果数

与哈希表相比：

✅ Trie 支持前缀查找、按字典序遍历
✅ Trie 不需要处理哈希冲突

6.3 代码实现

class TrieNode:
    def __init__(self):
        self.children = {}  # 字符 → 子节点
        self.is_end = False  # 是否为单词结尾

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        """插入单词：O(m)"""
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def search(self, word):
        """精确查找：O(m)"""
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.is_end
    
    def starts_with(self, prefix):
        """前缀是否存在：O(m)"""
        node = self.root
        for c in prefix:
            if c not in node.children:
                return False
            node = node.children[c]
        return True

6.4 应用：敏感词过滤

flowchart TD
    A[输入文本] --> B[遍历文本]
    B --> C{当前字符在Trie中?}
    C -->|是| D[继续匹配]
    C -->|否| E[保留原字符]
    D --> F{到达单词结尾?}
    F -->|是| G[替换为*]
    F -->|否| C
    G --> B
    E --> B
    B -->|结束| H[输出过滤后文本]

7. 线段树

7.1 原理

线段树用于解决区间问题，支持 O(log n) 的区间查询和单点更新。

核心思想：将区间递归二分，每个节点存储一个区间的聚合值（和、最值等）。

数组 [1, 3, 5, 7, 9, 11] 的线段树：

graph TD
    ROOT["[0-5]: 36"] --> L1["[0-2]: 9"]
    ROOT --> R1["[3-5]: 27"]
    L1 --> L2["[0-1]: 4"]
    L1 --> R2["[2]: 5"]
    R1 --> L3["[3-4]: 16"]
    R1 --> R3["[5]: 11"]
    L2 --> L4["[0]: 1"]
    L2 --> R4["[1]: 3"]
    L3 --> L5["[3]: 7"]
    L3 --> R5["[4]: 9"]
    
    style ROOT fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    style L1 fill:#fff3e0,stroke:#e65100,stroke-width:2px
    style R1 fill:#fff3e0,stroke:#e65100,stroke-width:2px

查询区间 [2, 4] 的和：

graph TD
    ROOT["[0-5]: 36"] --> L1["[0-2]: 9"]
    ROOT --> R1["[3-5]: 27"]
    L1 --> L2["[0-1]: 4"]
    L1 --> R2["[2]: 5"]:::used
    R1 --> L3["[3-4]: 16"]:::used
    R1 --> R3["[5]: 11"]
    
    classDef used fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px

查询结果 = [2]:5 + [3-4]:16 = 21（只需访问 2 个节点！）

7.2 复杂度

操作	时间复杂度	空间复杂度
构建	O(n)	O(4n)
单点更新	O(log n)	-
区间查询	O(log n)	-

7.3 代码实现

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        self._build(data, 0, 0, self.n - 1)
    
    def _build(self, data, node, l, r):
        if l == r:
            self.tree[node] = data[l]
        else:
            mid = (l + r) // 2
            self._build(data, 2*node+1, l, mid)
            self._build(data, 2*node+2, mid+1, r)
            self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]
    
    def query(self, ql, qr):
        return self._query(0, 0, self.n-1, ql, qr)
    
    def _query(self, node, l, r, ql, qr):
        if qr < l or ql > r:
            return 0
        if ql <= l and r <= qr:
            return self.tree[node]
        mid = (l + r) // 2
        return self._query(2*node+1, l, mid, ql, qr) + \
               self._query(2*node+2, mid+1, r, ql, qr)

8. 决策树

8.1 原理

决策树通过递归选择最优特征进行分裂，将数据划分成越来越"纯"的子集。

贷款审批决策树：

graph TD
    A["收入?"] -->|<5万| B["负债?"]
    A -->|≥5万| C["信用?"]
    B -->|高| D["❌ 拒绝"]:::reject
    B -->|低| E["✓ 通过"]:::approve
    C -->|差| F["❌ 拒绝"]:::reject
    C -->|好| G["✓ 通过"]:::approve
    
    classDef reject fill:#ffcdd2,stroke:#c62828,stroke-width:2px
    classDef approve fill:#c8e6c9,stroke:#2e7d32,stroke-width:2px
    
    style A fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    style B fill:#fff3e0,stroke:#e65100,stroke-width:2px
    style C fill:#fff3e0,stroke:#e65100,stroke-width:2px

8.2 信息熵与信息增益

graph LR
    subgraph 信息熵
        E1["[是,是,是,是]<br/>熵 = 0<br/>(完全确定)"]:::certain
        E2["[是,是,否,否]<br/>熵 = 1<br/>(最不确定)"]:::uncertain
    end
    
    classDef certain fill:#c8e6c9,stroke:#2e7d32
    classDef uncertain fill:#ffcdd2,stroke:#c62828

信息增益计算：

信息增益 = 父节点熵 - Σ(子节点权重 × 子节点熵)

选择信息增益最大的特征进行分裂

9. 如何选择树结构

graph TD
    START["选择树结构"] --> Q1{存储位置?}
    Q1 -->|内存| Q2{需要范围查询?}
    Q1 -->|磁盘| Q3{需要范围查询?}
    
    Q2 -->|是| RB["红黑树<br/>O(log n)"]
    Q2 -->|否| HT["哈希表"]
    
    Q3 -->|是| BPT["B+ 树<br/>O(log n)"]
    Q3 -->|否| LSM["LSM Tree"]
    
    START --> Q4{特殊需求?}
    Q4 -->|字符串前缀| TRIE["Trie<br/>O(m)"]
    Q4 -->|区间查询| SEG["线段树<br/>O(log n)"]
    Q4 -->|分类任务| DT["决策树<br/>O(n log n)"]
    
    style RB fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    style BPT fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    style TRIE fill:#c8e6c9,stroke:#2e7d32,stroke-width:2px
    style SEG fill:#fff3e0,stroke:#e65100,stroke-width:2px
    style DT fill:#f3e5f5,stroke:#7b1fa2,stroke-width:2px

需求	推荐结构	时间复杂度	典型应用
内存键值存储	红黑树	O(log n)	Java TreeMap, C++ std::map
磁盘持久化	B+ 树	O(log n)	MySQL InnoDB, PostgreSQL
字符串前缀匹配	Trie	O(m)	搜索提示、敏感词过滤
区间聚合查询	线段树	O(log n)	实时监控、游戏排行榜
分类/回归任务	XGBoost/LightGBM	O(n log n)	风控系统、推荐系统

工程优化建议

内存对齐：树节点大小应对齐到缓存行（64 字节）
内存池：高频分配场景使用预分配池
批量操作：B+ 树批量插入时先排序再构建
并发控制：读多写少用 Copy-on-Write，写多用细粒度锁

10. 总结

树算法是计算机科学的核心基础设施：

mindmap
  root((树算法应用))
    操作系统
      进程调度 红黑树
      内存管理
    数据库
      索引结构 B+树
      查询优化
    编译器
      语法分析 AST
      代码生成
    机器学习
      特征选择 决策树
      模型构建
    搜索系统
      自动补全 Trie
      全文检索

深入理解树的原理和实现，是构建高性能系统的必备能力。

参考资料

Cormen, T. H. et al. Introduction to Algorithms, 4th Edition
MySQL 8.0 Reference Manual - InnoDB Storage Engine
LightGBM: A Highly Efficient Gradient Boosting Decision Tree
Linux Kernel Documentation - Red-Black Trees
Database System Concepts - Silberschatz et al.

深入研究树算法：从原理到生产实践#

1. 引言#

2. 基础二叉树#

2.1 什么是二叉树？#

2.2 为什么需要不同的遍历方式？#

2.3 遍历算法原理#

2.4 代码实现#

3. 二叉搜索树（BST）#

3.1 核心性质#

3.2 操作原理#

3.3 复杂度分析#

3.4 代码实现#

4. 平衡二叉搜索树#

4.1 为什么需要平衡？#

4.2 AVL 树#

4.3 AVL 代码实现#

4.4 红黑树简介#

5. B 树与 B+ 树#

5.1 为什么需要 B 树？#

5.2 B 树结构#

5.3 B+ 树 vs B 树#

5.4 生产场景：MySQL InnoDB#

6. 字典树（Trie）#

6.1 原理#

6.2 复杂度分析#

6.3 代码实现#

6.4 应用：敏感词过滤#

7. 线段树#

7.1 原理#

7.2 复杂度#

7.3 代码实现#

8. 决策树#

8.1 原理#

8.2 信息熵与信息增益#

9. 如何选择树结构#

工程优化建议#

10. 总结#

参考资料#