※ 引述《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 移动来 减少总距离。把整个想法套用到所有的区间後，你就会得到中位数的答案。 -- Just because you deserve this doesn't mean they're gonna give it to you. Sometimes you gotta take what's yours. ── Kenny Ray Carter --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 54.240.196.185