[問題] 關於bst跟array的速度

[WSzc (WSzc)]

雖然做完了
可是對於bst為什麼do2會慢array這麼多還是有點疑惑耶

在insert的時候bst是比較快
但是到了delete的時候就慢了10倍以上

可是delete的時候(adtd -r xxx)

array花O(n)的時間做memmove的動作

而bst要先找successor
最壞的情況會花O(n)的時間
然後再把這個node換成successor
這個地方應該是constant time吧 只是一堆判斷式
(我有加了parent 所以不用花時間trace)
那怎麼會慢這麼多呢(20幾秒跟2秒的差距)

還是那些改變pointer指的位置的判斷式都會很花時間呢??

謝謝回答!

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 118.161.57.246
推 goodword:我記得老師好像有回答過.....
推 Trumen:作業5 random delete的random指的是iterator不是value喔
→ goodword:不是delete時慢   是要random找一個來delete時會滿久的
→ goodword:iterator++   做random次  才選到要刪的那一個
→ WSzc:原來如此阿 感謝!!