PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 紅黑樹, 中位數

看板Prob_Solve (計算數學 Problem Solving)作者eieio (好多目標)時間12年前 (2012/11/22 02:02)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串1/1

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