[問題] getPos()函式

[david942j (文旋)]

在adtTest.h裡面
random刪去節點的時候
是random產生數字
然後呼叫getPos()函式
可是
getPos()這個函式的實做方式是
遍歷整個_container，找出對應第幾大的位置

這樣不就失去BST的快速尋找的意義了嘛QQ?

害我以為adtd -r 100000跑到天荒地老都沒有結果是我寫爛了(默



另外
雖然題本說可以不用旋轉
可是寫了應該沒差吧?
不是為了平衡
是小弟不才不知道不旋轉怎麼刪去節點=.=

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 58.115.139.219
※ 編輯: david942j       來自: 58.115.139.219       (12/05 21:54)
※ 編輯: david942j       來自: 58.115.139.219       (12/05 21:55)
※ 編輯: david942j       來自: 58.115.139.219       (12/05 22:25)
※ 編輯: david942j       來自: 58.115.139.219       (12/05 22:32)
→ david942j:沒人理我QQ 因為這件事所以實驗設計中就不能放adtd -r了
推 XDucka:十萬太大了  如果是adta -r 一萬再刪一萬就不會跑到天荒地
→ david942j:可是BST明明就可以logN刪去 老師這樣寫好奇怪唷QQ
推 ric2k1:如果是 random 產生 string 再來用 logN 刪去，由於 string
→ ric2k1:的 combinations 太多種，hit rate 會很低，所以才改成
→ ric2k1:random 產生 position, traverse 到第 i 大的 node之後再刪
→ ric2k1:這樣的確比較像是在測 erase 這個動作本身，而不是在測
→ ric2k1:logN 的搜尋。不過在不知道資料的前提之下，好像也沒有
→ ric2k1:比較好的做法。你要做旋轉很 OK 啊! 只要你不嫌麻煩就好。
→ david942j:那可以改成呼叫ADT的第i大元素(? (getPos自己寫的意思)