[理工] [資結] tree兩題疑問
以下兩個問題想請教如下:
1. Consider a binary tree T. The maximum number of nodes on level k is
(2^k) - 1(level以1開始). The maximun number of nodes in T of level k is
2^(k-1) . 因此對於任何一個有n個nodes的binary tree T 而言,
它的高度為大寫omega(nlogn).
這是97年成大資管乙的題目，這題答案是true，但是我感到怪怪的，因為n個nodes的
Binary tree最大高度不是才n嗎，怎麼會是題目所說的至少是nlogn呢?
--
2. Without comparing keys in a BST , we cannot determine both the
successor and predecessor of a node.
這題是98年成大資管的題目，這題是false，但我也很不確定，我認為錯的原因，因為可
以拿inorder traversal作為反例，不知道題目是不是要問這個呢?
謝謝大家
--
標題 [問卦] 男女生小時候最愛看的卡通的八卦?
時間 Mon Jun 18 01:34:21 2012
--
→
06/18 01:36,
06/18 01:36
婀 妳好兇喔
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.135.237.24
※ 編輯: vinny200277 來自: 220.135.237.24 (06/28 20:04)
推
06/28 23:38, , 1F
06/28 23:38, 1F
→
06/28 23:41, , 2F
06/28 23:41, 2F
→
06/28 23:41, , 3F
06/28 23:41, 3F