登录以参加训练计划

labuladong对二叉树算法的总结：

https://labuladong.online/algo/essential-technique/binary-tree-summary/

在 NOIP/CSP 竞赛中，二叉树（Binary Tree） 占据了数据结构的半壁江山。

首先我要纠正一个概念：C++ STL（标准模板库）中并没有一个直接名为 binary_tree 的容器。

但是，STL 中有很多容器底层是用二叉树实现的，或者是基于二叉树逻辑的。我们在竞赛中通常分为两类来掌握：

1. 直接调用 STL 容器（利用红黑树或堆的特性解题）。
2. 手写二叉树（为了实现更复杂的功能，如线段树、树形DP）。

下面为你详细总结。

---

第一部分：STL 中基于二叉树的容器（黑盒使用）

这些容器你不需要知道它里面怎么连线的，你只需要知道它们能自动排序，操作复杂度通常是 $O(\log N)$。

1. set 和 multiset （集合 / 多重集合）

• 底层原理：红黑树（一种自平衡二叉搜索树 BST）。
• 功能：
  • set：存进去的数会自动排序，且去重。
  • multiset：存进去的数会自动排序，不去重（允许重复元素）。
• NOIP 用途：
  • 动态维护一个有序序列。
  • 快速查找某个数是否存在。
  • 找某个数的前驱（比它小的最大数）和后继（比它大的最小数）。
• 常用函数：
  • insert(x): 插入，$O(\log N)$。
  • erase(x): 删除，$O(\log N)$。
  • find(x): 查找，返回迭代器。
  • count(x): 统计出现次数。
  • lower_bound(x): 返回第一个 $\ge x$ 的元素的迭代器（神器）。
  • upper_bound(x): 返回第一个 $> x$ 的元素的迭代器。

2. map 和 multimap （映射）

• 底层原理：红黑树。
• 功能：存 key-value 对（键值对）。通过 key 自动排序。
• NOIP 用途：
  • 相当于一个“下标可以是任意类型”的数组（离散化）。
  • 比如统计字符串出现的次数 map<string, int>。
• 常用函数：
  • mp[key] = val: 像数组一样赋值，$O(\log N)$。
  • find(key) / count(key): 查找键。

3. priority_queue （优先队列）

• 底层原理：二叉堆（完全二叉树）。
• 功能：随时取出最大值（默认）或最小值。
• NOIP 用途：
  • 贪心算法（每次取当前最优）。
  • Dijkstra 最短路优化。
• 常用函数：
  • push(x): 入队，$O(\log N)$。
  • top(): 看堆顶（最值），$O(1)$。
  • pop(): 删堆顶，$O(\log N)$。

---

第二部分：NOIP 需要“手写”的二叉树知识

STL 的容器功能是固定的，当你需要处理区间操作、子树问题时，STL 就无能为力了，必须手写。

1. 二叉树的存储方式

在算法竞赛中，我们很少用指针（Node* left），因为容易出错且慢。我们通常用结构体数组或纯数组模拟。

写法 A：结构体数组（最推荐，直观）

const int N = 1e5 + 5;
struct Node {
    int l;   // 左孩子在数组中的下标
    int r;   // 右孩子在数组中的下标
    int val; // 节点存的值
} tree[N];

// 访问左孩子：tree[i].l

写法 B：纯数组（适合完全二叉树/堆/线段树） 利用下标关系：如果是从 1 开始编号：

• 节点 i 的左孩子是 2 * i (或 i << 1)
• 节点 i 的右孩子是 2 * i + 1 (或 i << 1 | 1)

2. 核心遍历方式（必背）

• 前序遍历 (Pre-order): 根 -> 左 -> 右
• 中序遍历 (In-order): 左 -> 根 -> 右 （BST 的中序遍历是有序序列）
• 后序遍历 (Post-order): 左 -> 右 -> 根 （常用于计算子树信息，比如树形DP）
• 层序遍历 (Level-order): 用 queue 实现 BFS。

3. NOIP 高频考点：特殊的二叉树

在普及组和提高组中，你不需要手写平衡树（Treap/Splay），但必须掌握以下两种：

A. 线段树 (Segment Tree)

• 本质：一棵完美的二叉树，每个节点代表一个区间 [L, R]。
• 用途：$O(\log N)$ 解决区间修改、区间求和、区间最值问题。
• 必考指数：⭐⭐⭐⭐⭐（提高组必考，普及组压轴可能涉及）。

B. 树状数组 (Binary Indexed Tree, BIT)

• 本质：利用二进制特性构建的“残缺”二叉树。
• 用途：比线段树写起来更短，解决单点修改、区间求和。

C. 字典树 (Trie)

• 虽然是多叉树，但思想类似。用于处理字符串前缀问题。

---

总结：NOIP 备考策略

1. 如果题目只是需要“动态排序”、“查找”、“找最值”：

   • 不要手写二叉树！
   • 直接用 STL 的 set（去重排序）、map（统计/映射）、priority_queue（动态最值）。
   • 优势：代码短，不容易错，红黑树效率稳定。

2. 如果题目涉及“树的结构”、“子树操作”、“区间修改”：

   • 必须手写。
   • 普及组：重点掌握二叉树的递归遍历（求深度、还原二叉树）、堆的调整。
   • 提高组：重点掌握线段树、树形 DP。

举个简单的例子（手写递归求二叉树深度）

struct Node {
    int l, r;
} tree[1005];

int get_depth(int u) {
    if (u == 0) return 0; // 0 表示空节点
    int left_depth = get_depth(tree[u].l);
    int right_depth = get_depth(tree[u].r);
    return max(left_depth, right_depth) + 1;
}

希望这个总结能帮你理清二叉树在竞赛中的位置！如果有具体想学的点（比如线段树怎么写，或者 set 的迭代器坑点），随时问我。