408八股——数据结构

发表于 更新于 分类于 ， 阅读次数：

哈希表

散列表(哈希表) - 散列函数, 冲突处理, 平均查找长度(ASL)_哔哩哔哩_bilibili

image-20260713145331002

哈希表的底层核心其实就是一个普通的一维数组。为了把任意类型的 Key（比如字符串、对象、大整数）塞进数组里，它设计了三步走的流水线：

  1. 计算哈希值（Hash Code）： 当你要存入一个键值对（如 Key="Zhang", Value=99）时，系统先把 Key 喂给一个哈希函数（Hash Function）。这个函数会把抽象的 Key 变成一个很大且杂乱无章的整数（Hash Code）。
  2. 映射数组下标（Index）： 算出来的 Hash Code 通常非常大，超出了我们数组的长度。于是算法通过取模运算（Index = HashCode % 数组长度），把这个大整数强行约束在当前数组的合法下标范围内。
  3. 原地存取： 找到了精准的 Index 后，直接把 Value 扔进对应的数组格子 array[Index] 里。查找时同理，顺着这个公式一算，瞬间直达格子取值。

哈希冲突

哈希表看似完美，但它有一个致命的数学Bug——哈希冲突。 因为互联网上的 Key 是无穷无尽的，而我们的数组长度是有限的。根据鸽巢原理，只要数据足够多，必然会出现两个完全不同的 Key，经过哈希函数算完之后，指向了同一个数组下标。

image-20260713145710340

1. 拉链法 / 链地址法（Chaining）—— 工业界绝对的标配

  • 做法：数组的每个格子里面存的不直接是 Value，而是一个链表的头指针。
  • 冲突处理：如果新来的 Key 算出了相同的下标，别慌，直接把这个新数据挂在当前格子的链表末尾（或头部）。
  • 现代进化（红黑树化）：在 Java 的 HashMap 中，如果同一个格子里冲突的数据太多，链表变得太长（默认超过 8），为了防止查找效率退化，长链表会自动扭转退化为一棵红黑树，把最坏查找复杂度从 O(n) 死死卡在 O(log n)。

2. 开放寻址法（Open Addressing）—— 内存紧凑型选秀

  • 做法：不引入链表等额外结构，所有数据必须老老实实呆在数组里。
  • 冲突处理：如果算出的格子被人占了，新来的数据就顺着数组往后挪，寻找下一个空着的格子。
    • 线性探测：挨个格子往后看（+1, +2, +3...），谁空着我坐谁家。
    • 平方探测：按跳跃式往后看（+1², +2², +3²...），防止扎堆聚集。

线性表

线性存储结构和链式存储结构的优缺点

比较维度 顺序存储 (数组) 链式存储 (链表)
物理内存分布 必须严格连续 随机分散，通过指针维系
随机访问能力 强（支持下标 O(1) 直达） 弱（必须从头顺序查找 O(n)）
插入/删除元素 慢（需大面积搬移数据 O(n)） 快（只需修改指针连线 O(1)）
容量扩展性 固定大小，扩容成本极高 动态按需增减，无限延展
空间利用率 高（100%存数据，无冗余） 较低（需额外存储指针开销）
CPU Cache 友好度 高（局部性原理完美利用） 低（容易引发缓存缺失）

图

邻接表和邻接矩阵

一、 邻接矩阵（Adjacency Matrix）

image-20260714110657901

邻接矩阵的底层灵魂非常纯粹：用一个 V × V 的二维数组来直接表示顶点之间有没有边。

假设图中有 N 个顶点，我们就开辟一个 N × N 的大方阵 matrix[N][N]：

  • 无权图：如果顶点 i 到顶点 j 有边，则 matrix[i][j] = 1；如果没有边，则 matrix[i][j] = 0。
  • 带权图（网）：如果顶点之间有边，格子里就直接存边的权值（如距离、花费）；如果没有边，通常用一个无穷大（∞ 或 INT_MAX）来占位。

