数据结构

什么是数据结构

程序处理的是数据。数据不是零散孤立的，它们之间存在着某种逻辑关系，而程序需要在这些数据上反复执行各种操作。当数据规模增大、操作频次提高时，如何组织数据，将直接影响程序执行的效率。

数据结构，就是研究如何将数据元素按照特定的关系组织起来，并高效地支持对它们的增、删、查、改等基本操作的学科。

这里的“组织”包含三个层面的考量：

  1. 数据元素之间维持怎样的逻辑关系？
  2. 这种逻辑关系在计算机内存中如何落地？
  3. 落地之后，增删查改等操作能达到怎样的效率？

这三个层面，恰好对应了数据结构篇将要展开的三层递进框架：物理实现、关系结构、逻辑结构。

数据结构的核心目标：高效支持增删查改

无论一个数据结构外表如何复杂，评判其价值的标准终归要回到它支持增删查改这四类基本操作的效率上来。

  • 增：向数据结构中加入新的元素。
  • 删：从数据结构中移除已有的元素。
  • 查：在数据结构中寻找满足特定条件的元素。
  • 改：修改数据结构中某个元素的值或属性。

这四类操作，在不同的数据结构中，效率可能天差地别。有的结构擅长快速查找，却难以插入；有的结构善于灵活增删，却无法随机访问。没有哪种结构能在所有操作上都做到最优。数据结构设计的本质，就是在充分理解应用场景对增删查改需求的前提下，做出恰当的取舍。

这种取舍，最终都可以追溯到数据在物理层面上究竟是顺序存储还是链式存储。因为物理实现是所有上层操作的效率根源——访问操作是 $O(1)$ 还是 $O(n)$，插入删除需不需要搬移整个内存块，这些差异在物理层就已经注定。关系结构只是定义了元素的逻辑排列方式，逻辑结构只是在关系上施加了额外的约束，而真正决定增删查改操作效率的，是物理实现层中顺序结构与链式结构的根本分歧。这正是我们将“物理实现”作为整个数据结构篇起点的原因。

组织数据的三层递进

本系列对数据结构的讲述，采用从具体到抽象、从物理到逻辑的递进方式，分为三个层次。

第一层：物理实现

这是数据结构的物质基础。一切复杂的数据结构，最终都必须在计算机内存中落实为字节的排列。而在硬件层面，内存给我们的只有两种组织方式：

  • 顺序结构：一段连续的内存区域。它是数组的物理本质。
  • 链式结构：分散的内存节点，通过指针串联。它是链表的物理本质。

这两种结构分别注定了随机访问和插入删除的效率优劣。后续所有的关系结构，其实现方案都将在这二者之间选择或组合。

第二层：关系结构

从这一层开始，我们开始关心一个更高层面的问题：数据元素之间，应该维持怎样的逻辑关系？

纵观所有的数据组织方式，首先可以依据一个根本性问题划分为两大阵营：能否通过某种“键”直接定位到一个元素？

  • 如果能——键标识了一个元素——那么它属于表。
  • 如果不能——不存在键——那么它属于图。
  • 如果完全不存在键与目标的分离，维护的是元素和集合的关系，那么它是并查集。

表是一类可以通过键直接索引到元素的关系结构。索引的方式不同，表就分化出不同的形态。根据键的类型和索引原理，表分为三类：

  1. 线性表：按位置索引。键是一个整数下标。给出下标 $i$，能定位到第 $i$ 个元素。无论实现效率如何，线性表在逻辑层面上定义的索引方式是位置。每个元素有一个确定的前驱和一个确定的后继，它们排成一条线。对线性表的增删操作，关键代价也正来自于维护这条线的连续性。
  2. 树表：按键的序关系索引。键是元素自身（或其一部分），而索引的规则是键之间的序关系——偏序、全序、前缀序、区间序、频率序，不同的序定义出不同的树表。与线性表按固定位置一步到位不同，树表的索引是一个“逐步缩小范围”的过程。它的效率取决于树的高度，而树的高度又取决于维持平衡的能力。树表的增删操作，除了处理节点间的指针，还要维护序关系不被破坏——这是树表操作复杂度的根源。
  3. 哈希表：按键的哈希值索引。键是元素自身（或其一部分），但索引的规则既不是位置，也不是序关系，而是通过一个哈希函数将键映射为一个整数，再用这个整数作为下标去定位桶。哈希表不维护元素之间的顺序关系。它的索引是纯粹的计算，而非比较。正因为如此，它无法支持“找最小值”“找前驱后继”这类需要序关系的操作。它牺牲了序，换取了期望 $O(1)$ 的增删查。

图是一类不能通过键直接索引到元素的关系结构。图中没有“给出下标 $i$ 找到第 $i$ 个顶点”这种操作，也没有“给出键值找到对应顶点”这种全局索引。图中，要访问一个顶点，必须从某个已知的顶点出发，沿着边逐跳探访。

边，是图中唯一的关系纽带。顶点之间通过边建立任意的连接关系，这种关系是多对多的——一个顶点可以和任意多个顶点相邻。图的表达能力正因为这种“无索引、纯关系”的特性而极为强大：任何可以建模为“实体与联系”的问题，几乎都可以用图来表达。但也正因为没有索引，图的遍历和搜索往往需要遍历大量顶点和边，计算代价通常高于可索引的表结构。图的物理实现，本质上就是如何存储这些边关系。

并查集维护的是元素与集合间的从属关系——即一个元素属于哪个集合。

从函数形式看，表维护的是键到元素的映射，图维护的是顶点对到边的映射，而并查集维护的是元素到集合的映射。这三种映射，构成了关系结构层的完备分类。

关系结构的特点在于，同一种逻辑关系可以选用不同的物理实现。例如线性关系，既可以用顺序结构实现为顺序表，也可以用链式结构实现为链表。正是这种“逻辑与实现分离”的特性，使得我们可以根据实际需求调整实现方案，从而在增删查改的效率上做出不同的权衡。

第三层：逻辑结构

在关系结构之上，还可以再施加一层代数约束。通过对操作方式或元素性质加以限制，便得到了具有严格数学语义的特殊数据类型。这就是逻辑结构层。

逻辑结构不再定义“元素之间是什么关系”，因为关系已经在第二层确定。它定义的是“在这个结构上，你只能做什么操作”或者“这个结构中的元素，必须满足什么性质”：

  • 操作性质约束：限制增删操作发生的位置。
  • 元素性质约束：限制元素自身的属性。

逻辑结构层的价值在于，它为每一个具体的数据结构赋予了可严格定义的数学语义——栈对应自由群的撤销操作，队列对应自由幺半群的拼接，集合对应幂集代数。这些数学对象各自拥有一套公理和性质，当我们把一个数据结构对应上一个数学对象后，它的行为就可以被精确地推演，而不再是模糊的直觉。

三层之间的纵贯线

物理实现、关系结构、逻辑结构，这三层并非彼此孤立，而是有一条纵贯始终的线索相连：

物理层提供了砖块，关系层用砖块搭建出骨架，逻辑层在骨架上施加约束，赋予它独特的数学灵魂。

同一个逻辑结构，可以选择不同的关系结构来实现；同一种关系结构，也可以选择不同的物理方案来落地。每一层的选择，都会影响最终的增删查改效率。数据结构的学习，本质上就是学会在这三层之间做出恰当的权衡与决策。

理解了这三层递进关系之后，我们将自底向上，首先从物理实现层出发，考察顺序结构与链式结构的本质差异。随后进入关系结构层，逐一展开线性表、树表、哈希表和图的定义与实现。最后在逻辑结构层，探讨栈、队列、集合、映射等通过约束而获得的抽象数据类型，以及它们背后的代数本质。

物理结构

基本描述

物理结构是数据结构在计算机内存中的直接映射，是硬件赋予我们的最基础的数据组织方式。一切复杂的数据结构，最终都必须落实到物理结构上才能存在于计算机之中。

从内存的视角看，物理结构本质上只有两种：内存是一片连续编号的存储单元序列，数据要么占据其中一段连续的区域，要么分散在多段区域并通过记录位置关系来串联。前者称为顺序结构，后者称为链式结构。

这两种物理结构是一切数据结构的唯二物理基础。后续所有关系结构和逻辑结构，无论在逻辑层面呈现出怎样的形态，在物理层面都必然归属于顺序实现、链式实现，或二者的某种组合。

顺序结构

定义

顺序结构是指数据元素在内存中按照一段连续的地址空间依次存放的物理组织方式。每个元素紧邻其前驱和后继，逻辑上相邻的元素在物理地址上也相邻。

顺序结构在编程语言层面的最直接体现就是数组。

寻址原理

顺序结构的核心优势来自于它的寻址方式。设基地址为 $\text{base}$，每个元素占用 $\text{size}$ 个存储单元，则第 $i$ 个元素的地址为：$\text{base} + i \times \text{size}$

这个寻址公式只涉及一次乘法和一次加法，在任何计算机上都是常数时间完成的。因此，顺序结构天然具备随机访问能力：访问任意位置的元素，所需时间与元素的位置无关，也与结构的总规模无关。

操作特性

顺序结构上各类操作的时间复杂度，由上述寻址原理和连续存储的物理约束共同决定：

  • 随机访问：时间复杂度为 $O(1)$。这是顺序结构最核心的优势。
  • 尾部插入与删除：在已分配空间的尾部进行操作，仅需一次写入或标记，时间复杂度为 $O(1)$。
  • 中间插入与删除：需要将插入点之后的所有元素向后或向前整体搬移一个位置，以保持连续性。在最坏情况下（在首部操作），需要搬移全部 $n$ 个元素，时间复杂度为 $O(n)$。
  • 空间占用：存储空间大小等于元素个数乘以单个元素大小，无额外指针开销。但需要预先分配一块足够大的连续空间，若预估不足可能触发扩容，扩容时需要将所有元素整体拷贝至新区域。

物理本质

顺序结构的物理本质是用位置的连续性来蕴含逻辑关系的连续性。逻辑上的前驱后继关系，不依赖于任何显式的指针记录，而是直接编码在地址的相邻关系之中。这种以空间位置隐含关系的方式，使它在随机访问场景下拥有无可替代的效率优势，但也正因这种强耦合，导致了它面对频繁插入删除时的搬移代价。

链式结构

定义

链式结构是指数据元素分散存储在内存中互不相邻的区域，每个元素除了存储自身数据外，还显式存储其前驱或后继元素的地址信息，从而在逻辑上串联成一个整体。这些存储地址信息的附加字段称为指针。

链式结构在编程语言层面的最直接体现就是链表。

寻址原理

链式结构中，每个节点只知道其相邻节点的存储位置。要从一个节点到达第 $k$ 个节点，必须以头节点为起点，沿指针逐次向后跳转，共计 $k$ 次。不存在类似顺序结构的通用寻址公式。

因此，链式结构不具备随机访问能力，只能进行顺序访问。

操作特性

链式结构上各类操作的时间复杂度，由逐指针跳转的寻址方式和指针修改的灵活性共同决定：

  • 按位置访问：需要从头部沿指针逐个遍历，最坏情况下需要遍历全部 $n$ 个节点，时间复杂度为 $O(n)$。
  • 给定节点位置的插入与删除：仅需修改被操作节点及其相邻节点的指针指向，不涉及任何数据搬移，时间复杂度为 $O(1)$。
  • 首部插入与删除：仅需修改头指针和首节点的连接关系，时间复杂度为 $O(1)$。
  • 空间占用：每个节点除了存储数据本身，还必须额外存储至少一个指针。若单元素数据量较小，指针开销占比将相当可观。

物理本质

