[問題] getPos()函式

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