优点：

  1. 极速查找任意边（O(1) 时间）：你想知道顶点 3 和顶点 5 之间有没有连接？直接一行代码 if(matrix[3][5] == 1) 就能在常数时间内瞬间秒杀，读写性能极高。
  2. 计算图的度（Degree）很方便：对于无向图，想知道顶点 i 连接了几个邻居，只需要整整齐齐地把第 i 行（或第 i 列）的所有元素加起来就行了。
  3. 矩阵乘法的数学外挂：邻接矩阵可以直接进行矩阵运算。例如，把邻接矩阵进行平方（A2），得到的矩阵中 matrix[i][j] 的值，恰好代表顶点 i 到顶点 j 长度为 2 的路径有多少条。这在图的高级算法（如动态规划、图神经网络 GCN）里是非常强悍的数学工具。

缺点：

  1. 恐怖的空间开销（O(V2) 空间）：不管图里的边多还是少，只要顶点数是 V，就必须死板地申请 V2 个格子。
  2. 不擅长处理“稀疏图（Sparse Graph）”：如果一个图有 1 万个顶点（V = 10000），但一共只有 2 万条边（E = 20000）。邻接矩阵会强行申请 1 亿个格子，其中 99.98% 的格子里面存的都是 0。这种对内存的暴殄天物被称为稀疏矩阵的空间浪费。

二、 邻接表（Adjacency List）

image-20260714121749888

为了外挂拯救稀疏图下的内存崩溃，科学家们引入了邻接表。它的核心设计类似于哈希表的拉链法：用一个一维数组存下所有顶点，数组的每个格子代表一个顶点，后面挂一个单链表，链表里密密麻麻串联的，全都是它的亲密邻居。

构成组件：

  1. 顶点表（主干数组）：一个大小为 V 的普通数组，用来存放顶点的基本信息以及指向它第一个邻居的链表头指针。
  2. 边表（单链表）：链表中的每个节点代表一条真实的边，节点内部通常包含：[邻居顶点的下标 | 边的权值(可选) | 指向下一个邻居节点的指针 next]。

优点：

  1. 极高的空间利用率（O(V + E) 空间）：它是典型的“给多少钱办多少事”。有多少个顶点就建多大的数组，有多少条边就动态申请多少个链表节点。绝不为不存在的边浪费一个字节的内存，完美通杀稀疏图。
  2. 找所有人所有的邻居极其丝滑：如果算法需要从顶点 i 出发去遍历它的所有邻居（比如在进行 BFS 广度优先搜索 或 DFS 深度优先搜索 时），邻接表只需要顺着第 i 个格子的单链表一路往后走，指针指到谁就是谁，没有任何做无用功的空扫描。

缺点：

  1. 查找特定边时被迫变慢：如果你冷不防地想查一下“顶点 3 和顶点 999 之间有没有边？”，在邻接表里你必须先定位到数组的第 3 格，然后开始遍历它后面的长链表，最坏时间复杂度退化为 O(V)（或者顶点的最大度数）。
  2. 计算“入度（In-degree）”很痛苦（针对有向图）：在有向图中，邻接表默认只能轻松查到“我指向了谁（出度）”。如果想知道“谁指向了我（入度）”，必须把整个图里所有顶点的链表全量扫描一遍才能统计出来（工程上的解法是额外再建一棵逆邻接表）。

连通

一、 无向图的连通：只要能走到就行

image-20260714104452655

在无向图中，边的方向是双向通行的。它的连通概念非常纯粹：

  1. 连通（Connected）

如果从顶点 u 到顶点 v 之间存在至少一条路径，我们就说这两个顶点是连通的。

  1. 连通图（Connected Graph）

如果一个无向图中，任意两个顶点都是连通的（从任何一点出发，都能顺着边走到其他任何一点），那这个图就叫连通图。

  1. 连通分量（Connected Component）

