Re: [理工] 100成大資工 DS＆Algo(資結)
單純回覆第二題 red-black tree 支援min-gap
(a)
我覺得題目意思應該是可以改變資料結構
所以加上幾個變數 min : min-gap 中兩個數值比較小的那個
max : min-gap 中兩個數值比較大的那個
之後每次在insert data 到 red black tree的時候
都要dynamic 調整min , max兩個變數
調整方式很簡單，在insert的時候，找要insert位置的時候
把會經過的點，和目前要insert的值去比較，
若是 |經過的點-要Insert的值| < |min - max|
則就把 min , max 更新成 經過的點&要insert的值，這些都可以在O(1)完成
其他就和一般red black tree一樣，所以insert還是O(lgn)沒變
至於(b)...就直接拿min,max就是了XD
其實O(1)的時間而已
他題目說的O(lgn)應該是指 maintain這樣的data structure所要花的時間
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.218.169
推
01/25 14:28, , 1F
01/25 14:28, 1F
討論串 (同標題文章)
完整討論串 (本文為第 3 之 3 篇)：