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