w wyl123ly 的博客
MD

数据结构-树与堆

49 KB 2026.10.11 原文件

数据结构-树与堆

一句话概括

树把线性结构的「一对一」升级为「一对多」,从而把查找从 降到 :二叉搜索树(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 遍历(利用叶子空指针做线索)

五、由遍历序列还原二叉树

核心结论:

  1. 前序 + 中序、后序 + 中序 可以唯一确定一棵二叉树。
  2. 前序 + 后序 一般不能唯一确定(无法区分只有一个孩子时它是左还是右)。
  3. 只知道一种遍历更不能确定。

还原思路(前序 + 中序):前序的第一个元素是根;在中序里找到根的位置,左边就是左子树的中序、右边是右子树的中序;由左子树节点个数,可在前序中切出左子树的前序;递归即可。

例题:前序 [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 最难的环节,分三种情况:

  1. 删除叶子:直接摘掉,父节点对应指针置 None。
  2. 删除只有一个孩子的节点:用唯一的孩子顶替自己的位置(子树上移)。
  3. 删除有两个孩子的节点:用中序后继(右子树最小值)或中序前驱(左子树最大值)替换其值,然后递归删除那个后继节点。后继节点至多只有一个右孩子,于是问题化归为情况 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 五条性质

  1. 每个节点是红色或黑色。
  2. 根节点是黑色。
  3. 每个叶子(NIL 空节点)是黑色。
  4. 红节点的两个孩子必须是黑色(等价于:不存在两个连续的红节点)。
  5. 从任一节点出发到其所有后代 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 树的工程原因:

  1. 内部节点更小 → 同样大小的磁盘页能装更多键 → 树更矮 → I/O 更少。MySQL InnoDB 页默认 16 KB,一个内部节点可放上千个键,3~4 层即可索引上亿行。
  2. 所有查询都走到叶子,路径长度一致,查询性能稳定可预测。
  3. 叶子链表天然支持范围查询(BETWEEN、ORDER BY、> <),只需顺序扫描叶子层;B 树范围查询要靠中序遍历,反复上下跳。

磁盘 I/O 次数对比:假设一次 I/O 读一个节点。

结构分支因子 时的树高最坏 I/O 次数
二叉搜索树(平衡)2约 30 次
红黑树2最多 60 次
B+ 树(页 16 KB,键 16 B)约 10003~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)最小的二叉树。

其中 是第 个叶子的路径长度(根到该叶子的边数)。

构造算法(贪心):

  1. 把所有叶子放入最小堆。
  2. 每次取出权值最小的两个节点,合并成一个新节点(权值为两者之和),新节点入堆。
  3. 重复直到堆中只剩一个节点,它就是根。

复杂度: 次合并,每次堆操作 ,总计 。

哈夫曼编码:把字符频率当权值构造哈夫曼树,左分支记 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 语言版)》, 推导、哈夫曼树与编码