链式结构的物理本质是用显式的指针来记录逻辑关系。逻辑上的前驱后继关系，不再依赖于地址的连续性，而是通过每个节点内部存储的指针显式地表达出来。这种显式的关系记录，使得插入和删除操作只需改变指针的指向，而完全不需要搬移数据，从而获得了插入删除的高效性。但代价是放弃了随机访问能力——因为不再存在类似顺序结构那样的通用寻址公式，对任意元素的访问都必须从起点沿指针链逐一寻找。

对比与联系

顺序结构和链式结构，在本质上是对时间与空间两种资源的不同权衡：

维度 顺序结构 链式结构
随机访问 $O(1)$ $O(n)$
给定位置插入删除 $O(n)$ $O(1)$
首部操作 $O(n)$ $O(1)$
尾部操作 $O(1)$ $O(1)$ 或 $O(n)$
额外空间开销 无 每节点需存储指针
缓存友好性 高 低

这两种结构并非互斥，而是在不同场景下互补。后续介绍的关系结构——线性表、树表、哈希表、图——其物理实现都是在顺序存储和链式存储之间做出选择，或是对二者进行组合。例如，在开放寻址的哈希表中，整体采用顺序结构，但解决冲突的某些策略蕴含着链式结构的思维；在图结构的邻接表中，顶点的集合采用顺序结构组织，而每个顶点的邻居集合则采用链式结构组织。

关系结构

表

线性表

定义

线性表是元素之间具有一对一前驱后继关系的关系结构。除了第一个元素（表头）无前驱、最后一个元素（表尾）无后继之外，每个元素有且仅有一个直接前驱和一个直接后继。这种关系使得线性表中的元素天然排成一个序列。

它的索引键是整数下标。给出下标 $i$，在逻辑层面上即意味着要访问第 $i$ 个元素。至于这个索引访问能否在 $O(1)$ 时间内完成，取决于底层物理实现的选择。

同一套线性关系，可以用两种截然不同的物理方案来落实。这两种方案正是物理实现层所建立的顺序存储与链式存储。

顺序表

在内存中分配一段连续空间，将线性表中的元素按照其逻辑顺序依次存入。第 $i$ 个元素存放在相对于基地址偏移 $i \times \text{size}$ 的位置。这种实现方式称为顺序表。

  • 按位置索引：利用地址公式 $\text{base} + i \times \text{size}$ 直接计算目标地址，与线性表规模无关，时间复杂度为 $O(1)$。这是顺序表的核心优势。
  • 指定位置插入：在位置 $i$ 处插入新元素，需要将原本位于 $i$ 及其之后的所有元素整体向后搬移一个单位，以腾出空位。最坏情况是插入表头，需要搬移全部 $n$ 个元素，时间复杂度为 $O(n)$。
  • 指定位置删除：删除位置 $i$ 处的元素后，需要将其之后的所有元素整体向前搬移一个单位，以填补空缺。最坏情况同样是 $O(n)$。
  • 尾部操作：在表尾插入或删除，不涉及其他元素的搬移，时间复杂度为 $O(1)$。

顺序表依赖预分配的连续空间。当元素数量超出当前容量时，需要重新申请一片更大的空间，将全部已有元素拷贝过去。这一扩容操作的单次代价为 $O(n)$，但发生频率很低——若每次扩容翻倍，则平摊到每次插入的代价仍为 $O(1)$。

链表

将每个元素存放在独立的内存节点中，节点之间不必相邻。每个节点除了存储元素本身，还额外存储指针，指向其前驱或后继节点。通过指针将零散的节点串联成逻辑上的线性序列。这种实现方式称为链表。

根据指针的配置方式，链表有三种基本形态：

  • 单向链表：每个节点仅存储后继指针。只能从表头向表尾方向遍历，无法回溯。
  • 双向链表：每个节点同时存储前驱指针和后继指针。两个方向均可遍历，单节点即可完成插入删除操作。

  • 循环链表：表尾节点的后继指针指向表头（单向循环）或表头与表尾互指（双向循环），形成闭环。

  • 按位置索引：必须从表头出发，沿指针依次跳转 $i$ 次才能到达目标位置。最坏情况需遍历全部 $n$ 个节点，时间复杂度为 $O(n)$。链表不具备随机访问能力，只能顺序访问。
  • 给定节点后的插入：若已知目标位置的节点指针，仅需创建新节点并调整相关指针的指向，不涉及任何数据搬移，时间复杂度为 $O(1)$。对于双向链表，给定节点前的插入同样为 $O(1)$。
  • 给定节点的删除：若已知待删除节点的指针，仅需修改其前驱和后继的指针使其绕过该节点，时间复杂度为 $O(1)$。对于单向链表，删除给定节点本身仍为 $O(1)$，但删除其前驱需要从表头遍历。
  • 首部操作：在表头插入或删除，仅需修改头指针和首节点的连接关系，时间复杂度为 $O(1)$。
  • 尾部操作：对于仅维护头指针的单向链表，尾部插入需要遍历到表尾，为 $O(n)$。若额外维护尾指针，则尾部插入可达 $O(1)$。对于双向链表，尾部操作恒为 $O(1)$。

每个节点必须存储至少一个指针。当单个数据元素体积较小时，指针开销在总存储量中的占比可能相当显著。这是链式存储换取插入删除灵活性所付出的空间代价。

在链表的实际实现中，边界情况——如表头插入、表尾删除、空表操作——往往需要单独的条件判断。因为在边界处，需要修改的是头指针或尾指针，而非某个节点的前驱或后继指针。这导致代码中散布着大量的空指针检查，增加了实现的脆弱性。哨兵节点正是为消除这类边界特判而引入的物理实现技巧。

其做法是：在链表创建之初便额外分配一个或多个不存储实际数据的节点，将其安插在链表的边界位置。根据使用方式的不同，哨兵节点有两种常见形态：

  • 头哨兵：在表头之前安插一个哨兵节点。此后，所有包含实际数据的节点都拥有前驱，表头插入退化为哨兵节点之后的普通插入，不再需要修改头指针。空表也不再表现为空指针，而是表现为只有一个哨兵节点。
  • 头尾双哨兵：在表头之前和表尾之后各安插一个哨兵节点，并令二者互指形成闭环。此时双向链表的所有插入和删除操作，都可以统一为“在两个已知节点之间操作”的模式，不再出现任何修改头尾指针的特殊路径。

引入哨兵节点之后，增删操作的代码路径得到统一，不再需要显式处理空表、表头、表尾等边界条件。其代价是常数级的额外空间（一个或两个节点），以及哨兵节点在遍历时需要略过。哨兵节点不改变链表的基本操作复杂度，它是在物理实现层面对代码结构的优化，而非算法层面的优化。

顺序表与链表的对比

维度 顺序表 链表
按位置索引 $O(1)$ $O(n)$
给定位置插入删除 $O(n)$ $O(n)$（需先找到位置）
给定节点插入删除 不适用 $O(1)$
首部操作 $O(n)$ $O(1)$
尾部操作 $O(1)$ $O(1)$ 或 $O(n)$
额外空间 无 每个节点存储指针
缓存友好性 高（连续内存） 低（节点分散）
边界处理 需处理扩容与空表 哨兵节点可统一代码路径

需要特别指出的是，链表的“给定位置插入删除为 $O(1)$”这一说法，隐含了“已持有待操作位置的节点指针”这一前提。若没有节点指针，仅知道下标 $i$，则必须先花费 $O(n)$ 时间遍历到该位置，总代价仍为 $O(n)$。因此，链表真正擅长的是已知节点位置后的结构修改，而非按位置定位后的结构修改。

数组模拟链表

动机

数组模拟链表是用顺序存储的数组来实现链式存储逻辑的一种物理实现技巧。它用整数下标替代内存指针，在不支持动态内存分配或对内存分配效率有严苛要求的场景下，以数组的形式获得链式结构的灵活插入与删除能力。

标准链表的每个节点通常在堆上动态分配，节点之间通过指针串联。这带来了两个问题：一是动态内存分配本身有时间开销；二是频繁的分配与释放可能导致内存碎片。在某些环境中，动态分配不可用或代价过高。

数组模拟链表的核心思想是：预分配一个大数组作为节点池，每个节点由数组中的一个位置表示，节点之间的连接关系不再靠内存地址，而是靠数组下标来记录。这样，所有的“指针”本质上都是整数，节点的“分配”和“释放”变成对数组下标的简单管理。

单向链表例子
  • val[i]：节点 $i$ 存储的数据值。
  • nxt[i]：节点 $i$ 的后继节点在数组中的下标。若 $i$ 是尾节点，则 nxt[i] = -1。
  • head：链表头节点的下标。空表时 head = -1。
  • cnt：当前已分配节点的数量，也作为新节点的分配下标。初始为 $0$。

此外，通常维护一个空闲链表来复用被删除节点的位置，以避免数组空洞和空间浪费。为简化叙述，以下操作假定节点只分配不释放，或采用惰性删除。完整的内存回收机制将在本节末尾单独讨论。

function init():
    head := -1
    cnt := 0
头插法插入

将新节点插入到链表头部。分配新节点后，令其 nxt 指向当前头节点，再将 head 更新为新节点。

function insert_head(x):
    val[cnt] := x
    nxt[cnt] := head
    head := cnt
    cnt := cnt + 1

时间复杂度为 $O(1)$。

尾插法插入

在链表尾部追加新节点。需先遍历到尾部，再令尾节点的 nxt 指向新节点。若额外维护 tail 指针，可省去遍历，降至 $O(1)$。

function insert_tail(x):
    val[cnt] := x
    nxt[cnt] := -1
    if head == -1:
        head := cnt
    else:
        tail := head
        while nxt[tail] != -1:
            tail := nxt[tail]
        nxt[tail] := cnt
    cnt := cnt + 1

无 tail 指针时，遍历代价为 $O(n)$；维护 tail 指针时，尾部插入为 $O(1)$。

给定节点后插入

在节点 $p$ 之后插入新节点。仅需两步数组操作，完全不需要移动任何已有数据。

function insert_after(p, x):
    val[cnt] := x
    nxt[cnt] := nxt[p]
    nxt[p] := cnt
    cnt := cnt + 1

时间复杂度为 $O(1)$。这是数组模拟链表相比顺序表的核心优势——插入不需要搬移数据。

删除头节点

将 head 指向第二个节点即可。原头节点变为不可达，若需复用其位置，应将其下标回收到空闲链表中。

function delete_head():
    if head == -1:
        return
    head := nxt[head]

时间复杂度为 $O(1)$。

删除给定节点的后继

在节点 $p$ 之后删除一个节点。将 nxt[p] 跳过后继指向其下下个节点。

function delete_after(p):
    if nxt[p] == -1:
        return
    nxt[p] := nxt[nxt[p]]

时间复杂度为 $O(1)$。与指针链表相同，单向链表无法在 $O(1)$ 时间内删除给定节点本身（因为无法访问其前驱）。

遍历

从 head 出发，沿 nxt 逐跳访问，直到 $-1$ 终止。

function traverse():
    curr := head
    while curr != -1:
        // 处理 val[curr]
        curr := nxt[curr]

时间复杂度为 $O(n)$。

双向链表

在单向链表的基础上，为每个节点增设 pre[i]，记录前驱节点的下标。

哨兵节点

与指针链表类似，数组模拟的双向链表也可以引入哨兵节点来统一边界操作。在数组的头尾分别预先分配一个哨兵节点（通常固定在数组的前两个位置），所有实际数据节点插入在两个哨兵之间。此后任何位置的插入和删除都不再需要判断边界条件，代码路径完全统一。

内存回收：空闲链表

