当前位置：首页 > news >正文

块状链表的长度

news 2026/6/6 9:33:43

0.引入

块状链表就是一个链表，每个节点指向一个空间大小为 \(L\) 的数组。一个链表长度为 \(M\)，数组空间大小为 \(L\) 的块状链表能装至多 \(ML\) 个元素。

给定参数 \(M\) 和 \(L\)，在块状链表中查找一个元素的复杂度是 \(O(M)\)，朴素插入和删除一个元素的复杂度是 \(O(M+L)\)

给定总元素数量 \(n\)，我们希望固定合适的 \(L\)，让 \(M+L\) 保持尽可能小，从而让插入和删除更快。接下来介绍一种维护块状链表的策略，在这个策略下可以保证 \(M\le \lceil 3\frac{n}{L} \rceil\) 恒成立，并且这里的 \(3\) 不可改进，因此只需让 \(\lceil 3\frac{n}{L} \rceil+L\) 尽可能小，固定 \(L=\lfloor \sqrt{ 3n }\rfloor\) 即可。

注：这里的 \(3\) 不可改进，是说不存在 \(c<3\) 和 \(m>0\) 使得 \(M\le \left\lceil c \frac{n}{L} \right\rceil+m\) 恒成立

1.维护策略

为了完整描述这个策略，只需要考虑块状链表上的两个操作：插入和删除。

在某个节点中插入元素时，如果节点指向的数组未满，就直接在该数组中插入元素即可。

在某个节点中插入元素时，如果节点指向的数组已满，我们不得不开辟一个新的节点。此时，执行分裂操作，把数组中的元素尽可能均分到原节点和新节点，然后插入那个元素。这样操作的结果是，元素个数为 \(L\) 的节点 \(B\) 变成了元素个数分别为 \(\left\lfloor \frac{L+1}{2} \right\rfloor\) 和 \(\left\lceil \frac{L+1}{2} \right\rceil\) 的两个相邻节点 \(B_{1},B_{2}\)

在某个节点中删除元素时，先在数组中删除这个元素，如果删除后节点为空则直接删除该节点。然后考虑该节点是否可以和左相邻的节点合并，如果数组元素个数之和 \(\le L\)，那么就合并两个数组的元素到一个节点。否则，再考虑是否可以和右相邻的节点合并。

2.直观

直觉上，“分裂” 和 “合并” 让数组不会过于空。具体地，“分裂” 让分裂出的数组都至少有 \(\frac{L}{2}\) 那么大，而 “合并” 让相邻的小数组被合成更大的数组。它们分别暗示了两个理想中的全局性质：

任意一个数组的元素个数都 \(\ge \frac{L}{2}\)
任意两个相邻数组的元素个数和都 \(>L\)

性质 \(1\) 和性质 \(2\) 的任何一个成立都能让数组的平均元素个数控制在 \(\frac{L}{2}\) 级别，从而使 \(M\) 控制在 \(2 \frac{n}{L}\) 附近。可惜的是，这无法做到。性质 \(1\) 不能在 “分裂” 操作后保持，性质 \(2\) 不能在 “删除” 操作后保持。

实际上，把数组的平均元素个数控制在 \(\frac{L}{2}\) 级别是不可能的，可以构造这样的例子：

首先，通过不断插入得到这样的链表，数组元素个数序列如下：

\[(L,L,L,L,L,\cdots) \]

然后，对奇数位置反复删除至 \(1\)：

\[(1,L,1,L,1,\cdots) \]

最后，对所有的 \(L\) 都插入一次，造成分裂：

\[\left( 1, \left\lfloor \frac{L+1}{2} \right\rfloor, \left\lceil \frac{L+1}{2} \right\rceil, 1, \left\lfloor \frac{L+1}{2} \right\rfloor, \left\lceil \frac{L+1}{2} \right\rceil, 1,\cdots \right) \]

此时，数组的平均元素个数为 \(\frac{L+1}{3}\)，大约为 \(\frac{L}{3}\)，当元素个数趋于无穷时，可以看出 \(\frac{L}{3}\) 是不可改进的

幸运的是，\(\frac{L}{3}\) 已经是最坏情况了！我们接下来就给出 \(M\le \lceil 3\frac{n}{L} \rceil\) 的证明！

3.证明

引理 1：任何时刻，对于链表上连续的两个节点，其数组元素个数分别为 \((A,B)\)，则 \(A\lt \frac{L}{2}\) 和 \(B < \frac{L}{2}\) 不能同时成立

证明：

对数组操作进行数学归纳：

base case：当链表为空时，命题平凡成立。

case 1：如果最后一步是不产生分裂的插入，那么设受到影响的区间是 \((A,B,C)\)，它变为了 \((A,B+1,C)\)，考虑新的二元组 \((A,B+1),(B+1,C)\)，都保持了目标性质，这是因为 \(B+1>B\)

