作者david942j (文旋)
看板EE_DSnP
标题[问题] getPos()函式
时间Wed Dec 5 21:53:42 2012
在adtTest.h里面
random删去节点的时候
是random产生数字
然後呼叫getPos()函式
可是
getPos()这个函式的实做方式是
遍历整个_container,找出对应第几大的位置
这样不就失去BST的快速寻找的意义了嘛QQ?
害我以为adtd -r 100000跑到天荒地老都没有结果是我写烂了(默
另外
虽然题本说可以不用旋转
可是写了应该没差吧?
不是为了平衡
是小弟不才不知道不旋转怎麽删去节点=.=
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 58.115.139.219
※ 编辑: david942j 来自: 58.115.139.219 (12/05 21:54)
※ 编辑: david942j 来自: 58.115.139.219 (12/05 21:55)
※ 编辑: david942j 来自: 58.115.139.219 (12/05 22:25)
※ 编辑: david942j 来自: 58.115.139.219 (12/05 22:32)
1F:→ david942j:没人理我QQ 因为这件事所以实验设计中就不能放adtd -r了 12/06 15:11
2F:推 XDucka:十万太大了 如果是adta -r 一万再删一万就不会跑到天荒地 12/06 16:18
3F:→ david942j:可是BST明明就可以logN删去 老师这样写好奇怪唷QQ 12/06 16:51
4F:推 ric2k1:如果是 random 产生 string 再来用 logN 删去,由於 string 12/06 17:33
5F:→ ric2k1:的 combinations 太多种,hit rate 会很低,所以才改成 12/06 17:34
6F:→ ric2k1:random 产生 position, traverse 到第 i 大的 node之後再删 12/06 17:35
7F:→ ric2k1:这样的确比较像是在测 erase 这个动作本身,而不是在测 12/06 17:36
8F:→ ric2k1:logN 的搜寻。不过在不知道资料的前提之下,好像也没有 12/06 17:37
9F:→ ric2k1:比较好的做法。你要做旋转很 OK 啊! 只要你不嫌麻烦就好。 12/06 17:37
10F:→ david942j:那可以改成呼叫ADT的第i大元素(? (getPos自己写的意思) 12/06 17:48