Re: [商管] [資結] BST

看板Grad-ProbAsk作者 (SM)時間14年前 (2011/03/24 17:38), 編輯推噓1(1推 0噓 4→)
留言5則, 2人參與, 最新討論串2/2 (看更多)
※ 引述《koehie (開喜烏龍茶)》之銘言： : 假設六個鍵（key）插入（insert）一個不平衡的二元搜尋樹（unbalanced binary : search tree）的順序如下：4，6，3，8，2，5。以下那項陳述是正確的？①在這個二元 : 搜尋樹搜尋一個鍵（key）需要檢查1，2或3個節點（node） ②這個二元搜尋樹具有相同 : 數量的內部（internal）和葉（leaf）節點（node） ③在這個二元搜尋樹插入（insert : ）新鍵（key）7不需增加另一層次（level） : 這題答案是給 A ； 題目的意思是說一顆已存在還是未存在的不平衡的二元搜尋樹呢 ? : 這一題題目我完看不懂它的意思，請問它到底要求什麼呢 ?
→
03/24 16:49,
可以請你更清楚的解釋題目所提出的 3 點為什麼是正確的或
03/24 16:49
→
03/24 16:49,
錯誤的，謝謝。
03/24 16:49
以下是根據題目所給的sequtial key 所建立的BST level 4 1 / \ 3 6 2 / / \ 2 5 8 3 加入7後 level 4 1 / \ 3 6 2 / / \ 2 5 8 3 / 7 4 增加了一個level,所以選項3錯誤 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.248.220.89 ※ 編輯: SkullMaster 來自: 111.248.220.89 (03/24 17:39)
推
03/24 21:08, , 1F
(1)題目所說需檢查 1, 2 或 3 節點是指檢查節點 4, 節點 6
03/24 21:08, 1F
→
03/24 21:10, , 2F
或節點 3 嗎 ? (2)內部節點有 2 個和樹葉節點有 3 個 ?
03/24 21:10, 2F
→
03/24 21:35, , 3F
(1)因為樹高為3,所以最多檢查3次,即知搜尋成功或失敗
03/24 21:35, 3F
→
03/24 21:36, , 4F
(2)key 4,3,6為內部節點,key2,5,8為外部節點(leaf)
03/24 21:36, 4F
→
03/24 23:44, , 5F
喔，謝謝。
03/24 23:44, 5F
‣ 更多 SkullMaster 的文章
文章代碼(AID): #1DYn4ksL (Grad-ProbAsk)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共2篇)
‣ 更多 SkullMaster 的文章
文章代碼(AID): #1DYn4ksL (Grad-ProbAsk)