Re: [理工] [資結] BST
※ 引述《wsx02 ()》之銘言：
: give an n-node binary search tree on which both the find-min and find-max
: operations can be executed in constant time
: 請問有人知道該怎麼解嗎?
: 謝謝
Skew 的話，找最小(或最大)在root雖然可以是 O(1) (costant time)
但是另一個最大(最小)，會在 leaf 上
所以走訪時還是需要 O(n)的時間
可以用 min-max heap tree
root 會是最大(或最小)
其左右子樹的root(及左右兒子)會是最小(或最大)
接著每一層大小大小交錯以此類推
所以 find-min 會在 root 可以在 Constant Time 完成
find-max 會在下一層(Level 1)，所以也是 Constant Time
詳細可參考維基 http://goo.gl/aXfqZ
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.35.165.67
→
10/18 02:00, , 1F
10/18 02:00, 1F
→
10/18 15:29, , 2F
10/18 15:29, 2F
→
10/18 19:35, , 3F
10/18 19:35, 3F