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