公共祖先（树）

2026/6/28 · 算法与数据结构

问题简述

1 问题背景

在处理层级数据时，寻找“共同根源”是极高频的需求。

行政决策：如校内协作，机械学院和电子学院要开会，需要找到主管这两者的副校长来协调。
血缘回溯：在庞大的族谱中，找到两个远房亲戚最近的共同祖先，以确定亲缘远近。
技术痛点：如果一棵树有数万个节点，我们不可能每次查询都通过肉眼从下往上数，算法的效率决定了系统的响应速度。

2 问题抽象

给定一棵树中的两个节点 $p$ 和 $q$ ，寻找一个距离它们最近（深度最大）的共有祖先节点 $L$ 。

性质： $L$ 必须在根到 $p$ 的路径上，也必须在根到 $q$ 的路径上。
极端情况：如果 $p$ 就是 $q$ 的父亲，那么 $L$ 就是 $p$ 自身。

树的基础知识

1 树的本质与逻辑构造

1.1 形式化定义

树（Tree）是一种非线性数据结构，用于表示具有层次关系的数据集。

数学描述：一棵树是 $n (n \ge 0)$ $n (n \geq 0)$ 个节点的有限集合 $T$ $T$ 。
- 空树： $n = 0$ 时。
- 非空树： $n > 0$ 时，有且仅有一个特定的根节点（Root）。其余节点可分为 $m$ 个互不相交的有限集 $T_1, T_2, \dots, T_m$ ，其中每个集合本身又是一棵树，称为根的子树（Subtree）。

1.2 核心术语精讲

节点（Node）：树的基本单元，包含一个数据元素和指向其子树的引用（指针）。
度（Degree）：
- 节点的度：该节点拥有的子树数量。
- 树的度：树中所有节点度的最大值。
层次与高度：
- 层级（Level）：从根开始定义，根为第 1 层（部分教材定义为 0），其子节点为第 2 层，以此类推。
- 深度（Depth）：从根到该节点的路径长度（通常定义根的深度为 0）。
- 高度（Height）：从该节点到最远叶子节点的路径长度（叶子的高度为 0）。
节点关系：
- 父子关系：若 A 有子节点 B，则 A 是 B 的 Parent，B 是 A 的 Child。
- 兄弟（Sibling）：共享同一父节点的节点。
- 祖先（Ancestor）：从根到该节点路径上的所有节点。
- 后代（Descendant）：该节点子树中的所有节点。
叶子节点（Leaf）：度为 0 的节点，即没有孩子的节点。
森林（Forest）： $m (m \ge 0)$ 棵互不相交的树的集合。

2 树的分类体系与特性

2.1 按子节点数量分类

二叉树（Binary Tree）：每个节点最多有两个子树（左子树和右子树）。这是应用最广泛、理论最丰富的树形结构。
多叉树（Multiway Tree）：节点可拥有两个以上的孩子（如三叉树、四叉树）。文件系统是典型的多叉树应用。

2.2 按形状与平衡性质分类

满二叉树（Full Binary Tree）：所有节点要么是叶子，要么有两个孩子，且所有叶子都在同一层。
完全二叉树（Complete Binary Tree）：除最后一层外全满，且最后一层节点尽可能靠左。其核心优势是可以高效地映射到数组存储中。
二叉搜索树（BST）：左子树所有值 $\le$ 根值 $<$ 右子树所有值。
平衡二叉树（Balanced Tree）：
- AVL 树：任何节点的左右子树高度差不超过 1。
- 红黑树：通过颜色约束保证最长路径不超过最短路径的两倍，实现“近似平衡”。
堆（Heap）：一种特殊的完全二叉树。大顶堆中父节点值 $\ge$ 子节点；小顶堆则相反。

3 抽象数据类型（ADT）与存储实现

3.1 树的 ADT 核心操作

一个完整的树结构应支持以下基本操作：

初始化：创建空树。
获取属性：获取根节点、父节点、所有孩子节点、树的深度/高度、节点总数。
修改拓扑：插入子树、删除指定节点及其整个子树。
搜索与遍历：按特定顺序访问所有节点。

