Re: [商管] [資結] BST

[SkullMaster (SM)]

※ 引述《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 ； 題目的意思是說一顆已存在還是未存在的不平衡的二元搜尋樹呢 ?
: 這一題題目我完看不懂它的意思，請問它到底要求什麼呢 ?



→ koehie:可以請你更清楚的解釋題目所提出的 3 點為什麼是正確的或
→ koehie:錯誤的，謝謝。
以下是根據題目所給的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)
推 koehie:(1)題目所說需檢查 1, 2 或 3 節點是指檢查節點 4, 節點 6
→ koehie:或節點 3 嗎 ? (2)內部節點有 2 個和樹葉節點有 3 個 ?
→ SkullMaster:(1)因為樹高為3,所以最多檢查3次,即知搜尋成功或失敗
→ SkullMaster:(2)key 4,3,6為內部節點,key2,5,8為外部節點(leaf)
→ koehie:喔，謝謝。