作者bnsblue (想當你的天空)
看板EE_DSnP
標題[問題] bst的iterator 還有 end()
時間Tue May 13 00:11:23 2008
我有兩個問題想請問大家:
1. 根據題目要求,bst的iterator感覺上應該是要作成in-order的(?)
那還有需要把post-order和pre-order都implement嗎?
2. 由於在處理end()的時候遇到一些問題,所以有想到是不是
要把external node做出來呢?而且要怎麼判斷external node的parent是誰呢?
(要不然insert()實在是很難做...orz)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.137.69.97
1F:推 HigherKuo:我想問的是,operator ++ --就是找下一個node,除了 05/13 17:29
2F:→ HigherKuo:traverse整個tree一次之外(應該會慢到不行),有什麼比較 05/13 17:30
3F:→ HigherKuo:聰明的方式呢? 05/13 17:31
4F:→ bnsblue:其實有幾種case 如果有子樹的話可以直接找successor 05/13 18:20
5F:→ bnsblue:還有一些case可以用記錄"從root走到這個點的過程" 05/13 18:21
6F:→ bnsblue:但是還有一些case沒想到方法 05/13 18:21
7F:推 HigherKuo:我想到的是,多用一個pointer指到parents。 05/13 21:10
8F:→ bnsblue:可是那樣的memory overhead算是不小 尤其是10^5 nodes以上 05/13 23:21
9F:→ bnsblue:不過我也不知道該選擇速度還是空間比較好 05/13 23:23
10F:推 HigherKuo:嗯,先做出來卡要緊! XD 05/13 23:59
11F:→ bnsblue:說得好XD 05/14 00:01
12F:推 timrau:如果堅持要省下那個parent又想要快的話 請參考 05/14 00:33
13F:→ timrau:"Threaded binary tree". 不過要把這東西寫對嘛...... 05/14 00:33
14F:→ timrau:反正已經有code可看了,Wikipedia的第一個reference就是XD 05/14 00:35
15F:→ bnsblue:也是蠻長的XD 05/14 00:46
16F:推 timrau:C code都寫好放那邊了,OK的啦 XD 05/14 00:54
17F:推 Archezoa:可是還要記錄threaded 我覺得可能變快 但不會省得樣子 05/14 01:18
18F:→ bnsblue:有要多用ptr嗎?不是直接用leaves的左右子樹去指就好? 05/14 01:24
19F:推 timrau:threaded可以偷用pointer的最後2 bits.... 05/14 01:25
20F:推 Archezoa:哈~ 那還真是蠻麻煩的 05/14 01:52