case 2：如果最后一步是产生分裂的插入，那么设受到影响的区间是 \((A,B,C)\)，可以知道 \(B=L\)，它变为了 \((A,B_{1},B_{2},C)\)，考虑新的二元组 \((A,B_{1}),(B_{1},B_{2}),(B_{2},C)\)，都保持了目标性质，这是因为 \(B_{1}\ge \frac{L}{2},B_{2}\ge \frac{L}{2}\)

注意，这里的 \(A\) 和 \(C\) 可以为空，例如当 \(A\) 为空时，应理解为 \(B\) 是链首节点，区间 \((B,C)\) 变为了 \((B_{1},B_{2},C)\)，新的二元组有 \((B_{1},B_{2}),(B_{2},C)\)，其他情形和接下来的证明类似，不再强调

case 3：如果最后一步是不产生合并的删除，那么设受到影响的区间是 \((A,B,C)\)，它变为了 \((A,B-1,C)\)，考虑新的二元组 \((A,B-1),(B-1,C)\)，都保持了目标性质，这是因为不不发生合并说明 \(A+(B-1)>L\ge L,(B-1)+C>L\ge L\)

case 4：如果最后一步是产生合并的删除，那么设受到影响的区间是 \((A,B_{1},B_{2},C)\)，它变为了 \((A,B,C)\)，考虑新的二元组 \((A,B),(B,C)\)，都保持了目标性质，这是因为 \(B>B_{1},B>B_{2}\)

证毕。

引理 2：任何时刻，对于链表上连续的三个节点，其数组元素个数分别为 \((A,B,C)\)，如果 \(B\ge \frac{L}{2}\)，则 \(A+B<L\) 和 \(B+C< L\) 不能同时成立

证明：

对数组操作进行数学归纳：

base case：当链表为空时，命题平凡成立。

case 1：如果最后一步是不产生分裂的插入，那么设受到影响的区间是 \((X,A,B,C,Y)\)，它变为了 \((X,A,B+1,C,Y)\)，考虑新的三元组 \((X,A,B+1),(A,B+1,C),(B+1,C,Y)\)，都保持了目标性质，这是因为 \(B+1>B\)

case 2：如果最后一步是产生分裂的插入，那么设受到影响的区间是 \((X,A,B,C,Y)\)，可以知道 \(B=L\)，它变为了 \((X,A,B_{1},B_{2},C,Y)\)，考虑新的三元组 \((X,A,B_{1}),(A,B_{1},B_{2}),(B_{1},B_{2},C),(B_{2},C,Y)\)，都保持了目标性质，原因如下：

\((X,A,B_{1})\) 保持了性质，是因为 \(B_{1}\ge \frac{L}{2}\)，若 \(A\ge \frac{L}{2}\)，则 \(A+B_{1}\ge L\)
\((A,B_{1},B_{2})\) 和 \((B_{1},B_{2},C)\) 保持了性质，是因为 \(B_{1}+B_{2}=L+1\ge L\)
\((B_{2},C,Y)\) 保持了性质，是因为 \(B_{2}\ge \frac{L}{2}\)，若 \(C\ge \frac{L}{2}\)，则 \(B_{2}+C\ge L\)

case 3：如果最后一步是不产生合并的删除，那么设受到影响的区间是 \((X,A,B,C,Y)\)，它变为了 \((X,A,B-1,C,Y)\)，考虑新的三元组 \((X,A,B-1),(A,B-1,C),(B-1,C,Y)\)，都保持了目标性质，这是因为不发生合并说明 \(A+(B-1)>L\ge L,(B-1)+C>L\ge L\)

case 4：如果最后一步是产生合并的删除，那么设受到影响的区间是 \((X,A,B_{1},B_{2},C,Y)\)，它变为了 \((X,A,B,C,Y)\)，考虑新的三元组 \((X,A,B),(A,B,C),(B,C,Y)\)，都保持了目标性质，原因如下：

\((X,A,B)\) 和 \((B,C,Y)\) 保持了性质，是因为 \(B>B_{1},B>B_{2}\)
\((A,B,C)\) 保持了性质，是因为由引理 1，\(B_{1}\) 和 \(B_{2}\) 必有一个 \(\ge \frac{L}{2}\)，不妨设是 \(B_{1}\)，那么由于 \((A,B_{1},B_{2})\) 满足性质，可以知道 \(A+B_{1}\ge L\) 或 \(B_{1}+B_{2}\ge L\)，而 \(B=B_{1}+B_{2}-1\)，如果 \(A+B_{1}\ge L\)，则 \(A+B>A+B_{1}\ge L\)，如果 \(B_{1}+B_{2}\ge L\)，则 \(A+B\ge 1+B=B_{1}+B_{2}\ge L\)