3.2.20 # 解答 # 勘误：英文版为 keys() 方法（而非 Size() 方法）。 先来观察一下 keys() 方法的实现： public IEnumerable<TKey> Keys(TKey lo, TKey hi) { var queue = new Queue<TKey>(); Keys(root, queue, lo, hi); return queue; } private void Keys(Node x, Queue<TKey> queue, TKey lo, TKey hi) { var cmplo = lo.CompareTo(x.Key); var cmphi = hi.CompareTo(x.Key); if (cmplo < 0) Keys(x.Left, queue, lo, hi); if (cmplo <= 0 && cmphi >= 0) queue.Enqueue(x.Key); if (cmphi > 0) Keys(x. ...
3.2.21 # 解答 # 要注意保持每个键的出现概率相等，可以先随机一个排名，然后从树中将对应排名的键取出来。 private static readonly Random Random = new Random(); public TKey RandomKey() { var rank = Random.Next(1, Size() + 1); return GetKeyWithRank(root, rank); } private TKey GetKeyWithRank(Node x, int rank) { var left = (x.Left == null ? 0 : x.Left.Size) + 1; if (left > rank) { return GetKeyWithRank(x.Left, rank); } else if (left == rank) { return x.Key; } else { return GetKeyWithRank(x.Right, rank - left); } } 可以观察到每个键的出现概率都是差不多的。 ...
3.2.22 # 解答 # 这里的前驱和后继指的是二叉树中序遍历序列里结点的前驱和后继。 由于二叉搜索树的性质，它的中序遍历序列是递增有序的。 因此一个结点如果有左子树，要么前驱就是左子树中最大的结点（最右侧）； 同理结点如果有右子树，要么后继就是右子树中最小的结点（最左侧）。 于是结点的前驱不会有右子节点，后继不会有左子节点，得证。
3.2.23 # 解答 # 不满足，反例如下： |-------10 |---5---| 3 |-8-| 6 9 Delete 5 then delete 3 |-------10 6---| 8-| 9 Delete 3 then delete 5 |---10 |-8-| 6 9 这里先删除 3 会使 5 的左子树为空，导致删除 5 的时候采取的策略被改变（尽管 5 的右子树没有任何变化）。 另请参阅 # Deletion procedure for a Binary Search Tree-Stackoverflow
3.2.24 # 解答 # 根据命题 D （英文版 P404，中文版 P255），一次插入所需的比较次数平均为 $ 1.39\lg N$。 (我们这里要求和，因此可以直接使用平均值进行计算） 于是构造一棵二叉查找树所需的比较次数为： $$ 1.39C= 1.39\sum_{i=0}^N \lg i=1.39 \times(\lg 1 + \lg2+\cdots+\lg N) $$ 根据对数恒等式，有： $$ C=\lg 1 + \lg2+\cdots+\lg N=\lg(1\times2\times3\times\cdots\times N)=\lg(N!) $$ 于是有 $ 1.39C=1.39\lg(N!) > \lg(N!)$ ，得证。
3.2.25 # 解答 # 官方实现：https://algs4.cs.princeton.edu/32bst/PerfectBalance.java.html 先排序，然后视其为中序序列，每次取中间的键作为根结点，左半数组是左子树，右半数组是右子树，递归构造。 private Node BuildTree(KeyValuePair<TKey, TValue>[] init, int lo, int hi)// init is sorted { if (lo > hi) { return null; } var mid = (hi - lo) / 2 + lo; var current = new Node(init[mid].Key, init[mid].Value, 1); current.Left = BuildTree(init, lo, mid - 1); current.Right = BuildTree(init, mid + 1, hi); if (current.Left != null) { current.Size += current.Left.Size; } if (current.Right ! ...
3.2.26 # 解答 # 在 {% post_link 3-2-9 3.2.9 %} 的代码基础上进行修改，统计每种形状的出现次数，以此获得准确的概率。 概率如下，基本呈现一个对称的图形。 原始数据： n=2 50% 50% n=3 16.666666% 16.666666% 33.333332% 16.666666% 16.666666% n=4 8.333333% 16.666666% 37.5% 12.5% 8.333333% 16.666666% n=5 0.8333333% 0.8333333% 1.6666666% 0.8333333% 0.8333333% 2.5% 2.5% 2.5% 2.5% 0.8333333% 0.8333333% 1.6666666% 0.8333333% 0.8333333% 3.3333333% 3.3333333% 6.6666665% 3.3333333% 3.3333333% 5% 5% 5% 5% 3.3333333% 3.3333333% 6.6666665% 3.3333333% 3.3333333% 0.8333333% 0.8333333% 1.6666666% 0.8333333% 0.8333333% 2.5% 2.5% 2.5% 2.5% 0.8333333% 0.8333333% 1. ...
3.2.27 # 解答 # 二叉查找树的内存开销=对象开销+根结点引用+N个结点 =对象开销+根结点引用+N×(对象开销+父类型引用+左/右子树引用+键/值引用+结点数) =16+8+N×(16+8+16+16+4+4)=24+64N 字节 BinarySearchST：对象开销+键/值数组引用+键/值数组+计数器（一个 int）。 =16+16+(16+4+4+8N)×2+4+4=88+16N 字节。 SequentialSearchST：对象开销+头结点引用+N个结点+计数器 =对象开销+头结点引用+N×(对象开销+父类型引用+next引用+键/值引用)+计数器 =16+8+N×(16+8+8+16)+4+4=32+48N 字节 示意图如下： 其中，对象开销 16 字节，其他均为引用，各占 8 字节。 《双城记》中不重复的单词有 26436 个（不包括最后的版权声明），全部是原文的子字符串，每个占 40 字节。 一个 Integer 占 24 字节，于是估计的内存消耗为：24+(64+40+24)×26436=3383832 字节。
3.2.28 # 解答 # 修改一下 Put 和 Get 方法，在实际操作之前先检查缓存是否符合要求，然后在操作之后更新缓存。 代码 # private Node _cache; public override TValue Get(TKey key) { if (_cache != null && _cache.Key.CompareTo(key) == 0) { return _cache.Value; } return Get(root, key).Value; } protected override Node Get(Node x, TKey key) { if (key == null) { throw new ArgumentNullException("calls get() with a null key"); } if (x == null) { return null; } var cmp = key. ...
3.2.29 # 解答 # 本题在原书后续印刷中已修改，这里仍采用中文版的题目。 部分解答：https://algs4.cs.princeton.edu/32bst/BST.java.html（isSizeConsistent()） 如果根结点记录的结点数=左子树的结点数+右子树的结点数+1，就符合要求。 按照这个题意编制递归方法即可。 先写边界，当输入为 null 时，显然符合要求。 然后计算左子树的 Size 和右子树的 Size 加起来是否等于根结点的 Size + 1， 以及左子树和右子树是否符合同样的条件。 代码 # protected static bool IsBinaryTree(Node x) { if (x == null) { return true; // 空树显然符合二叉树条件。 } var size = 1; // 包括当前结点本身。 if (x.Left != null) { size += x.Left.Size; } if (x.Right != null) { size += x.Right.Size; } return IsBinaryTree(x.Left) && IsBinaryTree(x.Right) && x.Size == size; } 另请参阅 # BinarySearchTree 库