这是一个极高频的八股概念，定义叫做：无向图的极大连通子图。

  • 物理直觉：就是一个孤立的“朋友圈”。这个圈子内部所有人都能互通，但圈子外面的人绝对进不来。一个非连通的无向图，就是由多个互不相交的连通分量组合而成的。
  • 关键词：极大。意思是“能加进来的邻居都加进来了，再多加一个点，它就不连通了”。

二、 有向图的连通：方向决定一切（强连通 vs 弱连通）

image-20260714105814954

有向图的边是单行道，所以连通的难度直接翻倍。

  1. 强连通（Strongly Connected）

对于一对顶点 u 和 v，如果既存在一条从 u → v 的有向路径，同时也存在一条从 v → u 的有向路径（也就是两人能礼尚往来，互相直达），这才叫强连通。

  1. 强连通图（Strongly Connected Graph）

有向图中，任意两个顶点之间都是强连通的。

  • 最少边数考点：一个含有 n 个顶点的有向图，如果它是强连通图，最少需要 n 条边（刚好围成一个封闭的大环）。
  1. 强连通分量（Strongly Connected Component, SCC）

有向图的极大强连通子图。在工业界（如社交网络作弊团伙挖掘、网页 PageRank 计算），寻找 SCC 是非常核心的业务。

  1. 弱连通图（Weakly Connected Graph）

如果一个有向图本身不是强连通的，但如果你耍赖把所有有向边的箭头全部抹去，强行当成无向图来看，它变成了一个连通图。那原图就叫做弱连通图。

生成树

image-20260714110112649

一棵树如果想自称是原图 G 的“生成树”，它作为子图必须严格满足以下四个几何约束：

  1. 顶点全覆盖：它必须包含原图的全部 n 个顶点，一个都不能少。
  2. 边数死死锁死（n − 1 条）：如果原图有 n 个顶点，它的生成树必须且只能有 n − 1 条边。
    • 多一条边：必然会在线路中长出闭环（形成环路，就不能叫“树”了）。
    • 少一条边：图就会瞬间断裂，碎成不连通的两块。
  3. 绝对连通且无环：树的天然属性，任意两点之间有且仅有一条路径。
  4. 极小连通子图：这是最容易考的定义题。它是保证图连通的边数最少的子图。

💡 避坑小锦囊：一棵连通图的生成树不是唯一的。同一个图，只要你砍掉不同的冗余边，就能组合出形态各异的生成树，但它们的共同点是都拥有 n 个点和 n − 1 条边。

最小生成树-Prim(普里姆)算法和Kruskal(克鲁斯卡尔)算法

维度 Prim (普里姆) Kruskal (克鲁斯卡尔)
核心出发点 顶点（从一个点向外滚雪球） 边（每次挑最便宜的边拼接）
底层数据结构 邻接表/邻接矩阵 + 优先队列 (小顶堆) 边集数组 + 并查集 (DSU)
中间状态 过程中始终只有一棵逐渐变大的树 过程中会诞生很多孤立的小树林，最终合并
时间复杂度 O(Elog V) 或 O(V2) O(Elog E)
首选战场 稠密图（E ≈ V2，边很多） 稀疏图（E ≈ V，边很少）

  • 为什么稀疏图选 Kruskal？

    因为稀疏图里边很少（E 很小），Kruskal 第一步的边排序速度像闪电一样快。

  • 为什么稠密图选 Prim？

    因为稠密图里边多得像乱麻。Kruskal 对几十万条边排序会直接卡死；而 Prim 滚雪球的次数只和顶点数 V 相关，能极高地避开边多带来的开销。

什么是最小生成树？

一棵树想要被冠以“最小生成树”的称号，必须在带权无向连通图中严丝合缝地满足以下四个底层特征：

  1. 顶点全覆盖（不漏一人）：

    它必须包含原图中的全部 N 个顶点，任何一个节点都不能掉队。

  2. 边数死死卡死（不多不少）：

    对于 N 个顶点的图，最小生成树必须且只能包含 N − 1 条边。

    • 多一条：必然会在网络中滋生出冗余的“闭环”，电网就会短路。
    • 少一条：电网就会断裂，部分城市会沦为孤岛。

  3. 连通且无环：

    任意两个城市之间有且仅有一条通信路径，结构极其精简。

  4. 总权值最小：

    这是它灵魂的一点。在原图所有能挑出的、满足上述三条的“生成树”集合中，这 N − 1 条边的权值相加之和是最小的。

