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