当节点被删除后，其数组位置可以被后续插入复用。维护一个空闲链表即可跟踪所有可复用的下标。

  • free_head：空闲链表的头节点下标。初始时，可以将所有数组位置串联起来，或按需回收。
  • 当删除节点 $p$ 时，将其下标插入空闲链表头部：nxt[p] := free_head; free_head := p。
  • 当需要分配新节点时，若空闲链表非空，则从 free_head 取出一个下标使用；否则使用 cnt 并从数组末尾分配。

这一机制完全消除了传统动态链表中 free 操作的系统调用开销，分配和释放都退化为数组下标操作。

与指针链表的对比
维度 指针链表 数组模拟链表
节点分配 动态内存分配（malloc/new） 预分配数组，下标分配
指针类型 内存地址 整数下标
访问后继 指针解引用 数组下标索引
释放节点 系统调用（free/delete） 回收下标至空闲链表
内存连续性 节点零散分布 数组内部连续（按分配顺序）
额外空间开销 每节点存储一个指针 每节点存储一个整数下标
适用场景 通用场景 竞赛、内核、嵌入式
物理实现视角

数组模拟链表是物理实现层“用顺序存储模拟链式存储”的经典范例。它的物理形态是数组——一段连续内存，提供 $O(1)$ 的随机下标访问；但它的逻辑行为是链表——通过 nxt（和 pre）数组串联起各节点，实现 $O(1)$ 的插入删除而不需搬移数据。

优化：跳表

如何在按位置索引、首部操作、给定节点插入删除、二分查找之间取得平衡？跳表的答案是：给有序链表增加多层索引。

在原始的有序单向链表之上，额外构建若干层稀疏的索引。每一层索引本身也是一个有序链表，其中每个节点指向下一层中对应位置的节点。最底层包含全部元素，每向上一层节点数量递减。查找时从顶层开始，沿当前层前进直到下一步会越过目标，然后下降到下一层继续，最终在底层定位到目标元素。

这种多级索引的策略，其物理本质是通过增加冗余指针来换取访问效率的提升。它没有改变数据元素在内存中分散存储的事实，也没有改变底层仍然是链式结构的本质。它只是利用了额外的空间，在原始链表之上构建出了一套快速通道。

  • 查找：从顶层开始，每次下降一层，每层最多前进常数步。若层数为 $O(\log n)$，则期望查找时间复杂度为 $O(\log n)$。
  • 插入：随机选择一层插入，期望时间复杂度为 $O(\log n)$。
  • 删除：删去所有节点，期望时间复杂度为 $O(\log n)$。
  • 空间开销：全部索引节点的数量总和在期望意义下约为 $2n$，空间复杂度仍为 $O(n)$，常数因子较普通链表略大。

跳表是一种链式存储的优化方案，而非新的关系结构。它所在的关系结构仍是线性表——元素之间维持一对一的线性顺序，按位置索引。它所改变的，是在物理实现层面如何组织指针。

树表

定义

树表是表的一个分支，其核心特征是按键的序关系来索引。

与线性表按位置一步到位不同，树表的索引是一个“逐步缩小范围”的过程。给出一个键，从树的根节点出发，每一步根据当前节点与目标键的序关系选择进入某个子树，直至找到目标或确认目标不存在。查找路径本身就是索引的过程。

树表的效率取决于树的高度，而树的高度又取决于维持平衡的能力。树表的增删操作，除了处理节点间的指针，还要维护序关系不被破坏——这是树表操作复杂度的根源。

树表在实现上，通常满足树（或森林）的结构。

树是由 $n$（$n \ge 0$）个节点组成的有限集合。当 $n = 0$ 时称为空树。非空树满足以下条件：

  1. 有且仅有一个称为根的节点。
  2. 其余节点可分为 $m$（$m \ge 0$）个互不相交的有限集合 $T_1, T_2, \dots, T_m$，其中每个集合本身又是一棵树，称为根的子树。

这是一个递归定义：树由根和若干子树构成，子树本身也是树。根是唯一没有前驱的节点；除根外，每个节点有且仅有一个父节点。节点拥有的子树数目称为该节点的度。度为 $0$ 的节点称为叶节点。

基本性质

  • 树的节点数等于所有节点的度之和加 $1$。
  • 树中的边数等于节点数减 $1$。
  • 树中任意两个节点之间有且仅有一条路径。
  • 树是连通且无环的。

相关概念

  • 节点的深度：从根到该节点所经过的边的数目。根的深度为 $0$。
  • 节点的高度：从该节点到最深叶节点所经过的边的数目。叶节点的高度为 $0$。
  • 树的高度：根节点的高度，即树中节点的最大深度。
  • 有序树：子树之间有确定的左右顺序，不能随意交换。
  • 无序树：子树之间没有顺序关系。

森林是由 $m$（$m \ge 0$）棵互不相交的树组成的集合。每棵树有自己独立的根节点，树与树之间没有任何边相连。

树和森林可以相互转换：

  • 删去一棵树的根，所得到的若干棵子树构成一个森林。
  • 给一个森林添加一个根节点，并将森林中各树的根作为新根的子树，则森林变成一棵树。

这一关系在树表的实现中有实际意义。例如，二项堆和斐波那契堆在物理层面维护的便是一个森林——多棵满足堆性质的树的集合。并查集在路径压缩和按秩合并下的物理形态，也是由若干棵父指针树组成的森林。

维护偏序：堆

堆是树表中以偏序关系为索引依据的分支。偏序只保证父节点与子节点之间满足极值关系（父 $\le$ 子，或父 $\ge$ 子），不保证兄弟节点之间、同一层节点之间、或任意两个节点之间的全局有序。这一约束使得极值必然位于树根，因此堆的核心能力是快速获取极值，而非查找任意键。

堆家族包含多种结构，其中最基础、最常用的是二叉堆。二叉堆在物理实现上天然契合顺序存储，是最简洁也最经典的堆实现。

二叉堆
定义

二叉堆是一棵满足以下两个条件的二叉树：

  1. 结构性质：是一棵完全二叉树。即除了最底层外，其余各层均被节点填满；最底层的节点从左到右连续排列，不留空隙。
  2. 堆序性质：每个节点的键值不小于（或不大于）其父节点的键值。

根据堆序的方向，二叉堆分为两类：

  • 小根堆：父节点的键值 $\le$ 子节点的键值。根节点为全局最小值。
  • 大根堆：父节点的键值 $\ge$ 子节点的键值。根节点为全局最大值。不失一般性，下文以大根堆为例展开讨论。

完全二叉树的结构性质使得二叉堆天然适合用顺序存储实现。将完全二叉树的节点按层序遍历的次序编号（根为 1），则节点 $i$ 与其父子节点之间存在确定的下标关系：

  • 父节点：$\lfloor i / 2 \rfloor$
  • 左子节点：$2i$
  • 右子节点：$2i + 1$

因此，只需一个数组 heap[1..capacity]，即可存储二叉堆的全部节点，无需任何指针。数组第 $0$ 位通常留空或作为哨兵。若采用从 $0$ 开始编号，则父节点为 $\lfloor (i-1)/2 \rfloor$，左子为 $2i+1$，右子为 $2i+2$。

这种无指针的顺序存储，使得二叉堆在空间上极为紧凑，且访问父子节点的操作退化为简单的整数运算，常数极小。

核心操作

二叉堆支持两个核心操作，所有其他操作均基于它们实现：

  • 向上调整：当一个节点的键值可能小于其父节点时，沿父节点方向逐层向上调整，直到堆序恢复。
  • 向下调整：当一个节点的键值可能大于其子节点时，沿较小的子节点方向逐层向下调整，直到堆序恢复。
function heap_up(i):
    while i > 1 and heap[i] < heap[parent(i)]:
        swap(heap[i], heap[parent(i)])
        i := parent(i)

向上调整从节点 $i$ 出发，比较其与父节点的键值。若小于父节点，则交换二者并继续向上；否则停止。最坏情况下，节点从叶子上浮至根，路径长度为树的高度，时间复杂度为 $O(\log n)$。

function heap_down(i, n):
    while true:
        biggest := i
        left := 2 * i
        right := 2 * i + 1
        if left ≤ n and heap[left] > heap[biggest]:
            biggest := left
        if right ≤ n and heap[right] > heap[biggest]:
            biggest := right
        if biggest = i:
            break
        swap(heap[i], heap[biggest])
        i := biggest

向下调整从节点 $i$ 出发，比较其与两个子节点中较小者的键值。若大于较小者，则交换并继续向下；否则停止。每次向下走一步，最坏情况从根下沉至叶，时间复杂度为 $O(\log n)$。

建堆

给定 $n$ 个无序元素，构建一个二叉堆。朴素做法是逐个插入，每个元素上滤，总复杂度 $O(n \log n)$。更优的做法是从最后一个非叶节点开始，自底向上逐节点下滤：

function build_heap(A[1..n]):
    for i := floor(n / 2) downto 1:
        heap_down(i, n)

复杂度分析：第 $h$ 层的节点最多下滤 $h$ 步，而该层至多有 $\lceil n / 2^{h+1} \rceil$ 个节点。对所有层求和可得总代价为 $O(n)$。因此，自底向上建堆的时间复杂度为 $O(n)$，优于逐个插入。

插入

将新元素插入二叉堆，需保持完全二叉树的结构性质：

function heap_insert(x):
    n := n + 1
    heap[n] := x
    heap_up(n)

新元素被放在数组末尾（保持完全二叉树形态），然后通过向上调整至正确位置。时间复杂度 $O(\log n)$。

删除极值

删除并返回堆中的最大值（大根堆的根节点）：

function heap_extract_min():
    // 删除并返回最小值
    if n = 0:
        error "heap is empty"
    min_val := heap[1]
    heap[1] := heap[n]
    n := n - 1
    if n > 0:
        sift_down(1, n)
    return min_val

将根节点用数组末尾元素替换（保持完全二叉树形态），然后对新的根向下调整。时间复杂度 $O(\log n)$。

获取极值

获取最大值但不删除：

function heap_get_max():
    if n = 0:
        error "heap is empty"
    return heap[1]

根节点即为最大值，时间复杂度 $O(1)$。这是二叉堆的核心优势，也是偏序关系带来的直接收益——不需要全局排序，就能以常数时间获取极值。

修改键值

修改某个节点 $i$ 的键值为新值 new_val：

function heap_change_key(i, new_val):
    old_val := heap[i]
    heap[i] := new_val
    if new_val < old_val:
        sift_up(i)
    else if new_val > old_val:
        sift_down(i, n)

若新值小于旧值，可能破坏与父节点的偏序关系，执行上滤；若新值大于旧值，可能破坏与子节点的偏序关系，执行下滤。时间复杂度 $O(\log n)$。在应用中，若需频繁修改指定节点的键值（如 Dijkstra 算法中的松弛操作），通常需要额外维护一个从元素到堆中位置的映射，以便快速定位节点 $i$。

复杂度汇总
操作 时间复杂度
建堆（自底向上） $O(n)$
插入 $O(\log n)$
删除极值 $O(\log n)$
获取极值 $O(1)$
修改键值 $O(\log n)$
二叉堆的局限

二叉堆在获取极值上达到 $O(1)$，在插入和删除极值上达到 $O(\log n)$，空间紧凑，实现简洁。但它存在两个主要局限：

  1. 不支持高效合并。将两个二叉堆合并为一个，需要将其中一个堆的所有元素逐个插入另一个堆，代价为 $O(n \log n)$。即便使用自底向上建堆优化，也需要先将两个数组合并再建堆，代价 $O(n+m)$，但会破坏原有堆的内部状态。
  2. 不支持高效的向下调整。

这两项局限正是二项堆、斐波那契堆等更复杂的堆结构试图解决的问题。在后续章节中，我们将展开讨论这些二叉堆的变体，看它们如何通过对物理结构（从单棵树到森林）和调整策略（从即时调整到惰性合并）的改造，突破二叉堆的性能边界。

