作者danielko (蛋尼爾糕)
看板EE_DSnP
標題[請益] bst: adtd -r 超慢
時間Mon May 19 01:58:41 2008
我測過老師的do2大概120s左右
可是我的在adtd -r 50000就卡住了
洗個澡回來還是沒好@@
後來自己測了一下
adtr 100000
adta -r 100000
-- 到目前為止都比老師稍快XD --
因為不敢試50000個
先測adta -r 100居然花了3秒多
想問一下老師是做AVL tree嗎
感覺多花一些時間在insert卻可以使delete的效率大為提升
我因為不想碰rotation所以...
我的delete是分三個case(在要刪除的點)
case 1: no child -> 直接砍掉
case 2: one child -> 把child黏上parent
case 3: two child -> 把right subtree的min裡面內容換到現在的node，砍掉min
還是說我有什麼沒有注意的地方嗎？
謝謝～
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.27.3
1F：→ spock:老師有說，他偷偷把 iterator 跑過的紀錄存下來，省很多時間 05/19 06:14
2F：→ spock:時間瓶頸應該都是找 successor 的部份？（我猜） 05/19 06:15
3F：推 ric2k1:我只做 unbalanced BST. Yes, I record the trace on itera 05/19 09:28
4F：推 bnsblue:跑successor非常耗時.... 05/19 09:57
5F：→ danielko:我也有把iterator的trace存下來耶 05/19 11:49
6F：→ danielko:不過那不是只有在adtp <-r>的時候會用到嗎? 05/19 11:49
7F：推 ric2k1:我的 trace 是只要有動到 iterator 就會存在 & 更新 05/19 12:32
8F：→ danielko:所以老師的iterator支援印到一半add/erase node嗎? 05/19 16:01
9F：→ danielko:另外我不知道我慢是不是因為我delete是recursive call 05/19 16:01
10F：推 ric2k1:理論上可以, 我的 iterator 不限制 trace 一定要從 _root, 05/19 16:03
11F：→ ric2k1:而且可以同時多個 iterators 在做 traversal 05/19 16:03
12F：→ ric2k1:我還是覺得 recursive call 所造成的 overhead 應該還好, 05/19 16:04
13F：→ ric2k1:主要還是 algorithm 本身複雜度的問題. 05/19 16:05
14F：→ danielko:謝謝老師 05/19 19:00