3.1.41
2019-3-24
3.1.41 # 解答 # 英文版描述为 1, 2, and 10 times faster。 即一样快，快一倍和快十倍（一个例子）。 和上题类似，也是解超越方程。 插值查找的平均查找次数为 $\lg(\lg(N))$。 可以解得 N = 1, 4, 58。 实验结果如下： 由于 N 太小，可以看到插值查找的运行时间几乎没有变化。
Searching
3.2.1
2019-4-14
3.2.1 # 解答 # 构造出的树如下图所示： 总比较次数：0 + 1 + 1 + 2 + 2 + 3 + 1 + 2 + 4 + 3 + 4 + 5 = 28 次 另请参阅 # BinarySearchTree 库
3.2.2
2019-4-19
3.2.2 # 解答 # 用这样的序列就可以构造出最坏情况： "A X C S E R H", "X A S C R E H", "A C E H R S X", "X S R H E C A", "X A S R H E C", "A X S R H E C" 构造出来的树看起来像这样：
3.2.3
2019-5-1
3.2.3 # 解答 # 官方答案：第一个插入的是 H，且 C 在 A 和 E 之前插入，S 在 R 和 X 之前插入的树。 对序列排序，得到 A C E H R S X 。 最优情况需要树两侧平衡，因此 H 为根结点，C 和 S 分别为 H 的子结点。 同理，A 和 E 为 C 的子结点，R 和 X 为 S 的子结点。
3.2.4
2019-5-2
3.2.4 # 解答 # d 是错误的。 要点是追踪序列中的左右顺序， 如果向右查找，那么后面的树一定都比它大，反之都比它小。 例如 d 选项，2->7 向右查找，但后面的 8 比 7 大，应该挂在 7 的右子树上，不可能在 7 的左子树里。
3.2.5
2019-5-25
3.2.5 # 解答 # 事实上，这个问题可以归结为，如何根据频率来构造一棵最优的 BST？ 如果知道树的形状，逆推插入顺序也就不难了（先序遍历）。 首先我们定义某个结点的查找开销为该结点的深度加一乘以频率， （注意根结点的深度为 0，树的高度等于整棵树中最大的深度值） 所有结点的查找开销加起来就是一整棵树的查找开销了。 $$ cost(n)=\sum_{i=0}^{n} (depth(i)+1) \times frequency(i) $$ 对于固定的一组键值和频率，$cost$ 最小的树即为我们要找的树。 这样的树被称为最优化二叉树，或者 Optimal BST。 根据二叉树的性质，我们可以将 $cost$ 的表达式变为： $$ cost(n)=cost(left)+cost(right)+\sum_{i=1}^{n} frequency(i) $$ 即左子树的开销和右子树的开销相加，再加上所有结点的频率之和。 （左子树和右子树开销计算时每个结点的深度都少了 1，因此要加上频率和） 不难得到结论，Optimal BST 的所有子树也都是 Optimal BST。 我们可以利用一种类似于构造哈夫曼树的方法构造 Optimal BST， 哈夫曼树中比较的是频率，而构造 Optimal BST 时比较的则是开销。 由于二叉查找树是有序的，因此我们先对序列排序。 然后计算所有大小为 1 的子树开销，显然就等于各个节点的频率。 再计算大小为 2 的子树，注意这里只能按顺序取结点，不能跳着取（例如取第一个和第三个结点）， 每种结点取法都对应有两种根结点选择，计算出最小的开销并记录。 以此类推，直到计算到大小为 n 的树，此时整棵 BST 就被构造出来了。 举个例子，例如给出键值和频率如下表所示： $$ \begin{array}{l|lllll} key & 1 & 2 & 3 & 4 & 5 \\ \hline p & 0. ...
3.2.6
2019-5-26
3.2.6 # 解答 # 官方 BST 实现见：https://algs4.cs.princeton.edu/32bst/BST.java.html 二叉树的高度=左右子树最大高度+1，叶结点的高度为 0。 于是我们可以构造如下递归方法： protected virtual int Height(Node x) { return x == null ? -1 : 1 + Math.Max(Height(x.Left), Height(x.Right)); } 当 x 等于 null 时，说明它是叶子结点的左/右子树，应该返回 0-1=-1。 也可以在结点中添加一个 Height 属性，记录当前结点的高度，当插入新结点时重新计算高度。 在 Put 方法中添加计算高度的代码： protected virtual Node Put(Node x, TKey key, TValue value) { if (x == null) return new Node(key, value, 1); var cmp = key.CompareTo(x.Key); if (cmp < 0) x.Left = Put(x. ...
3.2.7
2019-6-13
3.2.7 # 解答 # 平均查找次数 = 树所有结点的深度之和 / 结点个数 + 1。 只要能够获得深度和，就能构造出如下用于计算平均查找次数的方法： public int AverageCompares() { return DepthSum(_root) / Size() + 1; } 二叉树的深度之和 = 左子树的深度和 + 右子树的深度和 + 左子树的结点个数 + 右子树的结点个数 （加上根结点会使左右子树所有结点的深度+1） 于是我们可以获得如下递归方法，用于计算一棵树的深度和： private int DepthSum(Node x) { if (x == null) return 0; return DepthSum(x.Left) + DepthSum(x.Right) + x.Size - 1; } 也可以在结点中直接添加一个 DepthSum 属性，用于记录当前结点的深度和。 需要在每次插入新结点时重新计算查找路径上所有结点的 DepthSum。 private Node Put(Node x, TKey key, TValue value, int depth) { if (x == null) return new Node(key, value, 1, depth); var cmp = key. ...
3.2.8
2019-6-14
3.2.8 # 解答 # 假设输入的完全二叉树结点数目为 $n$。 完全二叉树总是可以分成两部分，一个满二叉树，以及多余的结点。 于是完全二叉树中满二叉树的部分层数为 $l = \lfloor \log_2 (n+1) \rfloor$。（根结点位于第一层） 满二叉树占的结点数量为 $n_1 = 2^l -1$，多余结点数量为 $n_2=n-n_1$。 又因为深度等于层数 - 1，多余结点正好在满二叉树的下一层，因此多余结点的深度即为 $l$。 于是多余结点的深度和 $d_2 = l \times n_2$。 接下来计算满二叉树的深度和。 一个层数为 $l$ 的满二叉树，最后一层正好有 $2^{l-1}$ 个结点。 于是深度和为 $d_1 = 0 \times 1 + 1 \times 2+2 \times 4+\cdots+(l-1)2^{l-1} =\sum_{i=1}^{l-1} i2^i$。 用错位相减法，有： $$ \begin{eqnarray*} d_1&=&1\times 2^1 + &2 \times 2^2 + \cdots + (l-1)2^{l-1} \newline 2d_1&=& &1\times 2^2 + \cdots+(l-2)2^{l-1} +(l-1)2^{l} \newline d_1-2d_1&=& 1 \times2^1+ &1 \times2^2+\cdots+1\times2^{l-1}-(l-1)2^l \newline d_1 &=&(l-1)2^l &-2^l+2 \newline &=&(l-2)2^l &+2 \end{eqnarray*} $$ ...
3.2.9
2019-6-20
3.2.9 # 解答 # 比较简单，可以按照如下步骤解决： 生成 n 个数。 生成这 n 个数的全排列。 生成 n! 棵二叉搜索树，取其中结构不同的部分。 全排列可以通过递归方式生成，方法类似于 DFS。 开始 pool 中存有所有的数，遍历 pool ，每次取一个数放入 path 中，然后递归选择下一个。 void Permutation(List<int> pool, List<int> path, List<int[]> result) { if (pool.Count == 0) { result.Add(path.ToArray()); return; } for (var i = 0; i < pool.Count; i++) { var item = pool[i]; path.Add(item); pool.RemoveAt(i); Permutation(pool, path, result); pool.Insert(i, item); path.Remove(item); } } 有了 n! 棵二叉树之后，我们需要过滤掉结构相同的树。 我们可以把二叉树转换成数组表示（层序遍历即可），然后遍历数组进行比较。 public static bool IsStructureEqual<TKeyA, TValueA, TKeyB, TValueB>(Bst<TKeyA, TValueA> a, Bst<TKeyB, TValueB> b) where TKeyA : IComparable<TKeyA> where TKeyB : IComparable<TKeyB> { var treeA = a. ...