3.2 物理存储的三种范式

链式存储（Linked Storage）：每个节点包含数据域和多个指针域（指向孩子）。适用于一般的、结构动态变化的树。
数组存储（Array Storage）：主要用于完全二叉树。通过数组下标计算父子关系（如：索引为 $i$ 的节点，左孩子通常为 $2i$ ，右孩子为 $2i+1$ ）。
邻接表（Adjacency List）：利用列表或哈希表存储每个节点的孩子列表，适用于多叉树。

4 遍历算法与运行机制

4.1 深度优先搜索（DFS）

前序（PreOrder）：根 $\rightarrow$ 左 $\rightarrow$ 右。
中序（InOrder）：左 $\rightarrow$ 根 $\rightarrow$ 右（仅适用于二叉树）。
后序（PostOrder）：左 $\rightarrow$ 右 $\rightarrow$ 根。

4.2 广度优先搜索（BFS）

层序遍历（LevelOrder）：从上到下、从左到右逐层访问。通常利用队列实现。

4.3 递归与内存栈（底层原理）

递归实现遍历时，系统会利用内存栈：

栈帧（Stack Frame）：每次函数调用都会压入一个栈帧，存储参数、局部变量和返回地址。
控制流：通过 call 指令压栈跳转，执行完后通过 ret 弹出地址返回。这解释了递归虽然代码简洁，但大规模使用可能导致栈溢出的原因。

5 扩展背景——为什么需要复杂的树？

5.1 存储层级结构（Memory Hierarchy）

计算机存储系统的速度与成本存在权衡：寄存器、缓存（SRAM）、主存（DRAM）速度极快但容量小且昂贵；次级存储（磁盘/闪存）容量巨大但速度极慢（慢百万倍级）。

5.2 磁磁盘驱动器（HDD）的局限性

磁盘访问时间由三部分组成：寻道时间（Seek） + 旋转延迟（Rotation） + 传输时间（Transfer）。

由于物理磁头移动极其缓慢，算法的目标必须是极力减少磁盘 I/O 次数。
B 树/B+ 树的动机：通过高分支因子（ $m$ 阶）大幅度压缩树的高度（使其变得极其“扁平”），让每一次节点访问对应一次磁盘块读取，从而在海量数据中实现高效检索。

树的扩展

1 BST的退化问题

当你按顺序插入 10, 20, 30, 40, 50 时，BST 不会形成张开的树，而是会变成一条斜线（链表）。

后果：原本 $O(\log n)$ 的搜索速度变回了最慢的 $O(n)$ 。为了解决这个问题，我们需要 AVL 树（自平衡树）。

2 AVL树的动态旋转

2.1 平衡因子（Balance Factor）

AVL 规定：任何节点左右子树的高度差绝对值不能超过 1。一旦超过，就会触发“旋转”操作来重塑树的形状。

2.2 四大旋转场景

LL 型（右旋）：左边太沉了。将左孩子提升为新根，原根下沉变为右孩子。
1. 令失衡节点为 A，其左孩子为 B。
2. B 提升为新根。
3. A 下沉变为 B 的右孩子。
4. 若 B 原本有右子树（ $\beta$ ），则将其挂在 A 的左边。

      A (失衡节点)               B (新根)
     / \                       /   \
    B   γ      == 右旋 ==>    α     A
   / \                             / \
  α   β (B的右子树)                β   γ

RR 型（左旋）：右边太沉了。逻辑与右旋相反。
1. 令失衡节点为 A，其右孩子为 B。
2. B 提升为新根。
3. A 下沉变为 B 的左孩子。
4. 若 B 原本有左子树（ $\beta$ ），则将其挂在 A 的右边。

    A (失衡节点)                  B (新根)
   / \                          /   \
  α   B        == 左旋 ==>     A     γ
     / \                      / \
    β   γ                    α   β (B的左子树)