Prim

image-20260714123401412

Kruskal

image-20260714123659703

最短路径

Dijkstra(迪杰斯特拉)算法

image-20260714124227164

Floyd

image-20260714125331686
image-20260714125258805
image-20260714130111691

排序

稳定性问题

image-20260713143137551

快排时间复杂度什么情况下退化

场景一：数据已经“完全有序”或“完全逆序” + 选用边界元素做基准（最经典八股）

假设你有一组已经排好序的数据 [1, 2, 3, 4, 5]，而你的快排代码每次都盲目地选用第一个元素（或最后一个元素）作为基准值（Pivot）。

  • 第一次划分：选 1 为基准。比 1 小的在左边（0个），比 1 大的在右边（4个：[2, 3, 4, 5]）。
  • 第二次划分：对右边递归，选 2 为基准。左边 0 个，右边 3 个（[3, 4, 5]）……
  • 代价：由于每次切一刀，都只能切掉一个孤零零的元素，递归的深度直接从 log n 飙升到了 n。总共需要进行 n 次划分，每次划分要遍历剩下的一切设备，总比较次数就是 $n + (n-1) + (n-2) + ... + 1 = \frac{n(n+1)}{2}$，时间复杂度无悬念退化为 O(n2)。此外，过深的递归层数还极易引发栈溢出（Stack Overflow）。

场景二：数据中包含“大量高度重复”的元素

如果一个数组里有几万个数据，但它们的值全都一模一样（或者绝大多数都一样），例如：[5, 5, 5, 5, 5]。

  • 在传统的单向朴素划分机制（如 Lumoto 划分）下，算法很容易把所有等于基准值的元素全部强行划归到某一个子阵营（比如全部推到右边）。
  • 这就会再次造成左边 0 个、右边 n − 1 个的极端偏瘫结构，导致时间复杂度同样瞬间崩塌至 O(n2)。

1. 随机化选取基准（Randomized Quick Sort）

  • 做法：不再死板地选第一个或最后一个元素，而是每次在当前区间内随机盲抽一个元素作为 Pivot，并与边界元素交换后再执行划分。
  • 物理意义：这样把快排的命运从“看输入数据的脸色”变成了“看随机数发生器的脸色”。哪怕输入数据故意设计得再有序，在随机抓取下，每次都能抓到极端的概率降到了无限趋近于 0，在概率学上强行把期望复杂度死死锁在 O(nlog n)。

2. 三数取中法（Median-of-Three）

  • 做法：这是现代工业库（如许多 C++ std::sort 的底层变体）最青睐的做法。每次挑选当前区间的最左端、最右端和正中间这三个数，进行简单排序后，挑出大小排在第二的那个“中位数”作为基准值。
  • 物理意义：只要选出的不是极端极大或极小值，就能稳稳保证每一次切下去，左右两边多多少少都有人，绝不会长成单链表。

3. 三路快排（3-Way Quick Sort）针对重复元素

  • 做法：改变划分规则，将数组强行切成三块：【小于基准值】 | 【严格等于基准值】 | 【大于基准值】。
  • 物理意义：划分完毕后，中间那一整块【严格等于基准值】的大量重复元素在接下来的递归中直接被忽略，不需要再参与任何排序。算法只需继续向左、向右递归。这个外挂让快排在面对大量重复数据时，时间复杂度不仅不会退化，反而会大幅超越 O(nlog n)，甚至逼近 O(n)。

树

二叉搜索树(二叉排序树)(二叉查找树)

