数据结构-树与堆
一句话概括
树把线性结构的「一对一」升级为「一对多」,从而把查找从 降到 :二叉搜索树(BST)靠有序性查找但会退化成链表,AVL 用旋转强制平衡,红黑树用较少旋转换工程可控性,B+ 树把「高瘦」的二叉树压成「矮胖」的多叉树以减少磁盘 I/O;堆则是完全二叉树的数组实现,用上浮下沉维护偏序,支撑优先队列、堆排序与 Top-K。
读完本文你将能:手写四种遍历(递归 + 非递归)、由两种遍历序列还原二叉树、实现 BST 的增删查与 AVL 四种旋转、写堆排序与 Top-K,并讲清「数据库为什么用 B+ 树」「STL 为什么选红黑树」。
一、树的术语
树是 个节点的有限集合, 时为空树,否则有唯一的根(Root),其余节点分成若干互不相交的子树。
| 术语 | 含义 | 示例(下文示例树) |
|---|---|---|
| 根(Root) | 唯一没有父节点的节点 | A |
| 叶(Leaf) | 没有子节点的节点 | D、E、F |
| 父/子(Parent/Child) | 直接前驱/后继 | A 是 B、C 的父节点 |
| 兄弟(Sibling) | 同一父节点的节点 | B 与 C |
| 度(Degree) | 节点拥有的子树个数 | A 的度为 2,D 的度为 0 |
| 树的度 | 所有节点度的最大值 | 2 |
| 层次(Level) | 根为第 1 层,向下递增 | A 第 1 层,B/C 第 2 层 |
| 深度(Depth) | 从根到该节点的边数或节点数 | 常见两种约定,见下 |
| 高度(Height) | 从该节点到最远叶子的边数 | 叶子高度为 0 |
| 路径长度 | 路径上边的条数 | A→D 长度为 2 |
| 森林(Forest) | 若干互不相交的树 | 去掉根 A 后得到 2 棵树 |
深度与高度有两套约定,读代码前先对齐
约定一(边数):根深度 0,叶子高度 0,本文采用这套,AVL 平衡因子计算最简洁。
约定二(节点数):根深度 1(= 层数),空树高度 0。
LeetCode 多数题目用「节点数」定义高度(空节点高度 0,叶子高度 1)。两套约定算出的数值差 1,混用会导致平衡因子判断反向,是最隐蔽的 bug 来源之一。
示例树结构:
A <- 根,度 2,深度 0
/ \
B C <- 深度 1
/ \ \
D E F <- 叶,深度 2,高度 0
二、二叉树(Binary Tree)与重要性质
二叉树每个节点至多两个孩子,且左右孩子有顺序(左子树与右子树不能交换)。
2.1 性质一:第 层最多 个节点
根(第 1 层)有 个,每下一层每个节点最多分叉 2 个,故第 层最多 个。满二叉树(Full/Perfect Binary Tree) 每层都取到上限。
2.2 性质二:高度为 的二叉树最多 个节点
反过来, 个节点的二叉树最小高度为 (边数约定),这正是平衡树查找代价 的来源。
2.3 性质三: 的推导
记 分别为度为 0、1、2 的节点数。
从节点总数出发:
从边数出发:除根以外,每个节点都恰好有一条来自父节点的边,所以边数 。另一方面,每条边都由一个非叶节点发出,度为 1 的节点发出 1 条,度为 2 的发出 2 条:
把 (1) 代入 :
两边消去 与 :
这个结论的用途
看到「一棵二叉树有 10 个度为 2 的节点」,立刻能推出叶子数为 11、总节点数至少 21( 最小时为 0)。这是选择题与代码校验(例如哈夫曼树节点总数 )中的高频结论。
2.4 完全二叉树的特殊性质
完全二叉树(Complete Binary Tree):除最后一层外每层都满,且最后一层的节点从左到右连续排列(中间不能有空缺)。它的价值在于可以用数组零浪费存储。
对下标从 0 开始的数组表示(i 是数组下标):
| 关系 | 公式 |
|---|---|
| 父节点 | (i - 1) // 2( 时无父) |
| 左孩子 | 2 * i + 1 |
| 右孩子 | 2 * i + 2 |
| 是否为叶 | 2 * i + 1 >= n |
| 最后一个非叶节点 | n // 2 - 1 |
若下标从 1 开始,关系更简洁:父为 i // 2,左孩子 2i,右孩子 2i + 1。这就是堆的下标基础。
三、二叉树的存储方式
3.1 链式存储
class TreeNode:
"""二叉树节点:左右指针 + 值。"""
__slots__ = ("val", "left", "right")
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_sample_tree():
"""手工构建示例树:
1
/ \\
2 3
/ \\ \\
4 5 6
"""
root = TreeNode(1)
root.left = TreeNode(2, TreeNode(4), TreeNode(5))
root.right = TreeNode(3, None, TreeNode(6))
return root
带空指针标记的链表(线索化/序列化常用):用 None 表示空,可以把任意二叉树唯一序列化。
3.2 数组存储
- 完全二叉树:直接用上面的下标公式,零空间浪费。
- 一般二叉树:把空位也占上(用
None填充),最坏情况是右斜树, 个节点需要 个槽位,空间爆炸。所以一般二叉树不用数组存,这是「完全二叉树」在堆中地位特殊的原因。
def tree_to_array(root):
"""把二叉树按完全二叉树编号填入数组,空位用 None 占位(仅演示,稀疏时极浪费)。"""
if root is None:
return []
res = []
queue = [root] # 层序 BFS
while queue:
node = queue.pop(0)
if node is None:
res.append(None)
continue
res.append(node.val)
queue.append(node.left) # 空孩子也入队,保证下标关系成立
queue.append(node.right)
while res and res[-1] is None: # 去掉尾部冗余 None,便于阅读
res.pop()
return res
print(tree_to_array(build_sample_tree())) # [1, 2, 3, 4, 5, None, 6]
四、四种遍历
约定:前/中/后指的是根节点被访问的时机——前序(根左右)、中序(左根右)、后序(左右根);层序按层从上到下、从左到右。
4.1 递归实现
def preorder(root, out=None):
"""前序:根 -> 左 -> 右。"""
if out is None:
out = []
if root:
out.append(root.val)
preorder(root.left, out)
preorder(root.right, out)
return out
def inorder(root, out=None):
"""中序:左 -> 根 -> 右。BST 的中序是升序序列。"""
if out is None:
out = []
if root:
inorder(root.left, out)
out.append(root.val)
inorder(root.right, out)
return out
def postorder(root, out=None):
"""后序:左 -> 右 -> 根。适合自底向上计算(如求高度、释放内存)。"""
if out is None:
out = []
if root:
postorder(root.left, out)
postorder(root.right, out)
out.append(root.val)
return out
4.2 非递归实现(显式栈)
递归的本质是用系统调用栈保存现场,非递归就是自己维护这个栈。原因:递归深度大时会栈溢出;显式栈还可以中途暂停、恢复。
def preorder_iter(root):
"""前序非递归:栈中弹出即访问,再压右、压左(保证左先出)。"""
res, stack = [], [root] if root else []
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right) # 右孩子先入栈 -> 后访问
if node.left:
stack.append(node.left)
return res
def inorder_iter(root):
"""中序非递归:一路向左压栈,弹栈时访问,然后转向右子树。"""
res, stack, cur = [], [], root
while cur or stack:
while cur: # 走到最左
stack.append(cur)
cur = cur.left
cur = stack.pop() # 弹出即「左子树已处理完」的节点
res.append(cur.val)
cur = cur.right # 转向右子树
return res
def postorder_iter(root):
"""后序非递归(巧妙法):按「根-右-左」前序遍历,最后整体反转得「左-右-根」。"""
res, stack = [], [root] if root else []
while stack:
node = stack.pop()
res.append(node.val)
if node.left:
stack.append(node.left) # 左先入栈 -> 后出 -> 变体顺序为 根右左
if node.right:
stack.append(node.right)
return res[::-1] # 反转得到后序
def levelorder(root):
"""层序遍历:BFS,按层分组返回。"""
if root is None:
return []
res, queue = [], [root]
while queue:
level_vals, next_level = [], []
for node in queue: # 逐个处理当前层,同时收集下一层
level_vals.append(node.val)
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
res.append(level_vals)
queue = next_level
return res
if __name__ == "__main__":
root = build_sample_tree()
assert preorder(root) == preorder_iter(root) == [1, 2, 4, 5, 3, 6]
assert inorder(root) == inorder_iter(root) == [4, 2, 5, 1, 3, 6]
assert postorder(root) == postorder_iter(root) == [4, 5, 2, 6, 3, 1]
assert levelorder(root) == [[1], [2, 3], [4, 5, 6]]
print("四种遍历递归/非递归结果一致")
4.3 遍历复杂度
| 遍历 | 时间 | 空间(栈/队列深度) | 空间(最坏) |
|---|---|---|---|
| 前/中/后序递归 | (斜树) | ||
| 前/中/后序非递归 | |||
| 层序 | , 为最大宽度 | ||
| Morris 遍历 | (利用叶子空指针做线索) |
五、由遍历序列还原二叉树
核心结论:
- 前序 + 中序、后序 + 中序 可以唯一确定一棵二叉树。
- 前序 + 后序 一般不能唯一确定(无法区分只有一个孩子时它是左还是右)。
- 只知道一种遍历更不能确定。
还原思路(前序 + 中序):前序的第一个元素是根;在中序里找到根的位置,左边就是左子树的中序、右边是右子树的中序;由左子树节点个数,可在前序中切出左子树的前序;递归即可。
例题:前序
[3, 9, 20, 15, 7],中序[9, 3, 15, 20, 7]第 1 步:前序首元素
3是根。中序中3的位置在索引 1,所以左子树中序 =[9](1 个节点),右子树中序 =[15, 20, 7](3 个节点)。第 2 步:前序按左子树 1 个节点切分:左子树前序 =
[9],右子树前序 =[20, 15, 7]。第 3 步:左子树由
[9]与[9]确定,仅一个节点9。第 4 步:右子树根为
20;中序[15, 20, 7]中20在索引 1,左子中序[15]、右子中序[7],对应前序[15]与[7]。结果:
```
3
/ \
9 20
/ \
15 7
```
验证:后序遍历该树得到
[9, 15, 7, 20, 3]。
def build_from_pre_in(preorder, inorder):
"""由前序 + 中序还原二叉树。用哈希表定位根,整体 O(n)。"""
if not preorder:
return None
idx = {v: i for i, v in enumerate(inorder)} # 值不重复时可用;O(1) 定位根
def helper(pre_lo, pre_hi, in_lo, in_hi):
if pre_lo > pre_hi:
return None
root_val = preorder[pre_lo]
mid = idx[root_val]
left_size = mid - in_lo # 左子树节点个数
root = TreeNode(root_val)
# 前序区间:根之后 left_size 个属于左子树
root.left = helper(pre_lo + 1, pre_lo + left_size, in_lo, mid - 1)
root.right = helper(pre_lo + left_size + 1, pre_hi, mid + 1, in_hi)
return root
return helper(0, len(preorder) - 1, 0, len(inorder) - 1)
def build_from_post_in(postorder, inorder):
"""由后序 + 中序还原:后序的最后一个元素是根。"""
if not postorder:
return None
idx = {v: i for i, v in enumerate(inorder)}
def helper(post_lo, post_hi, in_lo, in_hi):
if post_lo > post_hi:
return None
root_val = postorder[post_hi]
mid = idx[root_val]
left_size = mid - in_lo
root = TreeNode(root_val)
root.left = helper(post_lo, post_lo + left_size - 1, in_lo, mid - 1)
root.right = helper(post_lo + left_size, post_hi - 1, mid + 1, in_hi)
return root
return helper(0, len(postorder) - 1, 0, len(inorder) - 1)
if __name__ == "__main__":
t = build_from_pre_in([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])
assert preorder(t) == [3, 9, 20, 15, 7]
assert inorder(t) == [9, 3, 15, 20, 7]
t2 = build_from_post_in([9, 15, 7, 20, 3], [9, 3, 15, 20, 7])
assert postorder(t2) == [9, 15, 7, 20, 3]
print("遍历序列还原测试通过")
六、二叉搜索树(Binary Search Tree, BST)
定义:对任意节点,其左子树所有值 < 根值 < 右子树所有值。这一定义带来中序遍历严格升序的性质。
6.1 查找、插入、删除(含删除的三种情况)
删除是 BST 最难的环节,分三种情况:
- 删除叶子:直接摘掉,父节点对应指针置
None。 - 删除只有一个孩子的节点:用唯一的孩子顶替自己的位置(子树上移)。
- 删除有两个孩子的节点:用中序后继(右子树最小值)或中序前驱(左子树最大值)替换其值,然后递归删除那个后继节点。后继节点至多只有一个右孩子,于是问题化归为情况 1 或 2。
删除有两个孩子的节点 5(用中序后继 6 替换):
5 6
/ \ / \
3 8 ==> 3 8
/ \ / \
6 9 7 9 <- 原 6 位置(现为 7)被摘除
\
7
class BST:
"""二叉搜索树:查找/插入/删除平均 O(log n),最坏 O(n)(退化)。"""
def __init__(self):
self.root = None
self._size = 0
# ---------- 查找 ----------
def search(self, val):
cur = self.root
while cur: # 迭代版:不需要递归栈
if val == cur.val:
return cur
cur = cur.left if val < cur.val else cur.right
return None
def contains(self, val):
return self.search(val) is not None
# ---------- 插入 ----------
def insert(self, val):
if self.root is None:
self.root = TreeNode(val)
self._size += 1
return
cur = self.root
while True:
if val < cur.val:
if cur.left is None:
cur.left = TreeNode(val)
break
cur = cur.left
elif val > cur.val:
if cur.right is None:
cur.right = TreeNode(val)
break
cur = cur.right
else:
return # 不允许重复值,直接忽略
self._size += 1
# ---------- 删除 ----------
def _delete(self, node, val):
"""返回删除后的子树根,用递归可以自然地「用孩子顶替自己」。"""
if node is None:
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:
# 情况 1 与 2:至多一个孩子,直接用孩子顶替
if node.left is None:
return node.right
if node.right is None:
return node.left
# 情况 3:两个孩子,找中序后继(右子树最小)
succ = node.right
while succ.left:
succ = succ.left
node.val = succ.val # 用后继值覆盖当前节点
node.right = self._delete(node.right, succ.val) # 再删掉后继节点
return node
def delete(self, val):
if self.contains(val):
self.root = self._delete(self.root, val)
self._size -= 1
def inorder(self):
return inorder(self.root)
def height(self):
"""树高(边数约定):空树 -1,叶子 0。"""
def h(node):
return -1 if node is None else 1 + max(h(node.left), h(node.right))
return h(self.root)
if __name__ == "__main__":
bst = BST()
for v in [50, 30, 70, 20, 40, 60, 80]:
bst.insert(v)
assert bst.inorder() == [20, 30, 40, 50, 60, 70, 80] # 中序即升序
bst.delete(20) # 情况 1:叶子
assert bst.inorder() == [30, 40, 50, 60, 70, 80]
bst.delete(60) # 情况 2:单孩子
assert bst.inorder() == [30, 40, 50, 70, 80]
bst.delete(50) # 情况 3:双孩子
assert bst.inorder() == [30, 40, 70, 80]
print("BST 增删查测试通过,树高 =", bst.height())
6.2 退化问题
按升序插入 会得到一棵只有右孩子的「斜树」,此时查找、插入、删除全部退化为 ,与链表无异。这就是平衡树存在的全部理由:不是为了让平均更快,而是为了保证最坏情况。
| 操作 | 平均(随机数据) | 最坏(有序插入) |
|---|---|---|
| BST 查找 | ||
| BST 插入 | ||
| BST 删除 | ||
| AVL / 红黑树 |
七、平衡二叉树(AVL Tree)
AVL 树是最早的自平衡 BST(Adelson-Velsky & Landis, 1962)。平衡因子(Balance Factor) 定义为:
插入或删除导致 时,通过旋转局部调整恢复平衡。旋转不改变中序序列,因此 BST 性质始终保持。
7.1 四种失衡类型与旋转判断
判断方法:从失衡节点( 的那个)出发,看新节点插入到了哪条路径:
| 类型 | 形态 | 判断依据 | 处理 |
|---|---|---|---|
| LL | 左孩子的左子树过高 | 且左孩子 | 一次右旋 |
| RR | 右孩子的右子树过高 | 且右孩子 | 一次左旋 |
| LR | 左孩子的右子树过高 | 且左孩子 | 先对左孩子左旋,再对自己右旋 |
| RL | 右孩子的左子树过高 | 且右孩子 | 先对右孩子右旋,再对自己左旋 |
记忆诀窍:类型名的两个字母就是「从失衡节点走到新节点的方向」。LR 表示先向左(到左孩子)再向右(到右子树),需要「先左旋再右旋」,两次旋转的方向与路径方向相反。
LL: 右旋 z RR: 左旋 z LR: 先左旋 y 再右旋 z RL: 先右旋 y 再左旋 z
z z z z
/ / \ / \ / \
y ==> y ... y ... ... y
/ / \ / \ / \
x x ... x ... x ...
(y 的右孩子变成新的根)
class AVLNode:
__slots__ = ("val", "left", "right", "height")
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.height = 0 # 叶子高度为 0(边数约定)
def _h(node):
return node.height if node else -1
def _update(node):
node.height = 1 + max(_h(node.left), _h(node.right))
def _balance_factor(node):
return _h(node.left) - _h(node.right)
def rotate_right(z):
"""LL 情形:以 z 为轴右旋。返回新的子树根。
指针顺序很关键:先把 y 的右子树挂到 z 的左边,再让 z 成为 y 的右孩子。
"""
y = z.left
z.left = y.right # y 的右子树「过户」给 z 当左子树
y.right = z
_update(z) # 必须先更新 z(它现在是子节点)再更新 y
_update(y)
return y
def rotate_left(z):
"""RR 情形:以 z 为轴左旋。与右旋完全对称。"""
y = z.right
z.right = y.left
y.left = z
_update(z)
_update(y)
return y
class AVLTree:
"""AVL 树:严格平衡(|BF| <= 1),查找最坏 O(log n)。"""
def __init__(self):
self.root = None
def insert(self, val):
self.root = self._insert(self.root, val)
def _insert(self, node, val):
if node is None:
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 # 重复值不插入
_update(node)
return self._rebalance(node)
def delete(self, val):
self.root = self._delete(self.root, val)
def _delete(self, node, val):
if node is None:
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 node.left is None:
return node.right
if node.right is None:
return node.left
succ = node.right # 中序后继
while succ.left:
succ = succ.left
node.val = succ.val
node.right = self._delete(node.right, succ.val)
_update(node)
return self._rebalance(node)
def _rebalance(self, node):
"""统一处理 LL / RR / LR / RL 四种失衡。"""
bf = _balance_factor(node)
if bf > 1: # 左子树过高 -> LL 或 LR
if _balance_factor(node.left) < 0: # LR:左孩子右子树高
node.left = rotate_left(node.left) # 先左旋左孩子
return rotate_right(node) # 再右旋自己
if bf < -1: # 右子树过高 -> RR 或 RL
if _balance_factor(node.right) > 0: # RL:右孩子左子树高
node.right = rotate_right(node.right)
return rotate_left(node)
return node
def inorder(self):
return inorder(self.root)
def height(self):
return _h(self.root)
if __name__ == "__main__":
# 升序插入本会让普通 BST 退化成链,AVL 通过旋转保持平衡
avl = AVLTree()
for v in range(1, 11):
avl.insert(v)
print("有序插入 1..10 后:")
print(" 中序 =", avl.inorder())
print(" 树高 =", avl.height(), "(普通 BST 此时为 9)")
assert avl.inorder() == list(range(1, 11))
assert avl.height() <= 4 # 理论最小高度为 ceil(log2(11))-1 = 3
avl.delete(5)
assert avl.inorder() == [1, 2, 3, 4, 6, 7, 8, 9, 10]
print("AVL 测试通过")
八、红黑树(Red-Black Tree)
红黑树是一种弱平衡 BST,通过给节点染色 + 旋转维持近似平衡。
8.1 五条性质
- 每个节点是红色或黑色。
- 根节点是黑色。
- 每个叶子(NIL 空节点)是黑色。
- 红节点的两个孩子必须是黑色(等价于:不存在两个连续的红节点)。
- 从任一节点出发到其所有后代 NIL 叶子的路径上,黑节点数量相同(称为该节点的黑高 Black Height)。
由性质 4、5 可推出关键结论:最长路径不超过最短路径的 2 倍,因此树高 ,所有操作 。
推导要点:设某节点黑高为 ,则其子树至少有 个节点(黑节点满二叉树);而根到叶子的路径上红黑交替,最长路径 。于是 。
8.2 红黑树与 AVL 对比
| 维度 | AVL 树 | 红黑树 |
|---|---|---|
| 平衡严格度 | 严格,, | 弱平衡, |
| 查找性能 | 略快(树更矮) | 略慢,常数差异小 |
| 插入删除代价 | 旋转更多(删除最多 次旋转) | 旋转更少(插入最多 2 次、删除最多 3 次旋转,其余靠变色) |
| 实现复杂度 | 中等 | 较高(删除的 4 种情形 + 对称共 8 种) |
| 适合场景 | 读多写少 | 读写均衡、频繁增删 |
| 典型应用 | 早期数据库索引、Windows 内核部分结构 | std::map/set、Java TreeMap、Linux CFS 调度器、epoll |
为什么 STL 的
map选红黑树而不是 AVL
map的使用模式是插入、删除与查找混合。红黑树牺牲少量查找深度(最多 2 倍),换来明显更少的旋转与更稳定的更新代价——这对需要频繁修改的关联容器更重要。此外红黑树的实现虽然复杂,但操作次数有严格上界(插入 2 次旋转、删除 3 次旋转),便于推理性能。AVL 更适合「一次构建、大量查询」的静态或读多写少场景。
九、B 树与 B+ 树
二叉树的问题是太高: 时高度约 30,若每个节点一次磁盘 I/O,就需要 30 次读盘。B 树(B-Tree) 的思路:让一个节点存多个键、多个孩子,把树压矮。
- m 阶 B 树:每个节点最多 个孩子、 个键;除根外每个节点至少 个孩子;所有叶子在同一层;键在内部节点也存储。
- B+ 树:内部节点只存索引键不存数据,所有数据都在叶子层,且叶子用双向链表串起来。
B+ 树优于 B 树的工程原因:
- 内部节点更小 → 同样大小的磁盘页能装更多键 → 树更矮 → I/O 更少。MySQL InnoDB 页默认 16 KB,一个内部节点可放上千个键,3~4 层即可索引上亿行。
- 所有查询都走到叶子,路径长度一致,查询性能稳定可预测。
- 叶子链表天然支持范围查询(
BETWEEN、ORDER BY、> <),只需顺序扫描叶子层;B 树范围查询要靠中序遍历,反复上下跳。
磁盘 I/O 次数对比:假设一次 I/O 读一个节点。
| 结构 | 分支因子 | 时的树高 | 最坏 I/O 次数 |
|---|---|---|---|
| 二叉搜索树(平衡) | 2 | 约 30 次 | |
| 红黑树 | 2 | 最多 60 次 | |
| B+ 树(页 16 KB,键 16 B) | 约 1000 | 3~4 次(根常驻内存则 2~3 次) |
结论
数据库索引选 B+ 树不是因为它「更快」,而是因为它的代价模型匹配磁盘:磁盘随机 I/O 极贵(相对内存访问慢约 倍),因此优化目标是最小化 I/O 次数,而不是最小化比较次数。这就是数据结构选型必须结合存储层次的典型案例。
十、堆(Heap)
二叉堆是一棵完全二叉树,满足堆序性质:小根堆中每个节点的值 其所有后代(只保证局部偏序,不保证全局有序)。
10.1 数组表示与上浮下沉
用数组存完全二叉树,无需指针(关系见 2.4 节)。两个核心操作:
- 上浮(Sift Up / Bubble Up):新元素放到数组末尾,不断与父比较,若违反堆序则交换,直到合适位置。插入用,。
- 下沉(Sift Down / Heapify Down):把根元素换成末尾元素后,与较小的那个孩子比较并交换,直到满足堆序。弹出堆顶用,。
class MinHeap:
"""最小堆:数组实现完全二叉树,插入/弹出 O(log n),取最小 O(1)。"""
def __init__(self, items=None):
self._data = list(items) if items else []
if self._data:
self._build_heap()
def __len__(self):
return len(self._data)
def peek(self):
if not self._data:
raise IndexError("peek from empty heap")
return self._data[0]
# ---------- 上浮 ----------
def _sift_up(self, i):
while i > 0:
parent = (i - 1) // 2
if self._data[i] < self._data[parent]: # 比父小 -> 违反小根堆
self._data[i], self._data[parent] = self._data[parent], self._data[i]
i = parent
else:
break # 已满足堆序,提前结束
# ---------- 下沉 ----------
def _sift_down(self, i):
n = len(self._data)
while True:
smallest = i
left, right = 2 * i + 1, 2 * i + 2
# 必须与「更小的那个孩子」交换,否则换完仍可能违反堆序
if left < n and self._data[left] < self._data[smallest]:
smallest = left
if right < n and self._data[right] < self._data[smallest]:
smallest = right
if smallest == i:
break
self._data[i], self._data[smallest] = self._data[smallest], self._data[i]
i = smallest
def push(self, val):
self._data.append(val) # 先放末尾,再上浮到正确位置
self._sift_up(len(self._data) - 1)
def pop(self):
if not self._data:
raise IndexError("pop from empty heap")
top = self._data[0]
last = self._data.pop() # 取末尾元素
if self._data:
self._data[0] = last # 末尾元素顶上根部
self._sift_down(0) # 再下沉复原
return top
def _build_heap(self):
"""自底向上建堆:从最后一个非叶节点开始下沉。"""
for i in range(len(self._data) // 2 - 1, -1, -1):
self._sift_down(i)
@classmethod
def heapify(cls, items):
"""Floyd 建堆法,时间 O(n)。"""
return cls(items)
if __name__ == "__main__":
h = MinHeap.heapify([9, 4, 7, 1, 8, 2])
print("堆顶 =", h.peek()) # 1
h.push(0)
print("push(0) 后堆顶 =", h.peek()) # 0
print("依次弹出:", [h.pop() for _ in range(len(h))]) # 升序输出
10.2 建堆为什么是
直觉上「 个元素各下沉一次,每次 」会得到 ,但这个上界不紧。精确分析:高度为 的节点最多有 个,而一个高度为 的节点下沉代价是 ,因此总代价:
用到的级数结论是 (),取 得 2。
关键洞察
建堆时大多数节点都在底层(约一半节点是叶子,高度 0,下沉代价为 0),而高度大的节点极少。自底向上建堆把「贵操作」分给了少数节点,因此总代价是线性的。同理,插入式建堆(逐个
push)是 ,比 Floyd 建堆慢——同样的目标,不同的顺序,复杂度不同。
10.3 堆排序
步骤:① 建大根堆 ;② 反复把堆顶(最大值)与末尾交换、堆长度减 1、对新堆顶下沉,共 次 操作。
def heap_sort(nums):
"""堆排序:原地、时间 O(n log n)、空间 O(1),但不稳定。"""
arr = list(nums)
def sift_down(i, size):
while True:
largest, l, r = i, 2 * i + 1, 2 * i + 2
if l < size and arr[l] > arr[largest]:
largest = l
if r < size and arr[r] > arr[largest]:
largest = r
if largest == i:
return
arr[i], arr[largest] = arr[largest], arr[i]
i = largest
n = len(arr)
for i in range(n // 2 - 1, -1, -1): # 建大根堆,O(n)
sift_down(i, n)
for end in range(n - 1, 0, -1):
arr[0], arr[end] = arr[end], arr[0] # 最大值归位到末尾
sift_down(0, end) # 在缩小的范围内恢复堆
return arr
assert heap_sort([5, 2, 9, 1, 5, 6]) == [1, 2, 5, 5, 6, 9]
print("堆排序测试通过")
10.4 Top-K 问题
求最大的 K 个数,用大小为 K 的最小堆:堆里始终保存「当前见过的最大的 K 个」,新元素比堆顶大就替换堆顶。
- 时间复杂度:,当 时远优于整体排序的 。
- 空间复杂度:。
- 反直觉点:求最大 K 个要用最小堆,因为堆顶是「这 K 个里最弱的」,最容易被替换,正好当作门槛。
import heapq
def top_k_largest(nums, k):
"""返回最大的 k 个数(升序)。时间 O(n log k),空间 O(k)。"""
if k <= 0:
return []
heap = [] # 最小堆,容量 k
for v in nums:
if len(heap) < k:
heapq.heappush(heap, v)
elif v > heap[0]: # 比当前门槛大才替换
heapq.heapreplace(heap, v)
return sorted(heap)
def top_k_frequent(words, k):
"""词频 Top-K:Counter 统计 + 最小堆,O(n log k)。"""
from collections import Counter
counts = Counter(words)
return [w for w, _ in heapq.nlargest(k, counts.items(), key=lambda kv: kv[1])]
print(top_k_largest([3, 1, 4, 1, 5, 9, 2, 6], 3)) # [5, 6, 9]
print(top_k_frequent("a b a c b a".split(), 2)) # ['a', 'b']
十一、Trie 字典树
Trie(前缀树 / 字典树) 把字符串按字符逐层展开,公共前缀共享节点。查找、插入代价是 ( 为串长),与词典规模无关。
插入 "cat"、"car"、"card"、"dog" 后的 Trie:
(root)
/ \
c d
a o
/ \ |
t r g
|
d <- is_end=True 标记词尾
class Trie:
"""字典树:插入/查询 O(L),适合前缀检索与自动补全。"""
def __init__(self):
# 用嵌套 dict 表示孩子,比固定 26 数组省内存(但访问稍慢)
self.root = {}
self._END = "#" # 词尾标记,用特殊键避免与字符冲突
def insert(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {})
node[self._END] = True
def search(self, word):
node = self._walk(word)
return node is not None and self._END in node
def starts_with(self, prefix):
return self._walk(prefix) is not None
def _walk(self, s):
node = self.root
for ch in s:
if ch not in node:
return None
node = node[ch]
return node
def autocomplete(self, prefix, limit=10):
"""前缀补全:走到 prefix 结尾后 DFS 收集所有词。"""
node = self._walk(prefix)
if node is None:
return []
res = []
def dfs(cur, path):
if len(res) >= limit:
return
if self._END in cur:
res.append(prefix + path)
for ch, nxt in cur.items():
if ch != self._END:
dfs(nxt, path + ch)
dfs(node, "")
return res
if __name__ == "__main__":
t = Trie()
for w in ["cat", "car", "card", "dog", "done"]:
t.insert(w)
assert t.search("car") and not t.search("ca")
assert t.starts_with("ca") and not t.starts_with("z")
print("以 ca 开头的词:", t.autocomplete("ca")) # ['cat', 'car', 'card']
print("以 do 开头的词:", t.autocomplete("do")) # ['dog', 'done']
| 结构 | 插入 | 查找 | 前缀查询 | 空间 |
|---|---|---|---|---|
| 哈希表 | 期望 | 期望 | 不支持 | 存完整键 |
| 平衡树 | 支持(范围扫描) | 存完整键 | ||
| Trie | 最优 | 可能较大(指针开销) |
十二、哈夫曼树与哈夫曼编码
哈夫曼树(Huffman Tree):给定 个带权叶子,构造带权路径长度(WPL)最小的二叉树。
其中 是第 个叶子的路径长度(根到该叶子的边数)。
构造算法(贪心):
- 把所有叶子放入最小堆。
- 每次取出权值最小的两个节点,合并成一个新节点(权值为两者之和),新节点入堆。
- 重复直到堆中只剩一个节点,它就是根。
复杂度: 次合并,每次堆操作 ,总计 。
哈夫曼编码:把字符频率当权值构造哈夫曼树,左分支记 0、右分支记 1,得到前缀码(Prefix Code)——任何编码都不是另一个编码的前缀,因此解码无歧义,且平均码长最短。这是无损压缩(ZIP、JPEG、HTTP/2 HPACK)的核心技术之一。
与 的联系
哈夫曼树是严格二叉树(每个内部节点都有两个儿子,没有度为 1 的节点)。由 :叶子数 个,则内部节点(合并产生)为 个,总节点数 ——这就是为什么 个字符的哈夫曼编码总共需要 个树节点。
import heapq
class HuffmanNode:
__slots__ = ("weight", "char", "left", "right")
def __init__(self, weight, char=None, left=None, right=None):
self.weight = weight
self.char = char # 非 None 表示是叶子(原始字符)
self.left = left
self.right = right
def build_huffman(freq: dict):
"""给定 {字符: 频次},返回哈夫曼树根节点。时间 O(n log n)。"""
# 用递增序号做 tie-breaker,避免两个节点权重相同时比较 HuffmanNode 报错
heap = [(w, i, HuffmanNode(w, ch)) for i, (ch, w) in enumerate(freq.items())]
heapq.heapify(heap)
seq = len(heap)
while len(heap) > 1:
w1, _, n1 = heapq.heappop(heap) # 最小
w2, _, n2 = heapq.heappop(heap) # 次小
merged = HuffmanNode(w1 + w2, None, n1, n2)
heapq.heappush(heap, (w1 + w2, seq, merged))
seq += 1
return heap[0][2] if heap else None
def huffman_codes(root):
"""生成 {字符: 编码},约定左 0 右 1。"""
codes = {}
def dfs(node, code):
if node is None:
return
if node.char is not None: # 叶子
codes[node.char] = code or "0" # 只有一个字符时编码不能为空
return
dfs(node.left, code + "0")
dfs(node.right, code + "1")
dfs(root, "")
return codes
def weighted_path_length(root, depth=0):
"""计算 WPL = Σ(权值 × 路径长度)。"""
if root is None:
return 0
if root.char is not None:
return root.weight * depth
return (weighted_path_length(root.left, depth + 1)
+ weighted_path_length(root.right, depth + 1))
if __name__ == "__main__":
freq = {"a": 45, "b": 13, "c": 12, "d": 16, "e": 9, "f": 5}
root = build_huffman(freq)
codes = huffman_codes(root)
print("编码表:", codes)
print("WPL =", weighted_path_length(root)) # 经典例子答案为 224
assert weighted_path_length(root) == 224
# 验证前缀性质:任何编码都不是另一个的前缀
for x in codes.values():
for y in codes.values():
if x != y:
assert not y.startswith(x), "违反前缀码性质"
print("哈夫曼编码测试通过(前缀性质成立)")
十三、树与堆相关结构总览
| 结构 | 查找 | 插入 | 删除 | 最值 | 空间 | 典型应用 |
|---|---|---|---|---|---|---|
| 普通二叉树 | 表达式树、语法树 | |||||
| BST | 平均 / 最坏 | 同左 | 同左 | 最左/最右 | 教学、小规模有序数据 | |
| AVL 树 | (旋转较多) | 读多写少的有序索引 | ||||
| 红黑树 | (≤2 次旋转) | (≤3 次旋转) | std::map、TreeMap、epoll | |||
| B / B+ 树 | 次 I/O | 同左 | 同左 | 数据库与文件系统索引 | ||
| 二叉堆 | 仅最值 | 优先队列、堆排序、Top-K | ||||
| Trie | — | 前缀搜索、自动补全、IP 路由 | ||||
| 哈夫曼树 | — | 合并 | — | — | 节点= | 压缩编码 |
十四、注意事项与常见坑
树与堆高频踩坑清单
1. 深度/高度约定不统一:混用「边数」与「节点数」会让 AVL 平衡因子判断反向。
2. BST 删除两个孩子时忘记递归删除后继:只替换值不删旧节点,会导致重复值。
3. BST 定义必须用「子树所有值」而非「左右孩子」:只比较孩子会漏掉深层违规。
4. AVL 旋转后忘记更新高度:且必须先更新被旋下去的子节点,再更新新的子树根。
5. LR/RL 的方向搞反:记住「类型字母 = 从失衡点走向新节点的方向,旋转方向与之相反」。
6. 中序非递归写成死循环:
while cur or stack两个条件缺一不可。7. 后序非递归直接用前序代码:正确做法是「根-右-左」再整体反转,直接套前序会得到错误结果。
8. 建堆用逐个插入:那是 ;正确做法是自底向上从
n//2-1开始下沉,。9. 堆只能保证堆顶最值,不能保证整体有序:
heap[1]不是第二小,要取第二小必须heappop两次。10. 用
heapq存不可比较的对象:元组比较会退化到比较第二个元素,需加序号做 tie-breaker。11. Top-K 用错堆的方向:求最大 K 个用最小堆;求最小 K 个用最大堆(Python 需存负值)。
12. Trie 用固定 26 长度数组存孩子:含中文/大小写混合时会数组越界或浪费大量内存。
13. 递归遍历深树导致
RecursionError:斜树深度可达 ,应改非递归或调高限制(有 C 栈溢出风险)。
十五、练习题
练习 1:求二叉树的最大深度与最小深度
分别用递归与非递归(层序)实现。注意最小深度不能简单写成
1 + min(左, 右)——若一个孩子为空,那条路径不算叶子路径。
练习 2:验证二叉搜索树
给定一棵二叉树,判断它是否为合法 BST。分别用「中序遍历检查升序」与「递归传递上下界」两种方法实现,并说明为什么只比较父子节点是错的(给出反例)。
练习 3:手写 AVL 插入并画出旋转过程
依次插入
[10, 20, 30, 40, 50, 25],画出每次插入后的树形与平衡因子,标出发生旋转的位置与类型(LL/RR/LR/RL),最后用代码验证中序结果。
练习 4:合并 K 个有序链表 / 数据流中位数
① 用最小堆合并 个有序链表,分析复杂度 。
② 设计一个支持
addNum与findMedian的结构,用一个大根堆 + 一个小根堆,要求findMedian为 ,addNum为 。
练习 5:用 Trie 实现敏感词过滤
给定敏感词表与一段文本,用 Trie 找出所有出现的敏感词。进阶:思考如何用 AC 自动机(Aho-Corasick) 把「多模式串匹配」从逐个 Trie 查询优化到单次 。
十六、常见问题 FAQ
Q1:为什么完全二叉树能用数组存,普通二叉树不行?
数组表示依赖下标与父子关系的固定映射,这要求树中节点位置可预测。完全二叉树「除最后一层外全满、最后一层从左连续」的结构保证了数组前 个位置被恰好填满、无空洞。普通二叉树若用数组存,需要为缺失节点留占位,右斜树会退化成需要 个槽位,空间复杂度从 变为 。链式存储则与树的形状无关,始终 。
Q2:AVL 和红黑树该选哪个?
判据是查询与更新的比例。查询远多于更新(如配置表、静态索引)选 AVL,因为树更矮、比较次数更少。更新频繁或读写均衡(如通用关联容器)选红黑树,因为旋转次数少且更新代价有严格上界。若还需要范围查询与磁盘存储,两者都不合适,应直接上 B+ 树。
Q3:堆排序已经 且原地,为什么实践中还是快排更常用?
三个原因:① 常数因子:堆排序的下沉操作访问的内存地址跳跃(),缓存不友好;快排顺序扫描数组,缓存命中率高。② 分支预测:快排的分区循环模式简单,CPU 分支预测器命中率更高。③ 稳定性:两者都不稳定,但快排可与插入排序结合(小数组用插入排序)进一步降低常数。堆排序的真正优势是最坏情况 与 空间,在实时性或内存受限场景不可替代。
Q4:B 树和 B+ 树的关键区别是什么?
三点:① 数据位置:B 树内部节点也存数据记录,B+ 树只有叶子存数据,内部节点纯索引。② 查询路径:B 树可能在内部节点命中提前返回,B+ 树一定走到叶子,因此路径长度固定、性能可预测。③ 范围查询:B+ 树叶子有链表,范围扫描效率极高;B 树需要中序回溯。因此数据库(MySQL InnoDB)与文件系统(NTFS、ext4)索引普遍用 B+ 树或其变种。
相关笔记
- 数据结构-线性结构:数组与链表是树与堆的存储基础,优先队列由队列概念引出
- 数据结构-哈希表:哈希表与平衡树在查找结构选型上互为替代,本文 8.2 节对比的延伸
- 算法-排序:堆排序、归并排序、快排的横向对比与稳定性分析
- 算法-复杂度分析:主定理、均摊分析与本文建堆 的级数证明基础
- 算法-查找与分治:二分查找与树形结构查找的思想联系
- 数据库原理:B+ 树索引、聚簇索引与最左前缀原则的落地
- 计算机组成原理:存储层次与磁盘 I/O 代价,理解 B+ 树设计的物理前提
- 00-索引:全库导航
参考来源
- OI Wiki《二叉树》,性质、遍历与还原:https://oi-wiki.org/ds/binary-tree/
- OI Wiki《AVL 树》,四种旋转与实现细节:https://oi-wiki.org/ds/avl/
- OI Wiki《堆》,建堆复杂度证明与堆排序:https://oi-wiki.org/ds/heap/
- OI Wiki《字典树(Trie)》:https://oi-wiki.org/ds/trie/
- VisuAlgo 可视化教学,BST 与 AVL 旋转动画:https://visualgo.net/en/bst
- Python 官方文档《heapq —— 堆队列算法》,堆不变量与 API 语义:https://docs.python.org/3/library/heapq.html
- MySQL 官方手册《InnoDB 索引类型》,B+ 树索引与聚簇索引说明:https://dev.mysql.com/doc/refman/8.4/en/innodb-index-types.html
- CLRS《算法导论》第 6 章(堆排序,含建堆 证明)、第 13 章(红黑树五条性质)
- 严蔚敏《数据结构(C 语言版)》, 推导、哈夫曼树与编码