LR/RL 型：最为复杂，需要先进行一次局部旋转（把折线拉直成 LL 或 RR），再进行整体旋转。当一个节点的左子树的右子树插入了新节点（形成“之”字形）时，单次旋转无法解决问题，需两步走。

第一步：对左孩子 B 执行左旋，将“之”字形拉直为 LL 型。
第二步：对失衡节点 A 执行右旋。 LR型：

      A (失衡)            A (拉直为LL)          C (最终平衡)
     / \                / \                  /   \
    B   δ   ==左旋B==> C   δ   ==右旋A==>   B     A
   / \                / \                  / \   / \
  α   C              B   γ                α   β γ   δ
     / \            / \
    β   γ          α   β

RL型：

第一步：对右孩子 B 执行右旋，将“之”字形拉直为 RR 型。
第二步：对失衡节点 A 执行左旋。

    A (失衡)              A (拉直为RR)          C (最终平衡)
   / \                  / \                  /   \
  δ   B    ==右旋B==>  δ   C    ==左旋A==>  A     B
     / \                / \                / \   / \
    C   α              β   B              δ   β γ   α
   / \                    / \
  β   γ                  γ   α

2.3 总结与性能分析

操作本质：旋转的本质是在保持二叉搜索树（BST）中序遍历有序性的前提下，调整节点层级以降低树的高度。
时空开销：单次左旋或右旋仅涉及常数个指针的改变，其时间复杂度为 $O(1)$ ，空间复杂度为 $O(1)$ 。
应用目标：通过这些旋转，AVL 树能保证任何时刻的搜索、插入、删除操作均维持在 $O(\log n)$ 的高效水平。

3 面向海量数据的 B 树与平衡扩展系列

针对类似京东商品数据库这种千万级甚至亿级的数据，由于单项数据（如商品详情、图片等）体积较大且总量巨大，内存无法完全容纳，必须依赖硬盘存储。

3.1 为什么不能用普通的二叉树？

硬盘寻址慢：磁盘访问包含寻道时间、旋转延迟和传输时间，其中物理磁头移动极其缓慢。
I/O 开销巨大：二叉树在海量数据下高度过高，每增加一层通常就意味着增加一次磁盘 I/O 操作。在存储层级中，磁盘访问速度比 CPU 慢数百万倍，过深的树结构会导致查询速度无法接受。

3.2 2-3 树：多路平衡的基石

2-3 树是理解所有多路搜索树的基础，它本质上是阶数为 3 的 B 树。

多路节点：
- 2-节点：含 1 个键和 2 个孩子，逻辑同普通二叉树。
- 3-节点：含 2 个键和 3 个孩子，能在一个节点内存储更多信息。
完美平衡：2-3 树要求所有叶子节点必须在同一水平线上。当插入导致节点超过 2 个键时，会通过向上分裂来增加树高，确保从根到任一叶子的路径长度完全相同。
- 分裂过程：临时 4-节点（触发分裂）若待插入的叶子节点已经是 3-节点，则插入新键后会暂时形成一个包含 3 个键的临时 4-节点。设这三个键为 a < b < c，则 b 为中间键。针对该临时 4-节点，执行以下分裂操作：
  - 中间键提升：将中间键 b 从 4-节点中取出，向上推送给父节点。
  - 左右分裂：剩余的两个键 a 和 c 分别分裂成两个独立的 2-节点（a 作为左 2-节点，c 作为右 2-节点）。
  递归向上检查与根分裂
  - 若父节点因接收 b 后也变成 4-节点，则继续重复上述分裂过程，逐层向上递归。
  - 若根节点发生分裂（即根变为 4-节点），则中间键 b 成为新的根节点，左右两个 2-节点成为其孩子，此时树高加 1。

通过这种“由下而上”的分裂机制，2-3 树始终保持所有叶子在同一深度，从而实现严格的平衡。

3.3 2-3-4 树与红黑树：内存中的平衡方案