数据结构合集 - 二叉搜索树(二叉排序树)(二叉查找树)_哔哩哔哩_bilibili

左子树铁律：若它的左子树不为空，则左子树上所有节点的值都必须严格小于它的根节点的值。

右子树铁律：若它的右子树不为空，则右子树上所有节点的值都必须严格大于它的根节点的值。

递归性质：它的左、右子树也必须各自是一棵完美的二叉排序树。

image-20260713153227527

平衡二叉树

平衡二叉树(AVL树)_哔哩哔哩_bilibili

一棵二叉树想要自称是“平衡二叉树”，必须同时满足以下两个条件：

  1. 它首先必须是一棵二叉搜索树（BST）：左小右大。
  2. 核心平衡条件（严格限高）：任意节点的左子树和右子树的高度差的绝对值不能超过 1。

核心概念：平衡因子（Balance Factor, BF）

在工程实现中，我们用“平衡因子”来量化一棵树是否失衡：

平衡因子 (BF) = 左子树的高度 − 右子树的高度

  • 只要整棵树中所有节点的平衡因子只能是 −1、 0、 1，这棵树就是平衡的。
  • 一旦某个节点的平衡因子绝对值大于 1（变成了 ±2），这棵树就拉响了“失衡警报”，必须立刻进行结构调整。
image-20260712202501173

平衡二叉树（AVL 树）是在二叉搜索树的基础上，通过限制任意节点左右子树高度差绝对值不超过 1来维持动态平衡的结构。它利用 LL/RR/LR/RL 四种旋转机制防止树退化为单链表，从而稳定保证了 O(log n) 的极速查找时间复杂度。

二叉搜索树性能退化的场景

二叉搜索树（BST，Binary Search Tree）的性能退化，核心原因只有一句话：当数据的插入顺序过于规律，导致二叉树失去了分叉的“金字塔”结构，硬生生退化成了一条“单链表”。

在理想的满二叉树或完全二叉树状态下，BST 的查找、插入、删除时间复杂度都是完美的 O(log n)。但在以下几种经典的工程场景中，它会直接发生灾难性的退化：

1. 严格递增或递减插入（最经典的面试八股场景）

如果你按照从小到大（或从大到小）的顺序，连续往一棵空的二叉搜索树里插入数据，例如：[1, 2, 3, 4, 5]。

  • 插入 1：作为根节点。
  • 插入 2：比 1 大，挂在 1 的右边。
  • 插入 3：比 1 大，比 2 大，挂在 2 的右边……

最终这棵树会毫无悬念地长成一根严格向右倾斜的单链表。

  • 代价：此时的树高直接等于节点总数 n。树的左右分支极其不平衡，每次查找末尾元素都要从头遍历到尾，时间复杂度直接从 O(log n) 惨烈退化成了 O(n)。

2. 交替边界插入（长成蛇形“之”字树）

如果插入的数据总是在当前数据集的极大值和极小值之间反复横跳，例如输入顺序为：[5, 1, 4, 2, 3]。

  • 5 是根节点，1 挂在 5 的左边，4 挂在 1 的右边，2 挂在 4 的左边……
  • 最终整棵树虽然不是笔直的，但它会形成一条没有多余分叉的“之”字形长蛇。由于它本质上依然是一条单链表，树高并没有降低，因此性能同样会退化为 O(n)。

红黑树

image-20260712203650441

规则

规则一：每个节点或者是红色的，或者是黑色的。

规则二：根节点永远是黑色的。

规则三：每个叶子节点（指的是最底层的空节点 NIL 或 NULL）都是黑色的。

规则四：如果一个节点是红色的，则它的两个子节点必须是黑色的。（也就是说：绝不能有两个连续的红节点搭在一起）。

规则五：对任意一个节点而言，从该节点到其所有后代叶子节点的宣告路径上，所包含的黑色节点数量必须完全相同（这个数量被称为黑色高度）。

B树

为什么需要B树

image-20260713090702105

减少磁盘 I/O 块的读取：

