1. 树的基本概念
1.1 术语定义
A ← 根节点（Root）
/|\
B C D ← B、C、D 是 A 的子节点
/| |
E F G ← 叶子节点（无子节点）
A 的深度：0（层数从 0 开始）
树的度：3（最大子节点数）
高度：3（最深路径的节点数）
| 术语 | 定义 |
|---|---|
| 度 | 节点拥有的子节点数 |
| 深度 | 根到该节点的边数 |
| 高度 | 该节点到最远叶子的边数 |
| 满二叉树 | 每层节点数达到最大值 |
| 完全二叉树 | 除最后一层外满，最后一层左对齐 |
2. 二叉树遍历
2.1 四种遍历方式
class TreeNode:
def __init__(self, val=0):
self.val = val
self.left = None
self.right = None
# 前序遍历：根 → 左 → 右
def pre_order(root):
if not root:
return
print(root.val, end=' ')
pre_order(root.left)
pre_order(root.right)
# 中序遍历：左 → 根 → 右（BST 中得到有序序列）
def in_order(root):
if not root:
return
in_order(root.left)
print(root.val, end=' ')
in_order(root.right)
# 后序遍历：左 → 右 → 根
def post_order(root):
if not root:
return
post_order(root.left)
post_order(root.right)
print(root.val, end=' ')
# 层序遍历（BFS）
def level_order(root):
if not root:
return
from collections import deque
q = deque([root])
while q:
node = q.popleft()
print(node.val, end=' ')
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
2.2 迭代实现
# 非递归中序遍历（栈）
def in_order_iter(root):
stack = []
result = []
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
3. 二叉搜索树（BST）
3.1 定义
左子树所有节点 < 根 < 右子树所有节点。
class BST:
def __init__(self):
self.root = None
def insert(self, val):
self.root = self._insert(self.root, val)
def _insert(self, node, val):
if not node:
return TreeNode(val)
if val < node.val:
node.left = self._insert(node.left, val)
elif val > node.val:
node.right = self._insert(node.right, val)
return node
def search(self, val):
return self._search(self.root, val)
def _search(self, node, val):
if not node or node.val == val:
return node
return self._search(node.left if val < node.val else node.right, val)
def delete(self, val):
self.root = self._delete(self.root, val)
def _delete(self, node, val):
if not node:
return None
if val < node.val:
node.left = self._delete(node.left, val)
elif val > node.val:
node.right = self._delete(node.right, val)
else:
# 找到要删除的节点
if not node.left:
return node.right
if not node.right:
return node.left
# 有两个子节点：找后继（右子树最小值）
min_node = self._find_min(node.right)
node.val = min_node.val
node.right = self._delete(node.right, min_node.val)
return node
def _find_min(self, node):
while node.left:
node = node.left
return node
3.2 BST 的问题
退化为链表时，操作退化为 O(n)：
退化的 BST (插入 1,2,3,4,5):
1
\
2
\
3
\
4
\
5
需要自平衡树来解决！
4. AVL 树（严格平衡 BST）
4.1 平衡因子
平衡因子 = 左子树高度 - 右子树高度，绝对值 ≤ 1
4.2 四种旋转
LL（左左）：右旋
z y
/ / \
y → x z
/
x
RR（右右）：左旋
z y
\ / \
y → z x
\
x
LR（左右）：先左旋再右旋
RL（右左）：先右旋再左旋
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(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):
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):
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)
elif val > node.val:
node.right = self.insert(node.right, val)
else:
return node
self._update_height(node)
balance = self._balance(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
AVL 树保证严格平衡，查找 O(log n)，但插入/删除旋转次数较多。
5. 红黑树（实用平衡 BST）
5.1 五条性质
| # | 性质 |
|---|---|
| 1 | 节点是红色或黑色 |
| 2 | 根是黑色 |
| 3 | 所有叶子（NIL）是黑色 |
| 4 | 红色节点的子节点必须是黑色 |
| 5 | 从任一节点到其叶子的所有路径包含相同数目的黑色节点 |
Java
TreeMap、C++std::map、Linux 内核调度器均使用红黑树。
5.2 与 AVL 对比
| 特性 | AVL 树 | 红黑树 |
|---|---|---|
| 平衡严格度 | 严格 | 宽松（最长路径 ≤ 2×最短） |
| 查找 | 略快 | 略慢（但差距很小） |
| 插入旋转 | 最多 2 次 | 最多 2 次 |
| 删除旋转 | 最多 O(log n) | 最多 3 次 |
| 适用场景 | 读多写少 | 读写均衡 |
6. B 树与 B+ 树
6.1 为什么需要多路查找树
磁盘 I/O 是数据库的瓶颈。二叉树节点数多、高度高，导致磁盘访问次数多。
6.2 B 树（B-Tree）
m 阶 B 树定义：
- 每个节点最多 m 个子节点
- 除根外，每个节点至少 ⌈m/2⌉ 个子节点
- 所有叶子在同一层
[20, 50]
/ | \
[5,10] [30,40] [60,70,80]
6.3 B+ 树（数据库索引首选）
| 特性 | B 树 | B+ 树 |
|---|---|---|
| 数据存储 | 内部节点和叶子 | 仅在叶子 |
| 叶子节点 | 相互独立 | 形成有序链表 |
| 范围查询 | 需要中序遍历 | 顺序扫描叶子 |
| 命中点 | 可能在内部节点 | 总是到叶子 |
| 空间利用率 | 较低 | 更高 |
B+ 树结构：
[20, 50] ← 内部节点只存键，不存数据
/ | \
[5,10,15]→[20,30,40]→[50,60,70,80]→NULL
数据 数据 数据
叶子节点通过指针连接，支持高效范围查询
MySQL InnoDB 主键索引、文件系统（Ext4/XFS）均使用 B+ 树。
7. 树的应用场景总结
| 结构 | 典型应用 |
|---|---|
| 普通二叉树 | 表达式解析、哈夫曼编码 |
| BST | 小型有序数据集合 |
| AVL | 内存中读多写少的索引 |
| 红黑树 | TreeMap、进程调度、内存管理 |
| B+ 树 | 数据库索引、文件系统 |
| Trie（字典树） | 搜索引擎自动补全、IP 路由前缀匹配 |
| 线段树 | 区间查询、区间更新 |
| 树状数组（Fenwick） | 前缀和、点更新 |
参考文章
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。