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