在底层设计中，B树的一个节点的大小通常会直接设置为操作系统的一个磁盘页（Page，一般是 4KB 或者是其整数倍）。

这样，每次进行一次磁盘 I/O，就能把一个节点里成百上千个键值一口气全部读进内存。

极度矮胖：

假设一个节点能存 100 个键值。一棵 3 层的 B树，最多可以容纳 100 × 100 × 100 = 100 万个数据！而要把 100 万数据存在红黑树里，高度可能有接近 20 层。

20次磁盘 I/O vs 3次磁盘 I/O，在性能上这就是几百倍的降维打击。

核心定义（以 m 阶 B树为例）

image-20260713100131224

B树是一种多路自平衡的搜索树。所谓“m 阶”，指的是一个节点最多能长出 m 个分叉（子节点）。

一棵标准的 m 阶 B树必须满足以下严苛的平衡性质：

  1. 节点多值性：每个节点内部不再只存一个 key，而是存一组排好序的多个键值（Keys）*和对应的*数据指针。
  2. 分支数的约束：
    • 根节点至少有 2 个子节点（除非整棵树只有根节点一个）。
    • 除了根节点外，所有内部节点至少有 ⌈m/2⌉ 个子节点，最多有 m 个子节点。
  3. 键值与分支的关系：如果一个节点包含了 k 个键值，那它必定拥有 k + 1 个子节点分叉。
    • 例如：节点里存了 [10, 20] 两个数，那它下面就会分出 3 个树枝，分别对应  < 10、 10 ∼ 20、  > 20 的数据区间。
  4. 绝对的叶子对齐：所有叶子节点都必须在同一层。B树不允许任何一个分支掉队，它是绝对完美的平衡。

B+树

数据结构合集 - B+树_哔哩哔哩_bilibili

为什么需要B+树

痛点一：B树节点“带货”导致分叉数受限，树还不够矮

💥 B树的问题：

在 B树中，每个节点（无论是根节点、内部节点还是叶子节点）里面都同时存储了键值（Key）和对应的真实数据（Data/Record）。

我们知道，计算机从磁盘读写的基本单位是磁盘页（Page，通常为 4KB 或 16KB）。因为真实数据（比如一条包含几十个字段的会员信息）占用的字节数非常大，导致一个 16KB 的磁盘页节点里面塞不下几个键值，分叉数（阶数 m）严重受限。分叉数一少，当数据量暴涨到千万级时，B树的高度还是会不可避免地抽高，从而引发更多的磁盘 I/O。

✨ B+树的进化（上层纯路由）：

B+树做出了极其激进的阶级分化：非叶子节点变成了纯粹的“导航路由”，里面只存 Key 和指针，绝对不带任何 Data 拖油瓶！所有的真实数据被悉数打包，全部踩压、堆放在最底层的叶子节点中。

  • 工程红利：由于非叶子节点不占地方，一个 16KB 的页可以疯狂塞入上千个 Key，分叉数瞬间暴涨。这使得 B+树达到了极致的“矮胖”，通常一棵 3 到 4 层的 B+树，就能轻松存储 上千万甚至数亿条 级别的数据。在大海捞针时，最多只需要 3 到 4 次磁盘 I/O。

痛点二：B树进行范围查询时，存在恐怖的“全树回溯”

💥 B树的问题：

在日常的 SQL 业务中，范围查询（比如 WHERE age BETWEEN 18 AND 25）或全表扫描是高频刚需。

如果用 B树，算法在树里定位到 18 后，想要找下一个比它大的数，必须频繁地在树的各个父子、兄弟节点之间上下回溯、进行复杂的左中右中序遍历。在磁盘文件系统里，这种跨节点的上下跳跃会导致大量跨页的随机磁盘 I/O，磁头疯狂寻道，性能瞬间雪崩。

✨ B+树的进化（底部双向链表）：