维护全序：搜索树

定义

全序关系要求树中任意节点的左子树中所有键值均小于该节点的键值，右子树中所有键值均大于该节点的键值。这一约束递归地贯穿整棵树，使得对树进行中序遍历即可得到所有键值的升序序列。与偏序不同，全序关系不仅支持快速获取极值，更支持按任意键值进行精确查找、范围查询、前驱后继查询等操作。

搜索树是以全序关系为索引依据的树表分支。本节围绕三类核心搜索树展开：标准二叉搜索树、红黑树、B树，其中B树采用“预先分裂/合并”策略以保证稳定的访问与修改性能。

标准二叉搜索树
定义

二叉搜索树是一棵二叉树，其中每个节点包含一个键值，且满足：

  • 左子树中所有节点的键值 < 根节点的键值。
  • 右子树中所有节点的键值 > 根节点的键值。
  • 左右子树自身也是二叉搜索树。

该定义不要求绝对平衡，树的形态取决于键值的插入顺序。

查找

从根节点开始，比较目标键值与当前节点键值，若相等则查找成功；若小于则进入左子树；若大于则进入右子树。重复此过程直至找到目标或遇到空子树。

function bst_search(root, key):
    curr := root
    while curr ≠ null:
        if key = curr.key:
            return curr
        else if key < curr.key:
            curr := curr.left
        else:
            curr := curr.right
    return null

查找操作的时间复杂度取决于树的高度。在平衡情况下，高度为 $O(\log n)$；在最坏情况下（如插入有序序列），树退化为链表，高度为 $O(n)$。

查找前驱/后继

前驱节点是小于目标键值的最大节点，查找过程与查找操作类似，不同的是在查找失败时，需要返回当前节点的前驱节点。

function bst_pred(root, key):
    curr := root
    pred := null
    while curr != null:
        if key = curr.key:
            return pred
        else if key < curr.key:
            pred := curr
            curr := curr.left
        else:
            curr := curr.right
    return pred

后继节点同理。

插入

插入新键值时，首先执行一次查找以确定插入位置。若键值已存在，则更新节点或忽略（依具体需求）。若不存在，则将新节点作为叶子插入到查找失败的位置。

function bst_insert(root, key):
    if root = null:
        return new_node(key)
    curr := root
    while true:
        if key = curr.key:
            return root
        else if key < curr.key:
            if curr.left = null:
                curr.left := new_node(key)
                break
            else:
                curr := curr.left
        else:
            if curr.right = null:
                curr.right := new_node(key)
                break
            else:
                curr := curr.right
    return root

插入的时间复杂度同样取决于树高，最坏为 $O(n)$。

删除

删除操作需要分三种情况处理：

  1. 被删节点无子节点：直接删除该节点。
  2. 被删节点有一个子节点：用其子节点替代该节点。
  3. 被删节点有两个子节点：找到该节点的中序后继，用后继节点的键值替换被删节点的键值，然后删除后继节点。因为后继节点至多有一个右子节点，其删除退化为前两种情况。也可以用前驱节点做相应操作。
function bst_delete(root, key):
    // 返回删除后的树根
    root, deleted := delete_node(root, key)
    return root

function delete_node(node, key):
    if node = null:
        return null, false
    if key < node.key:
        node.left, deleted := delete_node(node.left, key)
        return node, deleted
    else if key > node.key:
        node.right, deleted := delete_node(node.right, key)
        return node, deleted
    else:  // 找到待删节点
        if node.left = null and node.right = null:
            return null, true
        if node.left = null:
            return node.right, true
        if node.right = null:
            return node.left, true
        // 有两个子节点：找中序后继
        succ := get_min(node.right)
        node.key := succ.key
        node.right, _ := delete_node(node.right, succ.key)
        return node, true

删除操作的时间复杂度同样为 $O(h)$，$h$ 为树高。

退化问题

标准二叉搜索树的结构完全由插入和删除的顺序决定，没有任何自动平衡机制。当键值以有序序列插入时，树会退化成一条单链，所有操作的时间复杂度恶化至 $O(n)$。因此，实际应用中通常采用能够自动维持平衡的搜索树变体。

红黑树
定义与平衡策略

红黑树是一种自平衡二叉搜索树，通过对每个节点附加颜色属性（红或黑），并施加以下五条约束来保证树的近似平衡：

  1. 每个节点要么是红色，要么是黑色。
  2. 根节点是黑色。
  3. 每个叶节点（NIL 节点，通常视为空节点）是黑色。
  4. 如果一个节点是红色，则它的两个子节点都是黑色（即不允许连续的红节点）。
  5. 从任一节点到其每个叶节点的所有简单路径上，包含相同数量的黑色节点（黑高相等）。

这些约束确保任何一条从根到叶子的路径长度不会超过最短路径的两倍，从而树的高度不超过 $2\log (n+1)$，始终维持在 $O(\log n)$ 级别。

查找

查找操作与标准二叉搜索树完全相同，因为颜色不影响键值的大小关系。时间复杂度为 $O(\log n)$。

插入

红黑树的插入分两步：首先按标准 BST 的方式插入新节点，并将其着色为红色；然后通过一系列的重新着色与旋转操作修复可能被破坏的红黑树性质（主要是修复性质 4——连续红节点）。插入修复的核心思路是将“红色冲突”向上推移，直到可以通过一次旋转或重新着色解决。

插入修复过程循环处理当前节点 x 的父节点为红色的情况。根据父节点是祖父节点的左子还是右子，以及叔叔节点的颜色，分为三种情形。以下以父节点是左子为例：

function rb_insert(root, key):
    root := bst_insert(root, key)
    new_node.color := RED
    fix_insert(root, new_node)
    root.color := BLACK
    return root

function fix_insert(root, x):
    while x ≠ root and x.parent.color = RED:
        if x.parent = x.parent.parent.left:
            uncle := x.parent.parent.right
            if uncle ≠ null and uncle.color = RED:
                // 情形1：叔叔为红 -> 重新着色，上移冲突
                x.parent.color := BLACK
                uncle.color := BLACK
                x.parent.parent.color := RED
                x := x.parent.parent
            else:
                if x = x.parent.right:
                    // 情形2：当前节点是右子 -> 左旋，转为情形3
                    x := x.parent
                    left_rotate(root, x)
                // 情形3：当前节点是左子 -> 右旋并重新着色，修复完成
                x.parent.color := BLACK
                x.parent.parent.color := RED
                right_rotate(root, x.parent.parent)
        else:
            // 对称情况，父节点是祖父节点的右子
            // 类似处理，交换左右旋转方向
    root.color := BLACK

插入修复最多执行 $O(\log n)$ 次重新着色和至多两次旋转，因此插入的整体时间复杂度为 $O(\log n)$。

删除

删除操作首先按标准 BST 的方式删除节点，记录实际被移除或移动的节点及其颜色。若被移除的节点为黑色，则可能破坏性质 5（黑高相等），需要通过一系列修复操作恢复平衡。删除修复比插入修复更为复杂，根据兄弟节点的颜色和子侄节点的颜色，分为多种情形，但同样仅需 $O(\log n)$ 次操作和至多三次旋转。

删除操作的整体时间复杂度仍为 $O(\log n)$。

特点

红黑树通过较弱的平衡条件（与 AVL 树相比）换取了插入和删除时更少的旋转次数，特别适合频繁修改的场景。在 C++ 标准库的 std::map 和 Java 的 TreeMap 等工业实现中被广泛采用。

B树
动机与定义

B树是为磁盘等辅助存储设备设计的自平衡多叉搜索树。其核心思想是增加每个节点的分支数，从而大幅降低树的高度，减少磁盘 I/O 次数。

一棵最小度数为 $t$ 的 B 树满足以下性质：

  • 阶数为 $m = 2t$。
  • 每个节点至多有 $2t - 1$ 个键。
  • 每个节点（除根节点外）至少有 $t - 1$ 个子节点。
  • 有 $k$ 个子节点的内部节点包含 $k-1$ 个键值。
  • 所有叶节点位于同一深度。
  • 节点内的键有序，子节点对应的键值范围由相邻父键值界定。

由于节点内键值有序，B树同样满足全序关系，每个节点内部的键值按升序排列，子节点对应的键值范围由相邻父键值界定。

预先分裂与预先合并

经典的 B 树插入在节点溢出时进行分裂，自底向上传播。这种事后调整可能导致连锁分裂，且单次插入可能触发多次 I/O。

预先分裂/合并策略的核心是：在查找插入位置的过程中，遇到满节点就预先将其分裂；在查找删除位置的过程中，遇到即将低于最小占用（即占用恰好为 $t - 1$）的节点时，预先进行合并或从兄弟节点借调。这样，当实际插入或删除到达叶子时，路径上所有节点都已处于安全状态（不满或不贫），只需进行一次局部修改即可，无需回溯。这保证了操作的 I/O 次数严格与树高成比例，且单次操作只访问一次从根到叶的路径。

查找

查找操作与二叉搜索树的逻辑类似，但在节点内部需要遍历键值列表（通常采用二分查找以提高效率）。从根开始，在节点内部找到目标键值所在的区间，然后进入对应的子树，直至找到目标或到达叶节点。

插入（带预先分裂）

插入新键值 k 时，从根向下遍历，每当遇到一个满节点（键值数 = $2t-1$）时，先将其分裂为两个节点，并将中间键值提升到父节点。这样，继续向下插入时，目标节点一定有空间容纳新键值。最终在叶节点中插入新键值，无需回溯分裂。

function btree_insert(root, key):
    if root.size == 2t - 1:              // 根节点满时需特殊处理
        new_root := new_node()
        new_root.children[0] := root
        split_child(new_root, 0)
        root := new_root
    insert_non_full(root, key)

function insert_non_full(node, key):
    i := find_index(node.keys, key)   // 找到键值应插入的位置
    if node is leaf:
        insert_key_at(node, i, key)   // 直接在叶节点插入
    else:
        // 若目标子节点已满，预先分裂
        if node.children[i].size == 2t - 1:
            split_child(node, i)
            if key > node.keys[i]:
                i := i + 1
        insert_non_full(node.children[i], key)

function split_child(parent, i):
    // 分裂父节点的第 i 个子节点
    child := parent.children[i]
    new_child := new_node()
    // 将 child 的后半部分键值与子节点指针移动到 new_child
    move_keys_and_children(child, new_child, mid_index)
    // 将中间键值提升到父节点
    insert_key_and_child(parent, i, child.mid_key, new_child)

预先分裂确保了在向下递归过程中，所有被访问的节点都不是满的，从而插入只需在叶节点进行一次 $O(m)$ 的插入操作。每次分裂的代价为 $O(m)$，但发生频率随 $m$ 增大而降低。整体插入时间复杂度和 I/O 次数均为 $O(\log_m n)$。

删除（带预先合并/借调）

删除键值时，同样在向下遍历时采用预平衡策略：当发现下一步要进入的子节点键值数恰好为最小占用 $t - 1$ 时，先通过以下方式确保该子节点拥有足够键值（至少 $t$）：

  • 若其某个相邻兄弟节点的键值数大于 $t - 1$，则从兄弟节点“借调”一个键值（通过父节点旋转）。
  • 若兄弟节点均只有最小占用，则将该节点与其中一个兄弟以及父节点的分隔键值合并为一个节点。

经过预平衡，删除过程最终到达叶节点时，该节点一定拥有多于最小占用的键值，可以直接删除而不违反约束。

预先合并/借调使得删除操作同样只需遍历一次根到叶的路径，无需回溯。其时间复杂度为 $O(m \log_m n)$，I/O 次数为 $O(\log_m n)$。

