作者ck910679 (無)
看板EE_DSnP
標題[問題] bst中delete的速度…
時間Wed May 21 00:02:42 2008
其它的功能，速度都跟老師的差不多
只有delete，差非常非常多
在do2中的
adtd -r 50000
ref跑了1xx秒
我的跑了4xxxx秒
大概40倍吧@@
不知道是不是方法的問題@@
我做的事如下
先檢查是不是empty，做適當的反應
無論input如果，都找出裡面的data
然後進入一長串的判斷
判斷要刪的那個node，是左child，還是右child
要刪的node的child個數(0個或1個就直接接下一個
2個的話，找出右subtree的最小那個，然後改pointer，使他連到原來要刪的那個位子上)
大概是一一就不同情況做反應...
我有試著重寫過
把動覆用到的部分用function寫起來
但結果沒有變好Orz...
想問一下，這樣子程式大概是要怎麼修
謝謝大家~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.175.28.109
1F：推 bnsblue:那你括號裡面的要再做處理是怎麼處理？ 05/21 00:05
※ 編輯: ck910679 來自: 218.175.28.109 (05/21 00:09)
2F：推 ric2k1:找機會來跟大家分享一下我的 bst 怎麼寫... 05/21 00:14
3F：→ ric2k1:下星期三上課好了. 05/21 00:14
4F：推 bnsblue:也許可以檢查看看你有沒有重複尋找的動作~ 05/21 00:16
5F：→ ck910679:好，我找看看~~ 謝謝樓上。另外，會是判斷太多的關係嗎? 05/21 00:17
6F：推 bnsblue:也是有可能 但是多應該也不會多到太誇張 05/21 00:25
7F：→ bnsblue:或是你在迴圈裡有很多判斷式? 05/21 00:25
8F：推 timrau:改pointer接來接去太累了，何不直接把裡面的資料搬過來就好 05/21 00:30
9F：→ ck910679:有道理耶~~~ 05/21 00:44
10F：推 bnsblue:直接搬資料只有在2 children下比較快吧 05/21 00:50
11F：推 timrau:我當然是說只有2 children case，0/1 children cases簡單啊 05/21 00:52