树
Data Structures - Trees
系统地介绍几个常见的树结构，包括它们的特点、应用场景，以及常见开源实现里用到的地方。
🌳 常见树结构介绍
| 树结构 | 特点 | 应用场景 | 开源实现示例 |
|---|---|---|---|
| 二叉树 (Binary Tree) | 每个节点最多 2 个子节点（左、右），最基础的树结构 | 表达式树、层次化数据表示 | 数据结构课程中的基础实现 |
| 二叉搜索树 BST (Binary Search Tree) | 左子树所有值 < 节点值 < 右子树所有值 | 有序数据存储、查找（平均 O(log n)） | STL map (C++) 的早期实现 |
| 平衡二叉树 (AVL Tree) | 任意节点左右子树高度差 ≤ 1，严格平衡 | 查找、插入、删除都保持 O(log n) | 早期数据库/内存索引实现 |
| 红黑树 (Red-Black Tree) | 近似平衡二叉树，节点红/黑染色，保持平衡 | 插入/删除高效（比 AVL 插入更快） | Java TreeMap、C++ STL map/set、Linux 内核调度器 |
| B 树 (B-Tree) | 多路平衡搜索树，节点可存多个 key，常用于磁盘/数据库 | 数据库索引、文件系统 | MySQL MyISAM、Postgres 索引 |
| B+ 树 (B+Tree) | B 树改进，数据存储在叶子节点，叶子链表相连，范围查询高效 | 关系型数据库主流索引结构 | MySQL InnoDB、Postgres |
| Trie (前缀树) | 基于字符串前缀的多叉树 | 自动补全、搜索提示、字典存储 | Redis SETNX 实现的自动补全、搜索引擎分词 |
| Heap (堆，常见二叉堆) | 完全二叉树，父节点 ≤ 子节点（最小堆）或 ≥ 子节点（最大堆） | 优先队列、top-k | C++ priority_queue、任务调度系统 |
| Segment Tree (线段树) | 区间划分，支持区间查询与修改 | 范围和/最大值/最小值查询 | 算法竞赛、图形学渲染 |
| Fenwick Tree (Binary Indexed Tree, 树状数组) | 用数组模拟树，支持区间和查询与更新，空间更省 | 动态前缀和 | 算法竞赛、在线统计 |
| Suffix Tree (后缀树) | 存储字符串所有后缀，支持快速模式匹配 | 字符串搜索、基因序列匹配 | 生物信息学软件 |
| KD-Tree | 多维空间划分树 | 最近邻查询、空间索引 | 计算机图形学、机器学习（kNN） |
| Merkle Tree | 每个节点是子节点哈希，叶子存数据哈希 | 数据完整性验证、区块链 | Bitcoin、Ethereum |
📌 重点说明几个最常用的
1. 红黑树 (Red-Black Tree)
- 平衡二叉搜索树的一种。
- 相比 AVL 更快地插入/删除（因为它“近似”平衡，不追求完全平衡）。
- 保证查找、插入、删除在 O(log n)。
- 应用：Linux 内核调度器、C++ STL
map/set、JavaTreeMap/TreeSet。
2. B 树 / B+ 树
- 专为磁盘/数据库设计的多路平衡搜索树。
- 一个节点可以存多个 key，减少磁盘 IO。
- B+ 树在叶子节点存所有数据，并通过链表连接，范围查询效率极高。
- 应用：几乎所有关系型数据库的索引（MySQL InnoDB，Postgres）。
3. Trie (前缀树)
- 基于字符前缀构建树，适合字符串搜索。
- 常用于搜索引擎自动补全、拼写检查。
- 应用：Elasticsearch/Lucene 分词、Redis 自动补全。
4. 堆 (Heap)
- 用完全二叉树实现，常见的是二叉堆。
- 最常用于优先队列，支持快速取最小/最大值。
- 应用：任务调度、Dijkstra 最短路径算法、top-k 问题。
5. Merkle Tree
- 树的每个节点保存子节点的哈希，叶子存原始数据的哈希。
- 通过根哈希，可以快速验证大数据集完整性。
- 应用：区块链、分布式存储（IPFS、Git 对象存储）。
👉 这样你能把树结构分成三类：
- 平衡搜索类（红黑树、AVL、B 树、B+ 树） → 查询、索引。
- 前缀/特殊功能类（Trie、Suffix Tree、KD-Tree） → 字符串/空间/多维。
- 特殊验证类（Merkle Tree） → 分布式/安全性。