2-3-4 树：阶数为 4 的 B 树，允许节点包含最多 3 个键和 4 个孩子。
红黑树 (Red-Black Tree)：一种“近似平衡”的二叉搜索树，它是 2-3-4 树的等效实现。
- 等效性：红黑树中的一个黑色节点及其红色孩子共同对应 2-3-4 树中的一个大节点。
- 核心约束：通过 5 大颜色性质：
  1. 节点非红即黑。
  2. 根节点必黑。
  3. 所有叶子（NIL 节点）必黑。
  4. 红红不连续：红节点的子节点必须为黑。
  5. 黑高相等：从任一节点到其后代叶子的所有路径包含相同数量的黑节点。
  确保最长路径不超过最短路径的两倍。这使得它在插入和删除时比 AVL 树旋转更少，综合性能极佳。

3.4 B 树与 B+ 树的“压扁”战术

为了彻底解决磁盘 I/O 问题，B 树家族采用了极高的分支因子 $m$ 。

B 树（多路平衡搜索树）：
- 高度压缩：一个节点对应一个磁盘块（通常 4KB），通过大幅度增加分叉数量，将树的高度压缩得极其“扁平”，显著减少寻道次数。
- 节点结构：每个内部节点都存储键和实际数据（或指针）。
B+ 树（数据库索引的首选）：
- 索引分层：内部节点仅存键而不存实际数据，这让单个节点能容纳数千个索引，进一步压扁树高。
- 全叶链表：所有实际数据均存在叶子节点中，且叶子节点通过顺序链表相连。这使得它在执行范围查询（如查找某价格区间商品）时，只需定位起点后顺着链表横向扫描即可，无需频繁回溯根节点。

问题的两种解法

1 朴素对齐法（适合小规模数据）

这是最像“笨办法”的模拟过程，分为三步：

测高度：首先获取 $p$ 和 $q$ 的深度（Depth）。
拉平高度：让住得“深”的那个人先往上走，走到和另一个人同一层为止（例如 $p$ 在 5 层， $q$ 在 3 层，则 $p$ 先向上移动 2 次）。
同步上溯：两人同时向上一步一步走，他们相遇的第一站就是 LCA。

缺点：如果树非常深（像一根长绳子），单次查询可能要走 $O(N)$ 步，速度太慢。

def lca_naive(u, v):
    # 先将深度对齐，让较深的节点向上移动
    while u.depth > v.depth:
        u = u.parent
    while v.depth > u.depth:
        v = v.parent
    
    # 两节点处于同一深度后，同时向上移动直到相遇
    while u != v:
        u = u.parent
        v = v.parent

2 倍增跳跃法（大量数据高效解法）

为了不一步步“爬楼梯”，我们利用二进制的倍增思想（Binary Lifting）：

预处理（练级）：提前通过 DFS 计算出每个节点向上跳 $2^0, 2^1, 2^2 \dots 2^k$ 步是谁。这个表叫 up[u][k] 表。
二进制对齐：当深度差为 13 时，我们不走 13 步，而是跳 $2^3$ （8 步）+ $2^2$ （4 步）+ $2^0$ （1 步），通过几次大跳跃迅速对齐。
大跳探测：对齐后，从最大的 $k$ 开始尝试跳。如果跳完后两人还没相遇（up[p][k] != up[q][k]），就执行跳跃并缩小跳跃幅度继续试。

优势：将 $O(N)$ 的搜索变成了 $O(\log N)$ ，查询效率实现指数级提升。

# 预处理阶段：运行 DFS 设置 self.up[u][k]，k 为 1 到 log2(n)
def lca_Binarylifting(self, u, v):
    if self.depth[u] < self.depth[v]:
        u, v = v, u
    
    # 阶段一：将 u 向上跳到与 v 同深度
    diff = self.depth[u] - self.depth[v]
    for k in range(self.max_log):
        if diff >> k & 1:
            u = self.up[u][k]
    
    if u == v:
        return u
    
    # 阶段二：同步向上大步跳跃
    for k in range(self.max_log - 1, -1, -1):
        if self.up[u][k] != self.up[v][k]:
            u = self.up[u][k]
            v = self.up[v][k]
    
    # 最终返回 u 的父节点
    return self.up[u]