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