题目TC: 18.2-4

分析

因为插入B树的数字是递增的，所以只有最右边一条链的节点上可能有多于一个key。
我们先关注整个B树最右下角的节点，称之为$A$。
当插入到第$3$个数字时，$A$（这时候也是根）满了，然后在插入下一个数字$4$的时候，其分裂，变成

再插入$4$变成

注意到一个节点分裂之后（在把插入的数字塞到节点里之前），节点里还会剩下$1$个key。所以一个节点从上一次满到下一次满，需要插入两个数字。
即$A$在$n=3, 5, 7, \dots$的时候是满的。
$n=5$:

$n=6$:

$n=7$:

每个节点是在它满了之后，插入下一个数字时分裂的，即$A$在插入$n=4, 6, 8, 10, 12, 14, 16\dots$之后分裂。

接下来考虑$A$的父亲，称为$B$，它在$n=4$即$A$首次分裂之后出现。

$A$每分裂一次，相当于给$B$插入一个数字。即$n=4$时，给$B$插入第一个数字，$n=6$时，给$B$插入第二个数字…
所以在$A$分裂三次之后（$n=8$之后），$B$就（第一次）满了。
接下来每给$B$插入两个数字，即$A$每分裂两次，$B$又会变满一次。所以$B$是满的当$n=8, 12, 16, 20, 24, \dots$的时候。
同样地，$B$也是在它满了之后，插入下一个数字时分裂的，即$B$在插入$n=9, 13, 17, 21, 25\dots$之后分裂。

再考虑$B$的父亲$C$。
$B$分裂一次相当于给$C$插入一个数字。所以与上面类似，在$n=17, 25, 33, \dots$的时候$C$是满的，在$n=18, 26, 34, \dots$的时候$C$分裂。

…

以此类推。
对于每一个节点，它的右孩子分裂三次之后，在插入下一个数字的时候它第一次分裂。
之后它的右孩子每分裂两次，在插入下一个数字的时候它分裂一次。
用归纳法，得到第$i$个节点（第$1$个节点是$A$，第$2$个节点是$B$…）两次分裂的间隔是$2^i$个数字。
再用$S_i$​表示第$i$个节点第一次分裂的时间，有
$S_1=4$ $S_i=S_{i-1}+2\times2^{i-1}+1$
进而$S_i=2^{i+1}+i-1$

统计数量

如何统计插入$n$个数字后的节点数量$T_n$​？
初始数量为$T_0 = 1$，即空树有一个节点。
对于之前我们考虑的每一个节点，它第一次作为根分裂的时候，分裂一次节点数量加$2$（它自己一分为二，且加了另外一个根），之后它就是不是根了，分裂一次数量加$1$。

所以当$S_i \le n$的时候，第$i$个节点对最终的数量有贡献，且贡献为$1$加上其分裂次数，我们知道第$i$个节点在插入$S_i, S_i + 2^i, S_i+2\times 2^i, S_i+3\times 2^i, \dots$时分裂，故分裂次数为其中小于等于$n$的数字的个数，等于
$\left\lfloor\frac{n-S_i}{2^i}\right\rfloor+1$
则贡献为
$\begin{aligned} 1+\left(\left\lfloor \frac{n-S_i}{2^i} \right\rfloor + 1 \right) &= \left\lfloor \frac{n-S_i}{2^i}\right\rfloor + 2\\ &=\left\lfloor\frac{n-2^{i+1}-i+1}{2^i}\right\rfloor + 2\\ &=\left\lfloor\frac{n-i+1}{2^i}\right\rfloor \end{aligned}$
所以总的节点数量是1加上各个$i$贡献之和，即
$\begin{aligned} T_n &= 1+\sum_{i=1}^\infty[S_i \le n]\left(\left\lfloor\frac{n-i+1}{2^i}\right\rfloor\right)\\ &=1+\sum_{i=1}^{2^{i+1}+i-1 \le n}\left\lfloor\frac{n-i+1}{2^i}\right\rfloor\\ &=1+\sum_{i=0}^{2^{i+2}+i\le n}\left\lfloor\frac{n-i}{2^{i+1}}\right\rfloor \end{aligned}$

一般问题

在解决这个问题的时候，我们并没有依赖minimum degree为$2$这个特性，所以我们可以用同样的方法解决minimum degree为任意$t \ge 2$的情形。
类似上面的方法，用归纳法，第$i$个节点分裂两次的间隔是$t^i$个数字。
且第一个节点第一次分裂的时间为插入第$2t$个数字的时候，第$i$个节点第一次分裂是在第$i-1$个节点分裂$2t-1$次后插入下一个数字的时候，即
$S_1 = 2t$ $S_i = S_{i-1} + (2t-2)t^{i-1} +1$
进而
$\begin{aligned} S_i &= i-1 + 2t + \sum_{j=1}^{i-1}(2t-2)t^j\\ &=i+1 + \sum_{j=0}^{i-1}(2t-2)t^j\\ &=i+1+(2t-2)\sum_{j=0}^{i-1}t^j\\ &=i+1+(2t-2)\frac{t^i-1}{t-1}\\ &=2t^i+i-1 \end{aligned}$

对于$S_i \le n$的节点，其对答案的贡献为
$\begin{aligned} \left\lfloor\frac{n-S_i}{t^i}\right\rfloor+2 &= \left\lfloor\frac{n-2t^i-i+1}{t^i}\right\rfloor+2\\ &=\left\lfloor\frac{n-i+1}{t^i}\right\rfloor \end{aligned}$
所以总的节点数为
$\begin{aligned} T_n &= 1 + \sum_{i=1}^\infty [S_i \le n]\left(\left\lfloor\frac{n-i+1}{t^i}\right\rfloor\right)\\ &=1 + \sum_{i=1}^{2t^i+i-1 \le n}\left\lfloor\frac{n-i+1}{t^i}\right\rfloor \end{aligned}$