作者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