3.3.5 #

解答 #

注：英文版原文使用的是 “ignore the order of the subtrees”，也就是忽略子树的顺序。

我们将 N=6 时的树形简记为 [{3}, {2, 2, 3}]，代表根结点是一个 3-结点，第二层有两个 2-结点和一个 3-结点。

一个 N=6 的示例：

// 'D', 'G', 'K', 'O', 'S', 'Y'

 |--GO--|
D   K   SY

考虑插入元素的两种效用，一种是使 2-结点变成 3-结点（当前结点或者它的父结点）；另一种是使树高增加，被插入元素的 3-结点（及其父 3-结点）变回 2-结点。这两种操作的顺序不影响最后的树形。

于是 N=7 时，我们有两种树形。

[{3}, {2, 3, 3}]（插入到某个 2-结点）。

// 'D', 'G', 'K', 'O', 'S', 'Y', 'L'

// before
 |--GO--|
D   K   SY

// after
 |--GO--|
D   KL   SY

[{2}, {2, 2}, {2, 2, 2, 2}]（插入到 3-结点，变成满二叉树）。

// 'D', 'G', 'K', 'O', 'S', 'Y', 'Q'

// before
 |--GO--|
D   K   SY

// after
       |--------O--------|
 |--G--|                 |--S--|
D       K               Q       Y

N=8，对于 N=7 时的第一种树形，如果向 3-结点插入，会触发树高增加，结果相当于向第二种满二叉树底层 2-结点中的某一个插入元素后的树形。向第一种树形的 2-结点插入则会变成一个全部由 3-结点构成的 2-3 树。

注：可以把这里插入到 2-结点的操作看作是插入到 3-结点的一种“拖延”，它只是延后了树高增加的变换，但对最后的树形没有影响。

[{3}, {3, 3, 3}]（插入到唯一的 2-结点）

// 'D', 'G', 'K', 'O', 'S', 'Y', 'L', 'A'

// before
 |--GO--|
D   KL   SY

// after
 |--GO--|
AD   KL   SY

[{2}, {2, 2}, {2, 2, 2, 3}]（插入到满二叉树底部任意一个 2-结点）

// 'D', 'G', 'K', 'O', 'S', 'Y', 'Q', 'Z'

// before
       |--------O--------|
 |--G--|                 |--S--|
D       K               Q       Y

// after
       |--------O--------|
 |--G--|                 |--S--|
D       K               Q       YZ

N=9，和 N=8 时类似，对于 N=8 时的第一种树形，插入底层任意一个 3-结点都会触发平衡，等同于满二叉树底部两个 2-结点各插入一个元素的树形。考虑第二种树形最底层各结点插入元素后的树形即可。

[{2}, {2, 2}, {2, 2, 3, 3}]（插入到 3-结点同侧 2-结点）

// 'D', 'G', 'K', 'O', 'S', 'Y', 'L', 'A', 'C'

// before
 |--GO--|
AD   KL   SY

// after
       |--------G--------|
 |--C--|                 |--O--|
A       D               KL       SY

[{2}, {2, 2}, {2, 3, 2, 3}] （插入到 3-结点对侧 2-结点）

// 'D', 'G', 'K', 'O', 'S', 'Y', 'L', 'A', 'J'

// before
 |--GO--|
AD   KL   SY

// after
       |--------K--------|
 |--G--|                 |--O--|
AD       J               L       SY

[{2}, {2, 3}, {2, 2, 2, 2, 2}]（插入到 3-结点）

// 'D', 'G', 'K', 'O', 'S', 'Y', 'Q', 'Z', 'X'

// before
       |--------O--------|
 |--G--|                 |--S--|
D       K               Q       YZ

// after
       |--------O--------|
 |--G--|                 |--SY--|
D       K               Q   X   Z

N=10

[{2}, {2, 2}, {2, 3, 3, 3}] （插入到 2-结点）

// 'D', 'G', 'K', 'O', 'S', 'Y', 'L', 'A', 'C', 'B'

// before
       |--------G--------|
 |--C--|                 |--O--|
A       D               KL       SY

// after
       |--------G--------|
 |--C--|                 |--O--|
AB       D               KL       SY

[{2}, {2, 3}, {2, 2, 2, 2, 3}]（插入到 3-结点下的 2-结点）

// 'D', 'G', 'K', 'O', 'S', 'Y', 'Q', 'Z', 'X', 'P'

// before
       |--------O--------|
 |--G--|                 |--SY--|
D       K               Q   X   Z

// after
       |--------O--------|
 |--G--|                 |--SY--|
D       K               PQ   X   Z

[{2}, {2, 3}, {2, 3, 2, 2, 2}]（插入到 2-结点下的 2-结点）

// 'D', 'G', 'K', 'O', 'S', 'Y', 'Q', 'Z', 'X', 'J'

// before
       |--------O--------|
 |--G--|                 |--SY--|
D       K               Q   X   Z

// after
       |--------O--------|
 |--G--|                 |--SY--|
D       JK               Q   X   Z