作者SweepingMonk ((((((((((()))))))))))
看板EE_DSnP
標題[問題] 關於bst的size()
時間Sun May 18 23:09:18 2008
請問
在bst中 有沒有什麼比較好的方法來implement size()呢？
我想到的只有從最小的往上慢慢數...
但是這樣非常慢，還不如在BSTree裡面加入一個size的member
請問有沒有什麼好一點的辦法呢？
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.70.216.237
1F：推 timrau:不需要由小往大數，直接從root開始DFS/BFS走一遍就算完了 05/18 23:24
2F：推 danielko:return 1+size(subtree->_left)+size(subtree->_right); 05/19 00:52
3F：→ SweepingMonk:感謝樓上 不過recursive的做法會不會讓程式更慢呢？ 05/19 01:17
4F：推 spock:應該不會慢太多，倒是記憶體用量會以指數爆增，記憶體吃完 05/19 06:12
5F：→ spock:就會開始龜速了 囧rmmmmmmmmm... 05/19 06:13
6F：推 ric2k1:這種 recursive 吃的記憶體是很少的, 應該不至於影響速度 05/19 09:27