※ 引述《wsx02 ()》之铭言：
: 1. what is the largest possible number of internal nodes in a red black tree
: with black height k? what is the smallest possible number?
: CLRS的exercise 网络上的解答给
: 最多2^(2k) -1个, 最少2^k -1个
: 请问这两个数字是怎么推出来的?
2^k -1 是整个 tree 都是黑的，不能再少，再少的话你必然能找到一条 path
长度不到 k
2^(2k) -1 是整个 tree 的 height 为 2k，红黑相间，所有的 path 都是 k
个黑的和 k 个红的交错。如果有更多 node，因为 parent-child 不能都是红的
，必然会增加黑色的个数，使得 black height > k。
: 2. Professor Olay is consulting for an oil company, which is planning a large
: pipeline running east to west through an oil field of n wells. From each
: well, a spur pipeline is to be connected directly to the main pipeline along
: a shortest path (either north or south), as shown in Figure 9.2.
: Given x- and y-coordinates of the wells, how should the professor pick the
: optimal location of the main pipeline (the one that minimizes the total
: length of the spurs)? Show that the optimal location can be determined in
: linear time.
: 图 http://ppt.cc/0Nzd
: 网络上的解答给 若n为奇数, 即所有管线的y中的中位数
: 若n为偶数, y可以是所有y中两数间的任意值
: 请问这个结论是怎么推出来的?
: 谢谢
设所有井的 y 座标为 y1, y2, ..., yn，你其实就是找 y 去最小化
|y-y1| + |y-y2| + ... + |y-yn|
这里我举例有 10 个井，y 座标 sort 过。如果你 y 落在 y7 y8 之间好了，那
么当你把 y 往 y7 移动距离 d 的时候，|y-y1| + ... + |y-y7| 这里会减少 7d
，而 |y-y8| + |y-y9| + |y-y10| 会增加 3d，你就会一直把 y 往 y7 移动来
减少总距离。把整个想法套用到所有的区间后，你就会得到中位数的答案。