特点与变体

B树通过多叉结构和预平衡策略，将树高控制在极低水平（例如，$m=1024$ 时，数亿条记录仅需 3 层），是关系数据库索引和文件系统的核心数据结构。其变体 B+ 树将所有实际数据存储于叶节点，并在叶节点间增设链表以支持高效范围查询，成为现代数据库索引的事实标准。

维护权重：哈夫曼树

定义

哈夫曼树是树表中以权重为构建依据的分支。与前几类序关系不同，哈夫曼树不关心键值本身的大小关系，也不提供按任意键值查找的能力。它的核心问题是：给定一组带有权重的元素，如何构造一棵二叉树，使得所有元素的带权路径长度之和最小。权重越大的元素，在树中的深度越浅，从而在整体上获得最优的访问代价。

给定 $n$ 个元素，每个元素 $i$ 带有一个正权重 $w_i$。对于一棵有 $n$ 个叶节点的二叉树，每个叶节点对应一个元素，定义该树的带权外部路径长度为：$WPL = \sum_{i=1}^{n} w_i \times d_i$

其中 $d_i$ 为元素 $i$ 所在叶节点的深度（从根到该叶节点经过的边数）。哈夫曼树就是使得 WPL 最小的二叉树。

从物理形态看，哈夫曼树是一棵只有叶节点存储数据的二叉树。内部节点仅作为合并权重的抽象节点，不携带实际数据。权重是构建哈夫曼树的唯一依据——权重越大的元素，被放置在越浅的深度；权重越小的元素，被放置在越深的位置。

构建算法

哈夫曼树的构建采用自底向上的贪心策略。核心思想是反复合并权重最小的两棵子树，将它们的权重之和作为新父节点的权重，直到只剩一棵树。

function build_huffman_tree(elements):
    // elements: 每个元素包含值 value 和权重 weight
    // 初始化森林，每个元素为一棵单节点树
    forest := min_priority_queue()
    for each elem in elements:
        node := new_node(value=elem.value, weight=elem.weight)
        forest.insert(node, key=node.weight)   // 按权重作为优先级

    // 自底向上合并
    while forest.size > 1:
        left := forest.extract_min()   // 取出权重最小的树
        right := forest.extract_min()  // 取出权重次小的树
        // 创建新内部节点，权重为两子树权重之和
        parent := new_node(weight=left.weight + right.weight)
        parent.left := left
        parent.right := right
        forest.insert(parent, key=parent.weight)

    return forest.extract_min()        // 返回唯一的树根

构建过程的核心步骤是：

  1. 初始化：将每个元素视为一棵仅含根节点（也是叶节点）的树，全部放入优先队列，优先级为权重。
  2. 合并循环：每次取出权重最小的两棵树，以它们为左右子树创建一个新的内部节点。该内部节点的权重为两子树权重之和。将新树重新插入优先队列。
  3. 终止：重复合并直至优先队列中只剩一棵树，此树即为哈夫曼树。
操作分析

哈夫曼树主要提供编码生成和解码功能。作为一种静态结构，它不支持插入、删除等动态修改操作。

编码生成

给定哈夫曼树的根节点，对每个元素生成对应的二进制编码。从根节点出发，向左走记为 0，向右走记为 1，遍历到达每个叶节点时，沿途记录的 0/1 序列即为该叶节点对应元素的编码。

function generate_codes(root):
    codes := empty map
    generate_codes_recursive(root, "", codes)
    return codes

function generate_codes_recursive(node, prefix, codes):
    if node is leaf:
        codes[node.value] := prefix
        return
    generate_codes_recursive(node.left, prefix + "0", codes)
    generate_codes_recursive(node.right, prefix + "1", codes)

时间复杂度为 $O(n)$，因为哈夫曼树共有 $2n-1$ 个节点，每个节点访问一次。

解码

给定一段二进制编码序列，从哈夫曼树的根节点出发，遇到 0 走向左子节点，遇到 1 走向右子节点。每到达一个叶节点，输出该叶节点对应的元素，然后回到根节点继续处理剩余序列。

function decode(root, bit_sequence):
    result := []
    curr := root
    for each bit in bit_sequence:
        if bit = 0:
            curr := curr.left
        else:
            curr := curr.right
        if curr is leaf:
            result.append(curr.value)
            curr := root
    return result

解码过程逐位处理，遇到叶节点即输出元素并重置当前节点为根。单个位的处理时间为 $O(1)$，总时间复杂度与序列长度成正比。

复杂度分析
操作 时间复杂度
构建哈夫曼树 $O(n \log n)$
编码生成 $O(n)$
解码（逐位） $O(L)$，$L$ 为编码序列长度

构建过程需要 $n$ 次插入和 $n-1$ 次删除最小与插入操作。若用二叉堆实现优先队列，每次操作 $O(\log n)$，总时间为 $O(n \log n)$。哈夫曼树的节点总数为 $2n-1$，空间复杂度为 $O(n)$。

编码的性质
前缀性

哈夫曼树生成的编码是前缀码——任何一个元素的编码都不是另一个元素编码的前缀。这是由于所有元素均存储在叶节点中，从根到任何一个叶节点的路径不可能是到另一个叶节点路径的前缀。前缀性保证了解码时无需分隔符，逐位解码具有唯一性。

最优性

哈夫曼树在所有可能的二叉树编码方案中，能够最小化加权路径长度。这是由贪心策略的正确性保证的：每次合并当前权重最小的两棵树，最终得到的树必然是最优的。这一性质可用数学归纳法或反证法进行严格证明。

应用

哈夫曼树最经典的应用是数据压缩中的哈夫曼编码。将字符的出现频率作为权重，为高频字符分配短编码，低频字符分配长编码，从而在整体上压缩数据体积。

哈夫曼树是树表家族中以权重为构建依据的特殊成员。与偏序（堆）追求快速极值获取、全序（搜索树）追求高效查找不同，哈夫曼树的全部目标在于优化加权路径长度——让高权重的元素离根更近，低权重的元素离根更远。它不提供动态插入和删除，也不支持按任意键查找。它的价值在于：给定静态的权重分布，构造出整体代价最优的二叉树结构。这正是数据结构设计中的一种经典权衡——牺牲通用性，换取特定目标下的最优性。

维护字典序：Trie树等

维护区间序：区间数据结构

维护空间序：空间数据结构

哈希表

哈希表是表的一个分支，其核心特征是按键的哈希值索引。要理解哈希表的动机，最好从它的理想化前身——直接寻址表开始。

直接寻址表

定义

当键的全集 $U$ 规模较小时，可以直接分配一个大小为 $|U|$ 的数组 $T$，每个位置对应一个键。若键为整数且范围在 $[0, m-1]$，则数组下标即为键本身。这种结构称为直接寻址表。

操作

直接寻址表的操作极其简单：给定键 $k$，直接访问 $T[k]$。每个键在表中拥有唯一确定的槽位，不存在冲突。

function direct_address_search(T, k):
    return T[k]

function direct_address_insert(T, k, v):
    T[k] := v

function direct_address_delete(T, k):
    T[k] := nil

三种操作的时间复杂度均为 $O(1)$。

局限性

直接寻址表要求键的取值空间足够小，以便分配完整的数组。当键空间 $U$ 远大于实际存储的元素数量 $n$ 时，内存浪费严重。此外，若键不是整数（如字符串），无法直接作为数组下标，需要额外的转换机制。更关键的是，当键空间极大（如所有可能的字符串、64 位整数）时，根本无法分配如此庞大的数组。

这些限制直接催生了哈希表——保留直接寻址表常数时间访问的思想，但通过哈希函数将大键空间映射到小表空间。

从直接寻址到哈希表

哈希表的核心思路是：引入一个哈希函数 $h: U \rightarrow {0,1,\dots,m-1}$，将键映射到规模为 $m$ 的数组中。数组的每个位置称为桶。由于 $m$ 远小于 $|U|$，不同的键可能映射到同一个桶，这种现象称为冲突。哈希表的设计，本质上就是在哈希函数质量与冲突解决效率之间做出权衡。

哈希函数

哈希函数将键映射为数组下标。理想的哈希函数应满足：

  • 均匀性：每个桶被映射到的概率大致相等，避免某些桶过度拥挤。
  • 确定性：同一键始终产生相同的哈希值。
  • 高效性：计算哈希值的时间复杂度应为 $O(1)$ 或与键的规模无关的常数级。

常见的哈希函数构造方法：

  • 除留余数法：$h(k) = k \bmod m$。选择 $m$ 为素数可减少规律性冲突。
  • 乘法哈希：$h(k) = \lfloor m \cdot (k \cdot A \bmod 1) \rfloor$，其中 $A$ 为常数（如黄金分割比的倒数）。
  • 针对复合键：将字符串等复合键逐字符处理，如滚动哈希：$h(s) = \sum_{i=0}^{ s -1} s[i] \cdot p^{ s -1-i} \bmod m$。

冲突解决策略

拉链法
实现方式

每个桶维护一个链表（或其他动态容器）。发生冲突时，将新元素追加到对应桶的链表中。桶数组本身采用顺序存储，每个槽存储链表头指针。

操作
  • 查找：计算 $h(k)$ 定位桶，遍历该桶的链表，比较键值直到找到目标或遍历结束。
  • 插入：计算 $h(k)$ 定位桶。若需保证键唯一，先在链表中查找是否已存在；若存在则更新值，否则将新节点插入链表（通常插在头部以简化操作）。
  • 删除：计算 $h(k)$ 定位桶，在链表中找到目标节点后移除，调整指针。
function chained_hash_search(T, k):
    i := h(k)
    curr := T[i]
    while curr != nil:
        if curr.key == k:
            return curr.value
        curr := curr.next
    return nil

function chained_hash_insert(T, k, v):
    i := h(k)
    // 若需保证键唯一，先查找
    curr := T[i]
    while curr != nil:
        if curr.key == k:
            curr.value := v
            return
        curr := curr.next
    // 插入新节点到链表头部
    new_node := create_node(k, v)
    new_node.next := T[i]
    T[i] := new_node

function chained_hash_delete(T, k):
    i := h(k)
    prev := nil
    curr := T[i]
    while curr != nil:
        if curr.key == k:
            if prev == nil:
                T[i] := curr.next
            else:
                prev.next := curr.next
            return
        prev := curr
        curr := curr.next

在均匀哈希假设下，每个链表平均长度为 $\alpha = n/m$，三种操作的期望时间复杂度均为 $O(1 + \alpha)$。

开放寻址法
实现方式

所有元素直接存储在桶数组中，每个桶至多保存一个元素。插入时若目标桶已被占用，则按照一个探查序列依次尝试其他桶，直到找到空位。探查序列必须对每个键唯一确定，保证查找时可沿相同路径定位。

常见的探查方式：

  • 线性探查：$h(k, i) = (h’(k) + i) \bmod m$，其中 $i = 0,1,2,\dots$。实现简单，但容易产生一次聚集——连续被占用的槽会加长后续探查。
  • 二次探查：$h(k, i) = (h’(k) + c_1 i + c_2 i^2) \bmod m$。缓解一次聚集，但可能产生二次聚集——初始哈希值相同的键探查序列完全相同。
  • 双重哈希：$h(k, i) = (h_1(k) + i \cdot h_2(k)) \bmod m$。使用第二个哈希函数决定步长，有效分散探查路径，是开放寻址中的推荐策略。
操作
  • 查找：从 $h(k, 0)$ 开始，沿探查序列依次比较，直到找到目标键或遇到空槽（表示键不存在）。
  • 插入：从初始槽开始探查，遇空槽则插入；若遍历完整个探查序列仍无空位（负载过高或探查序列未能覆盖全表），插入失败。
  • 删除：不能简单将槽置空（会切断探查链），通常使用惰性删除——标记为“已删除”。查找时遇此标记继续探查；插入时可将此标记视作空槽复用。
