2019-6-28
3.2.10 # 解答 # 官方实现：https://algs4.cs.princeton.edu/32bst/TestBST.java.html
测试结果：
size = 10 min = A max = X Testing keys() --------------------------- A 8 C 4 E 12 H 5 L 11 M 9 P 10 R 3 S 0 X 7 Testing select --------------------------- 0 A 1 C 2 E 3 H 4 L 5 M 6 P 7 R 8 S 9 X key rank floor ceil --------------------------- A 0 A A B 1 A C C 1 C C D 2 C E E 2 E E F 3 E H G 3 E H H 3 H H I 4 H L J 4 H L K 4 H L L 4 L L M 5 M M N 6 M P O 6 M P P 6 P P Q 7 P R R 7 R R S 8 S S T 9 S X U 9 S X V 9 S X W 9 S X X 9 X X Y 10 X Z 10 X range search --------------------------- A-Z (11)A C E H L M P R S X Z-A (0) X-X (1)X 0-Z (11)A C E H L M P R S X B-G (3)C E C-L (4)C E H L After deleting the smallest 3 keys --------------------------- H 5 L 11 M 9 P 10 R 3 S 0 X 7 After deleting the remaining keys --------------------------- After adding back the keys --------------------------- A 8 C 4 E 12 H 5 L 11 M 9 P 10 R 3 S 0 X 7
2019-6-29
3.2.11 # 解答 # 树的高度为树中深度最大的点的深度。
因此 N 个结点最多只能构造出高度为 N-1 的树来，并不能构成高度为 N 的树。
如果将题目变为用 N 个结点构造高度为 N-1 的二叉搜索树。
这样的树即为二叉搜索树的最坏情况，除唯一的叶子结点之外，每个结点有且只有一个子树。
于是除根结点外，每个结点都有两种选择，要么在左，要么在右。
因此共有 $2 ^ {n - 1}$ 种形状。
接下来证明，对于某一种确定的最坏情况，在 N 个元素各不相同的情况下，输入顺序是唯一的。
证明：
就 1 2 3 这三个元素而言，构造这样一棵树：
2 1 3 可以有 2 1 3 和 2 3 1 两种序列，因为在插入 2 之后可以选择的位置有两个
但最坏情况下的二叉搜索树不存在具有两个子结点的结点，因此输入顺序是唯一的。
反证：
也可以这样考虑，假设序列 A 可以构造出一棵最坏情况下的二叉树，插入顺序为 $x_1 \dots x_n$
假设存在与 A 顺序不同的序列 B，它构造出的二叉树与 A 的相同。
由于 A 和 B 的元素相同，因此 A 必然可以通过有限次元素交换得到 B。
...
2019-7-6
3.2.12 # 解答 # 二叉树的大小=左子树的大小+右子树的大小+1
根据上述表达式可以构造出一个递归的 Size() 方法，并删除结点中的 Size 。
Rank() 和 Select() 仍然可以正常工作，但最坏情况下的耗时可能会达到 $O(n)$ 和 $O(n^2 )$。
2019-7-27
3.2.13 # 解答 # 官方实现：https://algs4.cs.princeton.edu/32bst/NonrecursiveBST.java.html
Get 方法可以很方便的改成非递归形式。
private TValue Get(Node x, TKey key) { if (key == null) throw new ArgumentNullException(nameof(key), "calls get() with a null key"); var cur = x; while (cur != null) { var cmp = key.CompareTo(cur.Key); if (cmp < 0) cur = cur.Left; else if (cmp > 0) cur = cur.Right; else return cur.Value; } return default; } Put 方法结构类似，但需要注意更新路径上各个结点的 Size 属性。
private Node Put(Node x, TKey key, TValue value) { if (x == null) return new Node(key, value, 1); var path = new Stack<Node>(); var cur = x; while (cur !
...
2019-7-28
3.2.14 # 解答 # 就 min，max 和 select 而言，它们是尾递归的，可以直接转换成迭代形式。 （简单的说，尾递归就是所有递归操作都出现在 return 语句上，且返回值不需要参与其他运算）
例如 min，递归形式为：
if (x.Left == null) return x; return Min(x.Left); 递归调用获得的值直接返回，不再参与运算，可以直接转换为递推：
while (true) { if (x.Left == null) return x; x = x.Left; } ceiling 和 floor 会略微复杂一些，具体见代码。
代码 # min 和 max 比较简单，用一个 while 循环就可以转换为递推形式，例如 min。
while (x != null) { if (x.Left == null) return x; x = x.Left; } return x; floor 和 ceiling 则要稍微复杂一点，需要记录当前找到的最小/最大值，例如 floor。
...
2019-8-18
3.2.15 # 解答 # 比较简单，这里比较/取值都算一次访问，因此 keys 的访问序列会出现重复元素。
函数 路径 floor(Q) E Q select(5) E Q ceiling(Q) E Q rank(J) E Q J size(D, T) E Q T E D keys(D, T) E D E Q J J M Q T S S T
2019-8-22
3.2.16 # 解答 # 在高德纳的《计算机程序设计艺术》第一卷里出现了这个公式，编号为 $2.3.4.5(3)$。
书中的证明简单直接：
考虑二叉树中的某个叶子结点 $V$，设根结点到它的路径长度为 $k$，现在将 $V$ 删去。 对于二叉树的内部路径长度 $I$ 和外部路径长度 $E$ ：
由于 $V$ 被删去，$E$ 将会减少 $2(k+1)$，$I$ 将会减少 $k$，但此时 $V$ 变成了一个外部结点，$E$ 又会加上 $k$。 因此最后 $E$ 减少了 $k+2$，$I$ 减少了 $k$，重复 $N$ 次操作之后就可以得到 $E = I + 2N$。
另请参阅 # 《计算机程序设计艺术：第一卷 基本算法》（第三版）P400
2019-8-25
3.2.17 # 解答 # 像这样，有一些字母是重复的，因此删除后树形状不变：
|-------------------------------E-------------------------------| A |---------------S---------------| |-------Q |-------Y I---| |---U |-O T N |---------------I---------------| A |-------S-------| |---Q |---Y |-O |-U N T I---------------| |-------S-------| |---Q |---Y |-O |-U N T I---------------| |-------T-------| |---Q |---Y |-O U N I---------------| |-------T-------| |---Q U |-O N I-------| |---T---| |-O U N I-------| |---T |-O N I-------| |---T |-O N I-------| |---T |-O N I---| |-O N |-O N N
2019-8-25
3.2.18 # 解答 # 和上一题类似，只是删除顺序不同：
|-------------------------------E-------------------------------| A |---------------S---------------| |-------Q |-------Y I---| |---U |-O T N E-------------------------------| |---------------S---------------| |-------Q |-------Y I---| |---U |-O T N |---------------S---------------| |-------Q |-------Y I---| |---U |-O T N |---------------S---------------| |-------Q |-------Y I---| |---U |-O T N |-------S-------| |---Q |---Y |-O |-U N T |-------S-------| |---Q |---Y O |-U T |-------S-------| Q |---Y |-U T S-------| |---Y |-U T |---Y |-U T |---Y |-U T |-Y U Y
2019-8-25
3.2.19 # 解答 # 类似于这样的序列：
|-------------------------------E-------------------------------| A |---------------S---------------| |-------Q |-------Y I---| |---U |-O T N |---------------I---------------| A |-------S-------| |---Q |---Y |-O |-U N T |---------------N---------------| A |-------S-------| |---Q |---Y O |-U T |---------------O---------------| A |-------S-------| Q |---Y |-U T |---------------Q---------------| A S-------| |---Y |-U T |-------S-------| A |---Y |-U T |---T---| A |-Y U |-U-| A Y |-Y A A