2019-11-2
3.2.40 # 解答 # 书中的结论是 1986 年 L. Devroye 给出的，原式为 $H_n \rightarrow c\log(n)$。
其中 $c$ 是方程 $c\log \frac{2e}{c}=1$ 的最大解，约为 $4.31107$。
2002 年 Michael Drmota 给出了一个跟精确的公式：$\mathrm{E}(H_n)=c\log n-\frac{3c}{2(c-1)}\log \log n + O(1)$。
测试结果如下，误差基本稳定在一个常数。
代码 # static void Main(string[] args) { var n = 10000; var trials = 100; for (var i = 0; i < 3; i++) { var items = new int[n]; for (var j = 0; j < n; j++) { items[j] = j; } var aveHeight = 0d; for (var j = 0; j < trials; j++) { var bst = new BST<int, int>(); Shuffle(items); foreach (var item in items) { bst.
...
2019-11-4
3.2.41 # 解答 # 大体上和标准 BST 实现差不多，做如下变换即可：
x.Key => _nodes[x].Key; x.Value => _nodes[x].Value; x.Left => _left[x]; x.Right => _right[x]; 由于使用了数组，在正常「删除」二叉树结点之后，还需要手工「垃圾回收」，如下图所示：
性能比较：
可见数组实现在删除节点时有巨大的性能差距。
代码 # private readonly Node[] _nodes; private readonly int[] _left; private readonly int[] _right; private int _size; private int _root; /// <summary> /// 二叉搜索树的结点。 /// </summary> private class Node { public TKey Key { get; set; } public TValue Value { get; set; } } /// <summary> /// 建立一个以数组为基础的二叉搜索树。 /// </summary> /// <param name="maxSize">二叉搜索树中的结点数。</param> public BSTArray(int maxSize) { _nodes = new Node[maxSize]; _left = new int[maxSize]; _right = new int[maxSize]; for (var i = 0; i < maxSize; i++) { _left[i] = -1; _right[i] = -1; } _size = 0; _root = 0; } /// <summary> /// 向符号表插入键值对。 /// </summary> /// <param name="key">键。</param> /// <param name="value">值。</param> public void Put(TKey key, TValue value) { if (_size == _nodes.
...
2019-12-8
3.2.42 # 解答 # 按照题意实现即可，关键点有两个：
一是选择前驱的实现方式，只要选择左子树中的最大结点即可。
if (_random.NextDouble() < 0.5) { x = Min(t.Right); x.Right = DeleteMin(t.Right); x.Left = t.Left; } else { x = Max(t.Left); x.Left = DeleteMax(t.Left); x.Right = t.Right; } 二是内部路径长度的计算方式，需要用层序遍历把所有结点的深度加起来。
var internalPath = 0; var nowLayer = new Queue<Node>(); var nextLayer = new Queue<Node>(); nextLayer.Enqueue(root); var depth = 0; while (nextLayer.Count > 0) { var temp = nowLayer; nowLayer = nextLayer; nextLayer = temp; while (nowLayer.
...
2019-12-28
3.2.43 # 解答 # 依照题意实现即可，put/get 大约 10 倍差距。
MostFrequentlyKey 的实现：
public static TKey MostFrequentlyKey<TKey>(IST<TKey, int> st, TKey[] keys) { foreach (var s in keys) { if (st.Contains(s)) st.Put(s, st.Get(s) + 1); else st.Put(s, 1); } var max = keys[0]; foreach (var s in st.Keys()) if (st.Get(s) > st.Get(max)) max = s; return max; } 另请参阅 # BinarySearchTree 库
2020-1-12
3.2.44 # 解答 # 使用类似于 3.1.38 的方法进行绘图，当 n=10000 时的结果如下：
代码 # 绘图部分：
public void Draw(long[] data) { var panel = CreateGraphics(); var unitX = (float)ClientRectangle.Width / data.Length; var unitY = (float)ClientRectangle.Height / data.Max(); var accumulation = 0f; // f = float for (var i = 0; i < data.Length; i++) { // Gray panel.FillEllipse(Brushes.Gray, (i + 1) * unitX, ClientRectangle.Bottom - data[i] * unitY, 2, 2); // Red panel.FillEllipse(Brushes.Red, (i + 1) * unitX, ClientRectangle.
...
2020-1-12
3.2.45 # 解答 # 结果如下，可参考 3.1.39。
SequentialSearchST
BinarySearchST
BST
可以看到 BST 的曲线更为平滑，插入和查找部分耗时十分接近。
另请参阅 # BinarySearchTree 库
2020-1-12
3.2.46 # 解答 # 翻译有些问题，其实指的是用 N 个 double 构造一个 BST 和 BinarySearchST 的速度对比。
Get 速度 BST 是不会比 BinarySearchST 快的。（$1.39\lg N$>$\lg N$）
二叉搜索树一次查找平均需要 $1.39\lg N$ 次比较，二分查找则是 $N/2$，于是可以求得开销：
二叉查找树：$1.39 \sum_{i=1}^{N-1} \lg i=1.39 \lg (N-1)!=1.39(N-1)\lg(N-1)$。
二分查找实现的符号表：$1/2+2/2+ \cdots+(N-1)/2=N(N-1)/4$ 。
令两式相等，可以求得快 10 倍，100 倍，1000 倍的 $N$ 值。 例如快 10 倍的方程：
$$ 13.9(N-1)\lg(N-1)=N(N-1)/4 \newline 13.9\lg (N-1)=N/4 $$
这是一个超越方程，可以简单用程序穷举出一个数值解。
for (var i = 0d; i < int.MaxValue; i++) { if (13.9 * Math.Log2(i - 1) < i / 4) { Console.
...
2020-1-28
3.2.47 # 解答 # 如下图所示，内部路径平均长度是比较符合规律的：
方差：
代码 # 一次测试：
private int Test(int n) { var data = GetRandomInt(n); var bst = new BST<int, int>(); foreach (var d in data) { bst.Put(d, d); } return bst.AverageInternalPathLength(); } 求解内部路径长度：
public int AverageInternalPathLength() => InternalPath() / Size() + 1; private int InternalPath() { var internalPath = 0; var nowLayer = new Queue<Node>(); var nextLayer = new Queue<Node>(); nextLayer.Enqueue(root); var depth = 0; while (nextLayer.
...
2021-9-6
3.3.1 # 解答 # 结果如下：
E AE |--E--| A S |--E--| A SY |--ES--| A Q Y |--ES--| A Q UY |--------S--------| |--E--| |--U--| A Q T Y |--------S--------| |--E--| |--U--| A IQ T Y |--------S--------| |--EO--| |--U--| A I Q T Y |--------S--------| |--EO--| |--U--| A IN Q T Y 代码 # 2-3 树的实现
using System; using System.Collections.Generic; using System.Linq; using System.Text; // ReSharper disable CognitiveComplexity namespace BalancedSearchTree { /// <summary> /// 2-3 树。 /// </summary> /// <typeparam name="TKey">键。</typeparam> /// <typeparam name="TValue">值。</typeparam> public class TwoThreeBst<TKey, TValue> : IOrderedSt<TKey, TValue> where TKey : IComparable<TKey> { private int _count; private Node _root; /// <inheritdoc /> public void Put(TKey key, TValue value) { if (_root == null) { _root = new Node(null); _root.
...
2021-9-6
3.3.2 # 解答 # 和 3.3.1 类似，结果如下：
Y LY |--P--| L Y |--P--| LM Y |--P--| LM XY |--LP--| H M XY |--LP--| CH M XY |--------P--------| |--L--| |--X--| CH M R Y |--------P--------| |--CL--| |--X--| A H M R Y |--------P--------| |--CL--| |--X--| A EH M R Y |--------P--------| |--CL--| |--X--| A EH M RS Y 另请参阅 # BalancedSearchTree 库