[问题] 红黑树, 中位数

楼主: wsx02   2012-11-21 20:16:39
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中两数间的任意值
请问这个结论是怎么推出来的?
谢谢

Links booklink

Contact Us: admin [ a t ] ucptt.com