作者ric2k1 (Ric)
看板EE_DSnP
标题[公告] 关於 bst 里用 array 的界线
时间Sun Dec 6 21:33:51 2009
有几位同学在问如果用 array 来 implement bst，可以吗?
我想 bottom line is:
如果你只是空有 bst 的壳子，但是骨子里根本就是 array 的操作话，
当然不行! 那是视同作弊，发现的话就直接Ｄ掉！
不过如果你的想法是像讲义 page 32 (Memory Usage Consideration) 所说的，
将所有的 data 存在一个 array 里，然後用 index, instead of using pointers,
来 access child nodes 的话，那是可以的!
或者是说，你让 bst 尽量保持 balance so that you can store the data in a
"complete bst"，然後用 array 来存这个 bst 以及做 node access 的话，
这也是可以的!
总而言之，你的 bst 必须符合 bst 的操作与精神，如果有用 array 的话，请注意:
1. Array 里面的 data 不应该照 ascending order 排。
2. Memory usage should be close to O(n)。
如有其他的想法与问题，欢迎分享!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.224.42.19