作者david942j (文旋)
看板EE_DSnP
標題[問題] getPos()函式
時間Wed Dec 5 21:53:42 2012
在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)
1F：→ david942j:沒人理我QQ 因為這件事所以實驗設計中就不能放adtd -r了 12/06 15:11
2F：推 XDucka:十萬太大了 如果是adta -r 一萬再刪一萬就不會跑到天荒地 12/06 16:18
3F：→ david942j:可是BST明明就可以logN刪去 老師這樣寫好奇怪唷QQ 12/06 16:51
4F：推 ric2k1:如果是 random 產生 string 再來用 logN 刪去，由於 string 12/06 17:33
5F：→ ric2k1:的 combinations 太多種，hit rate 會很低，所以才改成 12/06 17:34
6F：→ ric2k1:random 產生 position, traverse 到第 i 大的 node之後再刪 12/06 17:35
7F：→ ric2k1:這樣的確比較像是在測 erase 這個動作本身，而不是在測 12/06 17:36
8F：→ ric2k1:logN 的搜尋。不過在不知道資料的前提之下，好像也沒有 12/06 17:37
9F：→ ric2k1:比較好的做法。你要做旋轉很 OK 啊! 只要你不嫌麻煩就好。 12/06 17:37
10F：→ david942j:那可以改成呼叫ADT的第i大元素(? (getPos自己寫的意思) 12/06 17:48