function open_hash_search(T, k):
    i := 0
    repeat:
        j := h(k, i)
        if T[j] == nil:
            return nil
        else if T[j].key == k and T[j] != DELETED:
            return T[j].value
        i := i + 1
    until i == m
    return nil

function open_hash_insert(T, k, v):
    i := 0
    repeat:
        j := h(k, i)
        if T[j] == nil or T[j] == DELETED:
            T[j] := create_entry(k, v)
            return
        else if T[j].key == k:
            T[j].value := v
            return
        i := i + 1
    until i == m
    error "hash table overflow"

在均匀哈希假设下，开放寻址法查找的期望探查次数为 $\frac{1}{1 - \alpha}$，插入同理。

负载因子与扩容

负载因子定义为 $\alpha = n / m$ 衡量哈希表的填充程度。当 $\alpha$ 超过一定阈值（拉链法通常设为 $1$ 左右，开放寻址法一般设为 $0.7$ 以下），操作效率显著下降。

此时需要扩容：分配一个更大的新表（通常容量翻倍），将原表所有元素重新哈希并插入新表。单次扩容代价 $O(n)$，但因其发生频率随元素数增加而锐减，平摊到每次插入的代价仍为 $O(1)$。

复杂度汇总

操作 拉链法（期望） 开放寻址法（期望） 最坏情况
查找 $O(1 + \alpha)$ $O(1 / (1-\alpha))$ $O(n)$
插入 $O(1 + \alpha)$ $O(1 / (1-\alpha))$ $O(n)$
删除 $O(1 + \alpha)$ $O(1 / (1-\alpha))$ $O(n)$

最坏情况发生在所有键都映射到同一桶（或探查序列一致）时，退化为遍历整个结构。良好设计的哈希函数和适当的负载控制可确保这在现实中极难发生。

与树表的对比

维度 哈希表 树表（全序）
索引方式 哈希值计算 序关系比较
查找期望时间 $O(1)$ $O(\log n)$
有序性 无 有（中序遍历）
范围查询 不支持 支持
前驱/后继 不支持 支持
空间利用率 需扩容预留 节点开销（指针）

哈希表与树表的取舍，本质上是计算与比较的权衡。当只需精确查找、无需维护顺序时，哈希表通常是更优解；当需要有序遍历或范围查询时，树表更合适。

物理实现视角

从物理实现层看，哈希表是顺序存储与链式存储协同的典范：

  • 桶数组：顺序存储，提供 $O(1)$ 随机访问能力，是哈希索引的物理根基。
  • 拉链法：借助链式存储灵活解决冲突，避免聚集问题。
  • 开放寻址法：完全基于顺序存储，通过探查序列模拟链式跳转，缓存友好性更优，但付出更严格的负载控制代价。

直接寻址表是哈希表在键空间极小时的退化情形；随着键空间增长，哈希函数将大空间映射到小空间，冲突解决策略处理映射的歧义。这一演化路径清晰地展示了数据结构设计中“理想化抽象 → 工程现实约束 → 多层次权衡”的典型脉络。

图

定义

图是关系结构中不可索引的一支。与表不同，图中没有“给定键直接定位元素”的机制。要访问一个顶点，必须从已知顶点出发，沿着边逐跳探访。图维护的是顶点对到边的映射——给定两个顶点，可以查询它们之间是否存在边以及边的权值。这一映射是双向可用的：给定顶点对可查询边，给定一个顶点则可遍历其所有邻居。

图 $G = (V, E)$ 由两个集合构成：

  • 顶点集 $V$：图中的所有顶点。
  • 边集 $E$：顶点对之间的连接关系。每条边可以是有向的（有序对 $(u, v)$）或无向的（无序对 ${u, v}$），可以带权也可以不带权。

与线性表和树表不同，图对顶点之间的关系几乎没有拓扑约束。一个顶点可以和任意多个顶点相邻，图中可以存在环路，可以不连通，可以有孤立的顶点。这种“无约束”的特性赋予图极强的表达能力，但也使得图的操作通常比表结构更昂贵。

物理实现

图的物理实现，本质上是在存储边关系。同一张图，可以用两种截然不同的物理方案来存储。

邻接矩阵

用一个 $|V| \times |V|$ 的二维数组 $A$ 存储边信息。若存在从顶点 $i$ 到顶点 $j$ 的边，则 $A[i][j]$ 记录该边的权值（无权图记为 $1$）；若不存在，则记为 $0$ 或 $\infty$。对于无向图，邻接矩阵是对称的。

操作有：

  • 查询边：给定两个顶点 $u$ 和 $v$，直接访问 $A[u][v]$ 即可判定它们是否相邻以及边的权值。时间复杂度 $O(1)$。
  • 遍历邻居：要遍历顶点 $u$ 的所有邻居，需要扫描整行 $A[u][0.. V -1]$，检查每个位置是否非零。无论 $u$ 的实际度数是多少，都必须检查全部 $ V $ 个位置，时间复杂度为 $O( V )$。
  • 插入与删除边：修改 $A[u][v]$ 即可，时间复杂度 $O(1)$。
  • 空间开销：固定为 $O( V ^2)$，与边的数量无关。对于稠密图（$ E \approx V ^2$），空间利用率高；对于稀疏图（$ E \ll V ^2$），空间浪费严重。

邻接表

为每个顶点维护一个链表（或动态数组），存储其所有出边（或所有邻居）。整体结构通常是一个长度为 $|V|$ 的数组，数组的第 $i$ 个元素存储顶点 $i$ 的邻居列表。每个邻居节点除了存储目标顶点编号外，还可附带边的权值。

操作分析：

  • 查询边：给定两个顶点 $u$ 和 $v$，需要在 $u$ 的邻居列表中遍历查找 $v$。若 $u$ 的度数为 $d(u)$，时间复杂度为 $O(d(u))$。最坏情况下 $d(u) = O( V )$。
  • 遍历邻居：直接遍历 $u$ 的邻居列表，每个邻居恰好被访问一次，时间复杂度为 $O(d(u))$，与 $u$ 的实际度数成正比。
  • 插入边：将新邻居追加到列表尾部，时间复杂度 $O(1)$。
  • 删除边：需先在邻居列表中找到目标并删除。对于链表实现，删除节点本身为 $O(1)$，但查找代价为 $O(d(u))$。
  • 空间开销：$O( V + E )$，每条边存储一次（有向图）或两次（无向图）。对稀疏图极其节约空间。

链式前向星

链式前向星是邻接表的一种高效数组实现。它将所有边统一存储在一个全局数组中，用数组下标模拟指针，以静态链表的方式组织每个顶点的出边。其核心思想是：用连续的数组替代零散分配的链表节点，既保留了邻接表遍历邻居时的度数比例优势，又获得了顺序存储的缓存友好性。

数据结构由两个核心数组和一个计数器构成：

  • head[u]：顶点 $u$ 的第一条出边在边数组中的下标。初始时全为 $-1$，表示该顶点尚无出边。
  • to[e]：边 $e$ 指向的目标顶点。
  • nxt[e]：与边 $e$ 共享同一起点的下一条边在边数组中的下标。若 $e$ 是该起点的最后一条出边，则 nxt[e] = -1。
  • cnt：当前已存储的边数，也作为新边的下标（从 $0$ 开始计数）。

对于带权图，增设 wgt[e] 记录边 $e$ 的权值。

操作分析：

  • 查询边：与标准邻接表相同，需要在以 head[u] 为起点的静态链表中逐条遍历查找目标顶点 $v$，时间复杂度为 $O(d(u))$。
  • 遍历邻居：从 head[u] 开始，沿 nxt 指针逐条访问，直至遇到 $-1$ 结束。每条边恰好被访问一次，时间复杂度为 $O(d(u))$。
  • 插入边：新边总是被插入到链表的头部。将 to[cnt] 赋值为目标顶点，nxt[cnt] 指向当前 head[u]，再将 head[u] 更新为 cnt，最后 cnt 自增。这一头插法仅需常数步数组操作，时间复杂度为 $O(1)$。由于边按加入顺序分配下标，后加入的边下标更大，每个顶点的出边链表按插入顺序的逆序排列。 
      function add_edge(u, v):
      to[cnt] := v
      nxt[cnt] := head[u]
      head[u] := cnt
      cnt := cnt + 1
  • 删除边：在静态数组中删除一条边需要修改其前驱的 nxt 指针，但在单向链表中定位前驱需遍历整个链表，代价为 $O(d(u))$。若需频繁删除边，可改用双向链表实现（额外维护 pre 数组），或采用惰性删除（标记边为无效，遍历时跳过）。在大多数图算法（如 DFS、BFS、Dijkstra）中，建图后边集固定不变，删除操作并不常见，这一缺陷在实践中通常可忽略。
  • 空间开销：同标准邻接表，为 $O( V + E )$。三个数组（head、to、nxt）的长度分别为 $ V $、$ E $、$ E $，总计 $ V + 2 E $。与使用动态分配链表节点的标准邻接表相比，链式前向星省去了每个节点存储 next 指针所需的额外内存头部开销，且在内存中数组元素连续排列，缓存局部性显著更优。

稠密图与稀疏图的选择

两种实现方式的取舍，核心依据是图的疏密程度。

维度 邻接矩阵 邻接表 链式前向星
查询边 $O(1)$ $O(d(u))$ $O(d(u))$
遍历邻居 $O(\vert V\vert)$ $O(d(u))$ $O(d(u))$
插入边 $O(1)$ $O(1)$ $O(1)$
删除边 $O(1)$ $O(d(u))$ $O(d(u))$，惰性删除
空间 $O(\vert V\vert^2)$ $O(\vert V\vert + \vert E\vert)$ $O(\vert V\vert + \vert E\vert)$
适用场景 稠密图 稀疏图 稀疏图
当 $ E $ 接近 $ V ^2$ 时，邻接矩阵既有空间效率又有 $O(1)$ 判边的优势。当 $ E \ll V ^2$ 时，邻接表在空间上远优于邻接矩阵，且在遍历邻居时也更为高效——只需访问实际存在的邻居，而非扫描整行。这是物理实现层顺序存储与链式存储两种方案的又一次经典抉择。

链式前向星以数组下标替代指针，以头插法组织静态链表，在完整保留邻接表操作复杂度的同时，消除了动态内存分配的开销，并显著提升了缓存局部性。这一实现不改变邻接表的逻辑本质——它仍然是为每个顶点维护一个邻居列表——只是在物理存储层面将零散的链表节点整合为连续数组，是顺序存储思想在链式结构上的巧妙应用。

图的遍历

图的遍历是从某个起始顶点出发，按照一定规则访问图中所有可达顶点的过程。由于图没有索引，遍历是访问图中元素的根本方式。

深度优先搜索

深度优先搜索沿着一条路径尽可能深入地探访，直到无法继续时回溯。它天然适合用递归或显式栈来实现。

function dfs(G, start):
    visited := empty set
    dfs_visit(G, start, visited)

function dfs_visit(G, u, visited):
    visited.add(u)
    for each v in neighbors(G, u):
        if v not in visited:
            dfs_visit(G, v, visited)
若采用邻接表实现，每个顶点和每条边均被访问常数次，时间复杂度为 $O( V + E )$。若采用邻接矩阵，遍历邻居需要扫描整行，时间复杂度为 $O( V ^2)$。

DFS 的遍历顺序形成一棵深度优先搜索树。通过记录顶点的发现时间和完成时间，DFS 可以用于拓扑排序、强连通分量检测等图论算法。

