※ 引述《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.
: 圖

: 網路上的解答給 若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 移動來
減少總距離。把整個想法套用到所有的區間後，你就會得到中位數的答案。

謝謝