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. 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中兩數間的任意值
請問這個結論是怎麼推出來的?
謝謝