广度优先搜索

广度优先搜索以层次为序逐层向外扩展。它借助队列来维护待访问的顶点，先进先出的特性保证了先被发现的顶点先被处理。

function bfs(G, start):
    visited := empty set
    queue := empty queue
    visited.add(start)
    queue.enqueue(start)
    while queue is not empty:
        u := queue.dequeue()
        for each v in neighbors(G, u):
            if v not in visited:
                visited.add(v)
                queue.enqueue(v)
同深度优先搜索，邻接表实现为 $O( V + E )$，邻接矩阵实现为 $O( V ^2)$。

BFS 按距离起始点的层数逐层访问。在无权图中，BFS 首次发现一个顶点时所经过的路径即为该顶点的最短路径（边数最少）。这一性质使其成为无权图最短路径问题的基础算法。

深度优先与广度优先的对比

维度 深度优先搜索 广度优先搜索
辅助结构 栈（隐式递归） 队列
访问次序 尽可能深入，再回溯 逐层扩展
无权图最短路径 不保证 保证
适用场景 拓扑排序、连通性、回溯 最短路径、层次遍历

图的分类

图可以按多种维度进行分类，这些分类会影响算法的选择和实现的效率。

按边的方向：

  • 无向图：边 $(u, v)$ 没有方向，$(u, v)$ 与 $(v, u)$ 是同一条边。邻接矩阵是对称的。
  • 有向图：边 $(u, v)$ 有明确的方向，从 $u$ 指向 $v$。$(u, v)$ 与 $(v, u)$ 是两条不同的边。

按边的权值：

  • 无权图**：边仅表示连接关系，不存在权值。最短路径以经过的边数衡量。
  • 带权图：每条边附带一个权值，表示距离、代价、容量等。最短路径以路径上边权之和衡量。

按边的密度：

  • 稠密图：$ E $ 接近 $ V ^2$，适用邻接矩阵。
  • 稀疏图：$ E \ll V ^2$，适用邻接表。

按拓扑性质：

  • 连通图：无向图中，任意两个顶点之间存在路径。
  • 强连通图：有向图中，任意两个顶点之间双向都存在路径。
  • 有向无环图：有向图中不存在环路。支持拓扑排序，是动态规划在图上的基础结构。
  • 完全图：每对顶点之间都有一条边。无向完全图有 $ V ( V -1)/2$ 条边。
  • 二分图：顶点可划分为两个不相交的集合，所有边都跨越在两个集合之间。可用于匹配问题。
  • 树与森林：树是无环连通图，森林是多棵树的集合。图论中的树是无环的，与树表中作为索引工具的树在拓扑上是同一对象。

与关系结构其他分支的关系

图是关系结构中最具一般性的结构。线性表可以看作是一条路径（每个顶点的度数至多为 2 的连通图），树表可以看作是无环连通图加上根节点和序约束。图抹去了这些约束，获得了最强的表达能力，代价是丧失了索引能力和效率保证。

并查集

定义

并查集是一类不能通过键直接索引元素的关系结构。它维护的是元素在集合中的从属关系1。与图不同，它不支持通用的邻居遍历；与表不同，它不提供任何通过键来定位元素的能力。并查集仅支持两种基本操作：查询元素所属集合（find）和合并两个集合（union）。

从映射的视角看，并查集维护的是元素到其所在集合的函数，且这个函数是单向的：可以从元素追溯到集合的代表元，但无法从集合列举其全部成员。

给定 $n$ 个互异的元素，初始时每个元素各自构成一个单元素集合。并查集上定义以下操作：

  • find(x)：返回元素 $x$ 当前所属集合的代表元。代表元是集合中某个选定的元素，且对于同一集合中的任何元素，find 返回相同的结果。
  • union(x, y)：将元素 $x$ 和 $y$ 所在的集合合并为一个集合。若两者已在同一集合中，则不做任何操作。

并查集不关心集合内部元素的顺序，也不提供枚举集合成员的操作（除非额外维护）。

物理实现：父指针森林

并查集最经典的实现是将每个集合表示为一棵父指针树。所有元素存储在一个数组中，每个元素记录其父节点的下标。树根节点的父节点指向自身（或标记为无效值）。整个结构是一个森林。

  • 父指针数组：parent[1..n]，parent[x] 表示元素 $x$ 的父节点。初始时每个元素都是根，即 parent[x] = x。

这种实现完全基于顺序存储——数组提供 $O(1)$ 的随机访问来获取父指针。但逻辑上，它维护的是一个通过指针（下标）串联的链式结构。

操作朴素实现

function naive_find(x):
    while parent[x] != x:
        x := parent[x]
    return x

function naive_union(x, y):
    rx := find(x)
    ry := find(y)
    if rx != ry:
        parent[rx] := ry   // 将一棵树的根挂到另一棵树的根下

在朴素实现中，find 需要沿父指针链向上追溯，最坏情况下退化为 $O(n)$（树退化为链表）。union 的代价由 find 主导。

路径压缩

在执行 find(x) 时，将沿途访问的所有节点直接指向根。这样，后续对同一路径上节点的查询将大幅加速。

function find(x):
    if parent[x] != x:
        parent[x] := find(parent[x])   // 递归向上，同时压缩路径
    return parent[x]

路径压缩不改变树根，只是将查找路径“拍平”。它使得 find 操作的均摊代价急剧下降。

按秩合并

在执行 union(x, y) 时，总是将秩（树的高度上界）较小的树的根挂到秩较大的树的根下，避免树的不必要增高。若两树秩相等，则任选其一作为新根，并将其秩加一。

function union(x, y):
    rx := find(x)
    ry := find(y)
    if rx = ry:
        return
    if rank[rx] < rank[ry]:
        parent[rx] := ry
    else if rank[rx] > rank[ry]:
        parent[ry] := rx
    else:
        parent[ry] := rx
        rank[rx] := rank[rx] + 1

rank 数组记录每棵树的秩。初始时所有节点的秩为 $0$。按秩合并保证了树的高度始终为 $O(\log n)$ 级别；与路径压缩结合后，实际高度几乎为常数。

优化后的复杂度

同时使用路径压缩和按秩合并时，并查集的 find 和 union 操作的均摊时间复杂度为 $O(\alpha(n))$，其中 $\alpha(n)$ 是反阿克曼函数。该函数增长极其缓慢，对于任何可想象的 $n$（如 $n \le 2^{2^{2^{2^{16}}}}$），$\alpha(n) \le 5$。因此，在实际应用中，可以将其视为常数时间。

复杂度汇总

操作 时间复杂度 说明
初始化 $O(n)$ 初始化 parent 和 rank 数组
find $O(\alpha(n))$ 均摊几乎为常数
union $O(\alpha(n))$ 两次 find 加 O(1) 合并

并查集的扩展能力

基础并查集只能合并、无法拆分。但通过增强实现，可以支持更多操作：

  • 支持从集合中移除元素：通过为每个元素建立一个虚点作为父节点。也就是实际元素只作为树的叶子存在。删除后重建虚点作为父节点。
  • 带权并查集：在父指针上附加边权，维护节点与父节点之间的某种关系（如差值、距离），从而能够推导元素间的相对关系。

这些扩展表明，并查集的核心逻辑——维护动态等价关系——是独立于具体物理实现的。无论是数组父指针森林，还是可并树，都只是为了高效支撑 find 和 union 的工程手段。

逻辑结构

操作性质约束型

栈

定义

栈是一种操作性质约束的逻辑结构。它在关系结构层的线性表之上，施加了后进先出的操作限制：所有插入和删除操作只能在线性表的同一端进行。这一端称为栈顶，另一端称为栈底。

从数学视角看，栈对应于自由群的生成与撤销模型。push 是生成元，pop 是其逆元。push(x) 后立即 pop()，系统回归原态。这一代数结构赋予了栈清晰的语义——它在本质上维护的是一条可以撤销的操作历史。

栈 $S$ 支持以下操作：

  • push(x)：将元素 $x$ 压入栈顶。
  • pop()：移除并返回栈顶元素。
  • top()：返回栈顶元素但不移除。
  • empty()：判断栈是否为空。

栈不允许访问栈顶以外的任何元素。这一约束使得栈的操作语义极为纯粹——你只能和最近加入的元素打交道。

物理实现

栈的物理实现有两种方案：基于顺序存储的顺序栈，和基于链式存储的链式栈。二者在操作上完全等价，区别在于底层物理结构的性能特征。

顺序栈

使用数组 s[0..capacity-1] 存储元素，配合一个整数 top_idx 指示栈顶位置。栈底固定在数组的一端，栈顶随操作移动。

  • 栈空时 top_idx = -1。
  • push(x)：top_idx := top_idx + 1; s[top_idx] := x。
  • pop()：x := s[top_idx]; top_idx := top_idx - 1; return x。
  • top()：return s[top_idx]。
  • 栈满时 top_idx = capacity - 1，需扩容（同顺序表的翻倍策略，平摊 $O(1)$）。

除扩容外，所有操作均为 $O(1)$。顺序栈的空间利用率高，无指针开销，缓存友好。它是实践中绝大多数栈实现的底层选择——包括程序的调用栈，本质上就是一片连续内存上的顺序栈。

function seq_stack_init():
    s := new array[INIT_CAPACITY]
    top_idx := -1
    capacity := INIT_CAPACITY

function seq_stack_push(x):
    if top_idx + 1 == capacity:
        resize(capacity * 2)
    top_idx := top_idx + 1
    s[top_idx] := x

function seq_stack_pop():
    if top_idx == -1:
        error "stack underflow"
    x := s[top_idx]
    top_idx := top_idx - 1
    return x

function seq_stack_top():
    if top_idx == -1:
        error "stack is empty"
    return s[top_idx]

function seq_stack_empty():
    return top_idx == -1
链式栈

使用链表实现，栈顶对应链表头部。每个节点包含数据和指向下一节点的指针。

  • push(x)：在链表头部插入新节点。即 new_node.next := head; head := new_node。
  • pop()：移除并返回头节点。即 x := head.val; head := head.next; return x。
  • top()：返回 head.val。

链式栈同样所有操作 $O(1)$。它不需要预分配空间，不会触发扩容，但每元素有指针存储开销，且缓存友好性不如顺序栈。

function link_stack_init():
    head := nil

function link_stack_push(x):
    node := new_node(x)
    node.next := head
    head := node

function link_stack_pop():
    if head == nil:
        error "stack underflow"
    x := head.val
    head := head.next
    return x

function link_stack_top():
    if head == nil:
        error "stack is empty"
    return head.val

function link_stack_empty():
    return head == nil

应用场景

栈的操作约束恰好匹配了程序设计中的若干核心场景：

  • 函数调用与递归：调用栈维护函数的调用序列。每次函数调用压入栈帧，返回时弹出。递归的深度本质上就是调用栈的深度。这直接对应了栈作为自由群的撤销模型——每个函数调用是一个生成元，返回是其逆元。
  • 括号匹配：遇到左括号压栈，遇到右括号时弹栈并检查是否匹配。栈中始终保存着当前未闭合的左括号序列。
  • 表达式求值：中缀转后缀（或直接求值）时，运算符栈维护着等待处理的运算符及其优先级关系。
  • 深度优先搜索：既可以用递归隐式地使用系统调用栈，也可以显式地维护一个栈来模拟递归过程。
  • 撤销操作：编辑器中的撤销（undo）功能是栈最纯粹的应用——每一步操作压入历史栈，撤销时弹出最近的操作用逆操作还原。

不能做什么

栈不提供以下操作：

  • 访问非栈顶元素。
  • 遍历所有元素而不弹出。
  • 按索引或键值查找元素。