B+树在最底层放了一个物理大外挂：所有叶子节点之间，通过指针紧密地首尾相连，织成了一条环环相扣的双向链表。

  • 工程红利：算法通过根节点一路向下，做一次 O(log n) 的单点定位找到 18 所在的叶子节点。接下来的事情变得无比丝滑——不需要再回溯哪怕一次上层节点，直接顺着底部的双向链表一路横向往后进行线性指针扫描，直到看到 25 为止。随机 I/O 瞬间变成了极其高效的顺序 I/O。

痛点三：B树的查询效率上下抖动，不够稳定

💥 B树的问题：

在 B树中，因为每个节点都有数据，如果运气好，要找的主键刚好在根节点，那 O(1) 的时间就能高潮返回；如果运气不好在最底层的叶子节点，则需要 O(log n)。这在内存中无所谓，但在磁盘 I/O 敏感的数据库系统里，这会导致网络响应时间发生明显的抖动和不稳定。

✨ B+树的进化（路径一视同仁）：

在 B+树中，非叶子节点没有数据，任何数据的查询路径长度都是完全相同的——都必须老老实实从根节点走到最底层的叶子节点。

  • 工程红利：这种“一视同仁”保证了每一次 SQL 查询的响应时间都极度稳定、可预测，为高并发系统的吞吐量提供了坚实的下限保障。

b树和b+树的区别

image-20260713131105692
对比维度 B树 (B-Tree) B+树 (B+ Tree)
数据（Data）存储位置 所有节点（根节点、内部节点、叶子节点）都存数据。 仅最底层的叶子节点存储数据，非叶子节点只存索引键（Key）和指针。
叶子节点间关系 彼此孤立，没有指针连接。 首尾相连，通过双向链表紧密连接。
相同数据量下的树高 相对较高（节点因带货导致分叉数少）。 极其矮胖（非叶子节点能容纳更多Key，分叉数极大）。
单点查询效率 不稳定。运气好 O(1) 在根节点找到，运气差 O(log n)。 极其稳定。任何查询都必须一路走到最底层叶子节点，稳定在 O(log n)。
范围查询 / 全表扫描 代价极高。需要在树的各层节点之间反复上下回溯（中序遍历）。 极其丝滑。只需单点定位到起点，然后顺着底部链表横向线性扫描。
Key 的唯一性 树中所有 Key 不重复。 非叶子节点的 Key 会在子节点中重复出现（起区间路由作用）。
image-20260713131702330

并查集

image-20260714131103966
image-20260714131243444

堆（Heap）

完全二叉树

铁律一：除了最底层外，其余各层必须是满的。

如果一棵树有 h 层，那么从第 1 层到第 h − 1 层，每一层的节点数都必须达到最大值。例如第 1 层有 1 个，第 2 层有 2 个，第 3 层有 4 个，第 4 层有 8 个……绝不能有任何一个空位。

铁律二：最底层的节点必须“绝对靠左对齐”。

最底层的节点可以不满，但所有节点必须从左到右连续排列，中间绝对不能有任何空隙。只有左边塞满了，才能去填右边。

堆

它是一棵动态的、绝对对齐的完全二叉树，它的终极使命是让你在 O(1) 的时间内瞬间拿到当前这堆数据里的“最大值”或“最小值”。

一棵树想要称自己为“堆”，必须同时满足以下两个条件：

  1. 结构性质（完全二叉树）：除了最底层外，其余各层都是满的；且最底层的节点都连续集中在左边。这个性质决定了堆有一个绝妙的外挂——可以用连续的一维数组来直接存储，根本不需要指针。
  2. 堆次序性质（Heap Property）：任意节点的值都大于或等于（或小于或等于）其子节点的值。

根据堆次序的不同，堆分为两大流派：

  • 大顶堆 / 最大堆（Max-Heap）：根节点是整棵树的最大值，任何父节点的值都大于等于它的孩子。
  • 小顶堆 / 最小堆（Min-Heap）：根节点是整棵树的最小值，任何父节点的值都小于等于它的孩子。

网站推荐

题库 - 八股精