ikesnowy

红黑树的高度。改进你为练习 3.3.43 给出的程序，用图像绘制出所有红黑树的高度并讨论结果。

统计旋转。改进你为练习 3.3.43 给出的程序，用图像绘制出在构造红黑树的过程中旋转和分解结点的次数并讨论结果。

平均查找用时。用实验研究和计算在一棵由 N 个随机结点构造的红黑树中到达一个随机结点的平均路径长度（内部路径长度除以 N 再加 1）的平均差和标准差，对于 1 到 10000 之间的每个 N 至少重复实验 1000 遍。将结果绘制成如图 3.3.30 相似的 Tufte 图，并画上函数 lgN - 0.5 的曲线。

成本图。改造 RedBlackBST 的实现来绘制本节中能够显示计算中每次 put() 操作的成本的图（请参考练习 3.1.38）。

统计红色结点。编写一段程序，统计给定的红黑树中红色结点所占的比例。对于 N=10^4、10^5 和 10^6，用你的程序统计至少 100 棵随机构造的大小为 N 的红黑树并得出一个猜想。

删除操作。将上两题中的方法和二叉查找树的 delete() 方法结合起来，实现红黑树的删除操作。

删除最大键。实现红黑树的 deleteMax() 方法。需要注意的是因为红链接都是左链接，所以这里用到的变换和上一道练习中的有所不同。

删除最小键。实现红黑树的 deleteMin() 方法，在沿着树的最左路径向下的过程中实现正文所述的变换，保证当前结点不是 2- 结点。

旋转的基础定理。请证明，使用一系列左旋转和右旋转可以将一棵二叉查找树转化为由同一组键生成的其他任意一棵二叉查找树。