如果需要这些操作，说明栈不是正确的选择——应该直接使用线性表，或考虑其他逻辑结构。

变体

双端栈

使用一个数组同时存储两个栈，一个栈底在数组左端向右增长，另一个栈底在数组右端向左增长。两个栈的栈顶相向而行。这样可以充分利用数组空间，一个栈用满时可以从另一个栈的剩余空间中获取扩容。

最小栈

在标准栈的基础上增加一个辅助栈，同步维护当前栈中元素的最小值。push 时，辅助栈压入 min(x, 辅助栈顶)；pop 时，辅助栈同步弹出。这样可以在 $O(1)$ 时间内查询栈中最小元素。这是逻辑结构在基础约束之上进行功能扩展的典型方式——不改变对外暴露的操作接口，但在内部通过额外的辅助结构来丰富操作的能力。

队列

定义

队列是一种操作性质约束的逻辑结构。它在关系结构层的线性表之上，施加了先进先出的操作限制：插入操作只允许在一端（队尾）进行，删除操作只允许在另一端（队头）进行。元素从队尾进入，从队头离开，就像排队等候的队伍，最早到达的最早被服务。

从数学视角看，队列对应于自由幺半群的序列拼接模型。元素是消息序列，运算是拼接，单位元是空队列。先进先出的性质保证了多个生产者产生的消息序列在拼接后，其相对顺序不变。队列本质上是在对“时间”这一序关系进行忠实的建模。

队列 $Q$ 支持以下操作：

  • enqueue(x)：将元素 $x$ 插入队尾。
  • dequeue()：移除并返回队头元素。
  • front()：返回队头元素但不移除。
  • empty()：判断队列是否为空。

队列不允许访问队头和队尾以外的任何元素。两端各有各的职责：一端只进，一端只出。

物理实现

队列的物理实现有两种方案：基于顺序存储的顺序队列（通常以循环队列形式实现），和基于链式存储的链式队列。

顺序队列

最直观的方式是用数组配合两个指针：head 指向队头，tail 指向队尾的下一个空位。

  • enqueue(x)：q[tail] := x; tail := tail + 1。
  • dequeue()：x := q[head]; head := head + 1; return x。

但这一朴素方案存在严重问题：随着入队和出队的进行，head 和 tail 不断右移。即使队列中只有少量元素，tail 也可能触及数组末端导致“假溢出”——数组前端的大量空间已被出队操作释放，却无法被 tail 利用。

循环队列

循环队列正是为解决假溢出而引入的实现技巧。它将数组视为逻辑上的环形：当 head 或 tail 移动到数组末尾时，循环回绕到数组开头。操作通过取模实现：

  • enqueue(x)：q[tail] := x; tail := (tail + 1) mod capacity。
  • dequeue()：x := q[head]; head := (head + 1) mod capacity; return x。

判空与判满：若队列为空，head == tail；若队列为满，(tail + 1) mod capacity == head。因此，循环队列需要牺牲一个槽位来区分空和满，实际容量为 $capacity - 1$。也可通过额外维护一个 size 计数来利用全部槽位。

所有操作均为 $O(1)$，扩容时同样平摊 $O(1)$。顺序循环队列空间紧凑，缓存友好，是实际工程中队列的首选实现。

function circ_queue_init(cap):
    q := new array[cap]
    head := 0
    tail := 0
    capacity := cap

function circ_queue_enqueue(x):
    if (tail + 1) mod capacity == head:
        error "queue is full"
    q[tail] := x
    tail := (tail + 1) mod capacity

function circ_queue_dequeue():
    if head == tail:
        error "queue is empty"
    x := q[head]
    head := (head + 1) mod capacity
    return x

function circ_queue_front():
    if head == tail:
        error "queue is empty"
    return q[head]

function circ_queue_empty():
    return head == tail
链式队列

使用链表实现，队头对应链表头部，队尾对应链表尾部。同时维护 head 和 tail 两个指针，避免尾部插入时的遍历。

  • enqueue(x)：在链表尾部追加新节点。tail.next := new_node; tail := new_node。若队列为空，同时更新 head。
  • dequeue()：移除链表头部节点。x := head.val; head := head.next。若队列变空，同时更新 tail := nil。

链式队列所有操作 $O(1)$，无需预分配空间，不会触发扩容，适用于无法预估队列最大长度的场景。代价是每元素有指针存储开销。

function link_queue_init():
    head := nil
    tail := nil

function link_queue_enqueue(x):
    node := new_node(x)
    node.next := nil
    if tail == nil:
        head := node
        tail := node
    else:
        tail.next := node
        tail := node

function link_queue_dequeue():
    if head == nil:
        error "queue is empty"
    x := head.val
    head := head.next
    if head == nil:
        tail := nil
    return x

function link_queue_front():
    if head == nil:
        error "queue is empty"
    return head.val

function link_queue_empty():
    return head == nil

应用场景

队列的先进先出特性恰好对应了现实世界和计算系统中需要按时间顺序处理的场景：

  • 广度优先搜索：BFS 使用队列维护按层次排列的待访问顶点。先发现的顶点先处理，这保证了无权图上最短路径的正确性。
  • 任务调度：操作系统中的就绪队列、消息队列、请求队列，按到达顺序依次处理任务。队列的本质就是对“等待时间”的公平建模。
  • 缓冲区：数据流中的生产者-消费者模式。生产者将数据块 enqueue，消费者 dequeue 处理。循环队列特别适合此场景，因为生产者与消费者各自维护一个指针，无需同步整个数据结构。
  • 树的层序遍历：从根节点开始，逐层将子节点入队，按层次顺序处理节点。

不能做什么

队列不提供以下操作：

  • 访问非队头或队尾的元素。
  • 按索引或键值查找元素。
  • 在队列中间插入或删除元素。

如果需要在队列中支持这些操作，应该考虑双端队列，或退回使用线性表。

变体

双端队列

将队列的操作约束放宽，允许在两端都可以进行插入和删除。它同时具备了栈和队列的部分能力，将在之后单独讨论。

优先队列

队列的出队顺序不再是按到达时间，而是按优先级。优先级最高的元素总是最先出队。这已经不属于操作约束的范畴，而是将底层关系结构从线性表换成了堆（偏序树）。优先队列将在之后单独讨论。

单调队列

在队列的基础上维护元素的单调性（如队头到队尾单调递增）。enqueue 时，若新元素会破坏单调性，则从队尾弹出元素直到新元素可以加入。dequeue 时正常操作。单调队列常用于滑动窗口最值问题，它通过对入队操作施加额外的单调约束，使得查询当前窗口中最大/最小值的操作降为 $O(1)$。这是逻辑结构在基础约束之上进行功能扩展的又一个示例。

栈与队列的联系和对比

对比

维度 栈 队列
约束 LIFO（后进先出） FIFO（先进先出）
操作端 同一端 各一端
底层关系结构 线性表 线性表
数学对象 自由群（生成与撤销） 自由幺半群（序列拼接）
核心应用 递归、撤销、括号匹配 广度优先搜索、任务调度
顺序实现 顺序栈 循环队列

栈和队列是逻辑结构层中操作性质约束最基础的两个成员。它们都基于线性表构建，都不改变元素之间的前驱后继关系，只通过在何处插入、何处删除这一操作约束，就派生出了完全不同语义的数据类型。这种“同构异义”的现象，正是逻辑结构独立于关系结构的价值所在——同一副骨架，套上不同的约束，就成了截然不同的工具。

队列模拟栈

核心思想

模拟的关键在于维护一个“永远让最后加入的元素站在队头”的队列。这样，当调用 pop 时，从队头取出的自然就是最晚入队的元素。

实现方式：单队列模拟

使用一个队列 $Q$。每次 push(x) 时，先将 $x$ 入队。然后，将队列中排在 $x$ 之前的所有元素依次出队并立即重新入队。经过这一轮循环，$x$ 就排到了队头，而其余元素的相对顺序保持不变。

function queue_stack_push(x):
    n := Q.size
    Q.enqueue(x)
    // 将 x 之前的所有元素移到 x 之后
    for i := 1 to n:
        Q.enqueue(Q.dequeue())

function queue_stack_pop():
    return Q.dequeue()

function queue_stack_top():
    return Q.front()

function queue_stack_empty():
    return Q.empty()
  • push 操作：时间复杂度 $O(n)$，因为需要将原有的 $n$ 个元素逐个出队再入队。
  • pop 操作：时间复杂度 $O(1)$，直接从队头取出。
  • top 操作：时间复杂度 $O(1)$，直接查看队头。
实现方式：双队列模拟

也可以使用两个队列 $Q_1$ 和 $Q_2$ 来分摊代价，但操作复杂度与单队列方案一致。两种方案的核心原理相同——通过队列的循环操作，将最新元素推到队头。

复杂度分析
操作 单队列模拟
push $O(n)$
pop $O(1)$
top $O(1)$

队列模拟栈是一种教学意义上的构造。它证明了仅凭队列的先进先出操作，完全有能力表达栈的后进先出语义。但在实际应用中，若需要栈的行为，直接使用栈是显然更高效的选择。

栈模拟队列

核心思想

栈是后进先出。如果把一叠元素从一个栈倒入另一个栈，顺序就会完全颠倒。颠倒两次，就回到了原始顺序。栈模拟队列正是利用这一性质。

维护两个栈：in_stack 负责接收新元素（队尾），out_stack 负责输出元素（队头）。enqueue 时，直接将元素压入 in_stack。dequeue 时，若 out_stack 非空，直接从其栈顶弹出；若 out_stack 为空，则将 in_stack 中的所有元素逐个弹出并压入 out_stack，然后再从 out_stack 弹出。经过这一次“倾倒”，最先进入 in_stack 的元素暴露在 out_stack 的栈顶，恰好就是队列的队头。

实现
function stack_queue_enqueue(x):
    in_stack.push(x)

function stack_queue_dequeue():
    if out_stack.empty():
        if in_stack.empty():
            error "queue is empty"
        // 将 in_stack 全部倒入 out_stack
        while not in_stack.empty():
            out_stack.push(in_stack.pop())
    return out_stack.pop()

function stack_queue_front():
    if out_stack.empty():
        if in_stack.empty():
            error "queue is empty"
        while not in_stack.empty():
            out_stack.push(in_stack.pop())
    return out_stack.top()

function stack_queue_empty():
    return in_stack.empty() and out_stack.empty()
  • enqueue 操作：时间复杂度 $O(1)$，直接压入 in_stack。
  • dequeue 操作：每个元素至多在“倾倒”过程中被移动一次——从 in_stack 到 out_stack，然后再从 out_stack 弹出。因此，平摊时间复杂度为 $O(1)$。
  • front 操作：平摊时间复杂度 $O(1)$，理由同上。
复杂度分析
操作 双栈模拟
enqueue $O(1)$
dequeue 平摊 $O(1)$
front 平摊 $O(1)$

栈模拟队列不仅是一个理论构造，它在实际工程中有真实的应用背景。许多纯函数式语言中，由于不可变数据结构的限制，队列通常就以“一对栈”（称为“双栈队列”或“配对队列”）的形式实现。其平摊常数的性能保障，使得这一构造在实践中完全可用。

理论意义

队列模拟栈与栈模拟队列，共同证明了一个深刻的原理：逻辑结构的能力，取决于其操作约束所定义的语义，而非其底层的物理实现或关系结构本身。 仅凭先进先出的基本操作，可以完整表达后进先出的语义；反之亦然。两种结构的差异不是计算能力的差异，而是对特定操作模式效率偏好的差异——栈天然擅长维护“最近历史”，队列天然擅长维护“时间顺序”。理解这种差异，正是为特定问题选择正确数据结构的关键。

元素性质约束型