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