树结构是数据结构里的"主力军" —— 文件系统、组织架构、解析树、数据库索引、决策树都是树。但很多人对树的认识停在"二叉树前/中/后序遍历"。实际工程里用得最多的是 BST、AVL、B+ 树、Trie、跳表 等。这篇文章把树家族讲透,所有结构都配代码和应用场景。
二叉搜索树(BST)
每个节点的值大于左子树所有值,小于右子树所有值。这让查找、插入、删除都是 O(log n)(平均)。
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
class BST {
constructor() { this.root = null; }
insert(val) {
this.root = this._insert(this.root, val);
}
_insert(node, val) {
if (!node) return new TreeNode(val);
if (val < node.val) node.left = this._insert(node.left, val);
else node.right = this._insert(node.right, val);
return node;
}
search(val) {
let node = this.root;
while (node) {
if (val === node.val) return node;
node = val < node.val ? node.left : node.right;
}
return null;
}
}BST 的致命问题:顺序插入会退化成链表。1→2→3→4 顺次插入,树就是单链,操作变 O(n)。所以工程里用自平衡 BST:AVL、红黑树等。
AVL 树
1962 年第一个自平衡 BST。规则:每个节点的左右子树高度差 ≤ 1。失衡时通过 4 种旋转(LL、RR、LR、RL)恢复。
AVL 严格平衡 —— 查询性能最好。但代价是插入 / 删除时频繁旋转,写入性能不如红黑树。读多写少场景适合。
红黑树
1972 年提出,平衡条件比 AVL 松(最长路径 ≤ 2 倍最短路径)。插入 / 删除最多 3 次旋转,写性能好。
Java TreeMap / HashMap(链表过长转树)、C++ STL map / set、Linux 调度器、Nginx 定时器全用红黑树。
B+ 树
数据库索引的标准。和二叉树不同:
- 多叉(一个节点几百个 key),树矮(几亿数据树高也就 4-5 层)。
- 非叶节点不存数据,只存索引。
- 叶节点存数据,且用链表串起来(支持顺序扫描)。
MySQL InnoDB、PostgreSQL、SQLite、文件系统(NTFS / Ext4)都用 B+ 树。详细见之前 SQL 索引那篇文章。
Trie(字典树/前缀树)
专门为字符串设计。每个节点代表一个字符,从根到某节点的路径就是一个前缀。
class Trie {
constructor() { this.root = {}; }
insert(word) {
let node = this.root;
for (const ch of word) {
if (!node[ch]) node[ch] = {};
node = node[ch];
}
node.end = true;
}
search(word) {
let node = this.root;
for (const ch of word) {
if (!node[ch]) return false;
node = node[ch];
}
return node.end === true;
}
startsWith(prefix) {
let node = this.root;
for (const ch of prefix) {
if (!node[ch]) return false;
node = node[ch];
}
return true;
}
}
const trie = new Trie();
trie.insert('apple');
trie.insert('app');
trie.startsWith('app'); // true应用:自动补全(输入"kub"提示"kubernetes"、"kubectl")、敏感词过滤、IP 路由查找(把 IP 当二进制串)、编辑器关键词高亮。Aho-Corasick 算法基于 Trie 做多模式匹配,nginx / Snort 都用。
跳表(Skip List)
1989 年提出,概率型数据结构。本质是"多层链表",每一层是下一层的"快速通道"。
Level 3: 1 -----------------> 9
Level 2: 1 -----> 5 -------> 9
Level 1: 1 -> 3 -> 5 -> 7 -> 9
查 7:从 Level 3 开始
Level 3:1 next is 9 (>7),下层
Level 2:1 next is 5 (<7),前进
5 next is 9 (>7),下层
Level 1:5 next is 7 (=7),找到跳表的好处:
- 实现比平衡树简单得多。
- 支持范围查询(顺着 Level 1 扫)。
- 并发友好(局部修改影响小)。
Redis 的 Sorted Set 用跳表(而不是红黑树),作者解释:实现简单 + 范围查询好做 + 并发性更好。LevelDB / RocksDB 的 MemTable 也用跳表。
线段树(Segment Tree)
专门处理"区间"问题:区间求和、区间最大值、区间修改。
// 区间求和 + 单点修改的线段树
class SegmentTree {
constructor(arr) {
this.n = arr.length;
this.tree = new Array(4 * this.n).fill(0);
this._build(arr, 0, 0, this.n - 1);
}
_build(arr, node, start, end) {
if (start === end) { this.tree[node] = arr[start]; return; }
const mid = (start + end) >> 1;
this._build(arr, 2*node+1, start, mid);
this._build(arr, 2*node+2, mid+1, end);
this.tree[node] = this.tree[2*node+1] + this.tree[2*node+2];
}
update(idx, val) {
this._update(0, 0, this.n-1, idx, val);
}
_update(node, start, end, idx, val) {
if (start === end) { this.tree[node] = val; return; }
const mid = (start + end) >> 1;
if (idx <= mid) this._update(2*node+1, start, mid, idx, val);
else this._update(2*node+2, mid+1, end, idx, val);
this.tree[node] = this.tree[2*node+1] + this.tree[2*node+2];
}
query(l, r) { return this._query(0, 0, this.n-1, l, r); }
_query(node, start, end, l, r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return this.tree[node];
const mid = (start + end) >> 1;
return this._query(2*node+1, start, mid, l, r) + this._query(2*node+2, mid+1, end, l, r);
}
}所有"区间"类查询(求和、最值、GCD)都能用线段树 O(log n) 处理。游戏服务器算"排行榜某段排名"、传感器系统"某段时间的最大值"都用它。
树状数组(Fenwick Tree / BIT)
比线段树更简单的"区间求和 + 单点修改"结构。占空间 O(n),代码不到 30 行。
class BIT {
constructor(n) { this.tree = new Array(n + 1).fill(0); }
update(i, delta) {
for (; i < this.tree.length; i += i & -i) this.tree[i] += delta;
}
sum(i) {
let s = 0;
for (; i > 0; i -= i & -i) s += this.tree[i];
return s;
}
rangeSum(l, r) { return this.sum(r) - this.sum(l - 1); }
}BIT 用低位运算实现树形结构,代码量少且常数小。适合区间求和 / 频次统计的简单场景。
并查集(Union-Find / DSU)
处理"动态连通性" —— 给一堆点,支持"合并两个集合"和"查询两个点是否同集合"。
class UnionFind {
constructor(n) {
this.parent = Array.from({length: n}, (_, i) => i);
this.rank = new Array(n).fill(0);
}
find(x) {
if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]); // 路径压缩
return this.parent[x];
}
union(x, y) {
const rx = this.find(x), ry = this.find(y);
if (rx === ry) return false;
// 按 rank 合并:小的接到大的下面
if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry;
else if (this.rank[rx] > this.rank[ry]) this.parent[ry] = rx;
else { this.parent[ry] = rx; this.rank[rx]++; }
return true;
}
}应用:Kruskal 求最小生成树、社交网络好友圈分析、岛屿数量、判断图是否有环。每次操作摊还接近 O(1)。
实战:LRU Cache
哈希表 + 双向链表的组合(不是树,但常一起考):
class LRUCache {
constructor(capacity) {
this.cap = capacity;
this.map = new Map(); // JS Map 保留插入顺序
}
get(key) {
if (!this.map.has(key)) return -1;
const val = this.map.get(key);
this.map.delete(key);
this.map.set(key, val); // 重插到末尾(最近用)
return val;
}
put(key, val) {
if (this.map.has(key)) this.map.delete(key);
else if (this.map.size >= this.cap) {
this.map.delete(this.map.keys().next().value); // 删最久没用
}
this.map.set(key, val);
}
}选型经验
需求 首选
内存有序集合 红黑树 / 跳表
按 key 范围查询 B+ 树(磁盘)/ 跳表(内存)
前缀匹配 Trie
区间查询 + 单点修改 线段树 / 树状数组
动态连通性 并查集
缓存 哈希 + 双向链表(LRU)
排行榜 跳表 / 红黑树 + 哈希写在最后
树结构是程序员的"基础内功",看似学校里学过,真到工程实战才发现"该用哪个"的判断比"会写哪个"重要得多。理解每种树的性能特点和适用场景,你才能在系统设计时一眼选对工具。
一图看懂
树结构演进一图看懂:
—— 别看了 · 2026