作者percentage (九)
看板EE_DSnP
标题[请益] BSTree
时间Sat Dec 3 03:23:28 2011
我是采用parent的写法。
我一开始仿照了dlist的constructor，
在BSTree生成时就new了一个dummy node，
但後来发现，这样好像会导致我的 atda -r 产生出来的string都比ref慢一个。
例子如下
ref [0]=2 [1]=5 [2] = 7 [3]=4
我 [0]=5 [1]=7 [2]=4 .....以此类推
请问这样的话怎麽办?
毕竟我从一开始写的方法就跟老师不同了@@
还是说问题其实不在这里...
谢谢
打扰大家了..
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.44.9.157
※ 编辑: percentage 来自: 114.44.9.157 (12/03 03:23)
※ 编辑: percentage 来自: 114.44.9.157 (12/03 03:24)
1F：推 vincere:我的做法是一生成root的时候就硬塞给它的constructor一个 12/03 06:41
2F：→ vincere:空白字串 12/03 06:42
3F：推 victoret:或者是可以尝试 constructor 里面把 _root = 0，要增加的 12/03 10:32
4F：→ victoret:时候再 new 他 12/03 10:32
5F：→ shryuhuai:同一楼 12/03 10:39
6F：推 TommyKSHS:我觉得用 _root = 0 的方法比较好。因为如果今天 12/03 13:10
7F：→ TommyKSHS:template T 的 T 的 constructor 不是吃 string 的话 12/03 13:10
8F：→ TommyKSHS:一楼那招会炸开 @@ 12/03 13:10
9F：推 vuluy:可是_root=0的方法是不是就没有dummy node了，如果希望使用 12/03 13:16
10F：→ vuluy:dummy node的话... 12/03 13:16
11F：推 TommyKSHS:我的确没有用 dummy node … 12/03 13:18
12F：→ djshen:dummy node处理上好像比较麻烦 12/03 13:35
13F：推 victoret:感觉起来比较麻烦 +1 12/03 13:40
14F：→ shryuhuai:如果真的要拿来存资料的话也不用担心乱数跑掉吧 12/03 13:52
15F：→ shryuhuai:T不吃string的话改成呼叫T()就ok了 12/03 13:56
16F：推 TommyKSHS:只是呼叫 T() 的话就会出现原 PO 的问题就是了 XD 12/03 14:42
17F：推 tcm2006:能问一下没用dummy node的同学 end是指到哪里吗 我本来让 12/03 16:38
18F：→ tcm2006:指回_root 其他功能做起来没问题 但end()传root很奇怪... 12/03 16:39
19F：→ tcm2006: 回 12/03 16:40
20F：推 vuluy:楼上end()跟iterator(_root)怎麽分辨，我也想问楼上的问题 12/03 16:48
21F：推 TommyKSHS:我 end() 传回的是 iterator(NULL) 12/03 17:08
22F：推 vuluy:我想过这麽做，可是卡在--end()想不到怎麽处理 12/03 17:13
23F：推 victoret:就额外处理，特别拿出来检查就可以了 12/03 17:21
24F：推 vuluy:我知道要额外处理，但是怎麽找到最大值的那个点，iterator有 12/03 17:24
25F：→ vuluy:的资讯就只有_node而已啊，还是其实楼上几位都是用trace纪录 12/03 17:24
26F：推 victoret:啊我是用 trace... 12/03 17:29
27F：推 TommyKSHS:从 _root 往右一直走就会走到 max 了 12/03 17:55
28F：推 vuluy:可是compiler不让我在iterator里access _root啊 12/03 18:01
29F：推 victoret:friend 一下 12/03 18:03
30F：→ wmin0:我的作法是把successor的pointer偷放在没用的pointer里面 12/03 21:22
31F：→ wmin0:动了点手脚让他有所区隔 然後end就传max的successor那个被 12/03 21:23
32F：→ wmin0:动过手脚的pointer出来@@ 12/03 21:23
33F：→ wmin0:要--的话只要在那个pointer上再动一点手脚就指回去了XD 12/03 21:23
34F：→ wmin0:回一下vuluy 要抓_root的话 因为iter里面并没有树的资讯 12/03 21:25
35F：→ wmin0:看是要在construct的时候偷偷塞进去 还是要把_root变 12/03 21:25
36F：→ wmin0:private static 可是这麽一来就只能有一棵树@@" 12/03 21:25
37F：推 ric2k1:大家好像已经讨论得差不多了... 我说过我们会用 -string 12/04 00:29
38F：→ ric2k1:来测正确性，所以大家可以不用在 random 上面花太多的心思 12/04 00:29
39F：→ ric2k1:如果只是为了让 random 跟 ref 看起来一样结果却把 code 12/04 00:30
40F：→ ric2k1:写得很 tricky，我觉得会有点舍本逐末... 12/04 00:30