3.3.3 # 解答 # 题目给出的序列就可以，如下（只有根结点的 2-3 树的高度是 0，以此类推）： S ES |--E--| A S |--E--| AC S |--E--| AC HS |--ES--| AC H X |--ES--| AC HM X SEACHXM 排序后是 ACEHMSX，符合条件的一种情况即为 AC 为左子结点，HM 为中间结点，X 为右侧结点，ES 为根节点。 也可以是其他的模式，总共有 2880 种符合条件的组合（result.txt），共三种模式，结果如下： 864 |--CM--| A EH SX 1152 |--EM--| AC H SX 864 |--ES--| AC HM X 可以观察到树的形状是没有变化的，只是键在各结点中的分布有些变化。 代码 # using System; using System.IO; using BalancedSearchTree; var input = "ACEHMSX"; var output = File. ...
3.3.4 # 解答 # 一棵高度为 $h$ 的完美二叉树有：$1 + 2 + 2^2 + … + 2^{h}= 2^{h+1} - 1$ 个结点，反向得到 $N$ 个结点的完美二叉树高度为 $\log_2{(N+1)} -1$。 一棵高度为 $h$ 的完美三叉树有：$1+3+3^2+…+3^h= \frac{3^{h+1} - 1}{2}$ 个结点，反向得到 $N$ 个结点的完美三叉树高度为 $\log_3{(2N+1) - 1}$。 由于 2-3 树本身介于完美二叉树和完美三叉树之间，$N$ 个结点的 2-3 树高度就会介于 $N$ 个结点的完美二叉树和完美三叉树之间，即：$\sim\lfloor log_3N \rfloor \le h \le \sim\lfloor log_2{N} \rfloor$。 另请参阅 # 完美二叉树, 完全二叉树和完满二叉树 - veli - 博客园 (cnblogs.com)
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-结点，变成满二叉树）。 ...
3.3.6 # 解答 # 由 3.3.5 可知，$N=6$ 时的树形只有一种。 因此我们只需要将 $N=6$ 记为概率 1，利用乘法原理（或者说分步计数）计算之后的概率即可。 $N=6$ 的树形，底部共有 7 个位置可以插入： // 'D', 'G', 'K', 'O', 'S', 'Y' |--GO--| D K SY $N=7$ # 如果向 2-结点插入（示例中的 D 或 K），每个 2-结点有两个子树，概率均等，概率 $2/7 \times 2 = 4/7$，可以得到以下树形（记为 7-1）： // after |--GO--| D KL SY 如果向 3-结点插入（3-结点有三个子树，概率均等，概率 $3/7$），可以得到以下树形（记为 7-2）： |--------O--------| |--G--| |--S--| D K Q Y $N=8$ # 向 7-1 的唯一一个 2-结点插入（示例中的 D），概率 $4/7 \times 2/8= 1/7$，可以得到以下树形（记为 8-1）： ...
3.3.7 # 解答 # 根结点 # 父结点是 2-结点时 # 在左侧插入 # 在右侧插入 # 父结点是 3-结点时 # 在左侧插入 # 在右侧插入 # 在中间插入 # 见书本中文版图 3.3.9，或英文版 P428 插图。
3.3.8 # 解答 # 考虑在一棵表示 3-结点的红黑树中插入元素且不进行平衡操作的所有情况即可。 这个示意图位于中文版图 3.3.20，英文版 P436 插图 Insert into a single 3-node (three cases) 顺序插入（C->B->A 或 A->B->C） # 先中间，再两边（B->A->C 或 B->C->A） # 先两边，再中间（C->A->B 或 A->C->B） #
3.3.8 # 解答 # 官网有答案：https://algs4.cs.princeton.edu/33balanced/ iii 和 iv 是红黑树，i 不平衡，ii 不平衡且 F 不属于 D 和 E 之间的元素。
3.3.10 # 解答 # 按照题意插入即可，以下是步骤图，红链接会显示为红色。
3.3.11 # 解答 # 与上题类似，依次插入元素即可。
3.3.12 # 解答 # 插入 P 时的步骤如图所示，用例是 S E A R C H E X A M P L E，在 3.1 章的 3.1.3 节可以找到它。