樹結構 - 練習題¶

Q1. BST 性質判斷 (114)¶

Select all the correct statement(s) from the following statements regarding binary trees and binary search trees.

(A) Every binary tree is a binary search tree.
(B) Every binary search tree on n nodes has height \(O(\log n)\).
(C) In a binary search tree, we can find the next smallest element to a given element in \(O(1)\) time.
(D) Let \(A_1\), \(A_2\), and \(A_3\) be three sorted arrays of n distinct real numbers. Constructing a balanced binary search tree of the set \(A_1 \cup A_2 \cup A_3\) requires \(O(n)\) time.
(E) Let T be a complete binary tree with n nodes. Finding a path from the root of T to a given vertex \(v \in T\) using breadth-first search takes \(\Omega(n \lg n)\) time.

答案與解析

答案: (D)

解析: - (A) 錯誤: Binary tree 沒有排序性質，BST 要求左<根<右 - (B) 錯誤: BST 可能退化成鏈表，高度 \(O(n)\)。只有平衡 BST 才是 \(O(\log n)\) - (C) 錯誤: 找 successor 需要 \(O(h)\) 時間，h 是樹高 - (D) 正確: 三個已排序陣列可以 \(O(n)\) merge，然後 \(O(n)\) 建平衡 BST - (E) 錯誤: BFS 在 complete binary tree 找路徑是 \(O(n)\)，不是 \(\Omega(n \lg n)\)

Q2. B+ Tree 違規檢查 (112)¶

B+ tree is an extension of B tree. The major differences from B tree are (1) all leaf nodes are linked together in a doubly-linked list, and (2) data points are stored on the leaf nodes only; internal nodes only hold keys and act as routers to the correct leaf node; the left child is smaller than the key and the right child is larger or equal than that. Please find any/all violations of a B+ tree structure in the following diagram. Assume the tree node can at most contain 4 data points (keys).

                    20
                   /  \
              (A)10    30,40
                / \      /|\
             6,8 (B)13,20  22,27  33,36  47,52
                        (C)      (D)     (E)

答案與解析

答案: (B), (C), (E) 有違規

解析: B+ Tree 規則檢查： - (A) 10: 正確，作為 router - (B) 13,20: 違規 - 20 應該在右子樹（≥20 的應該往右），但 20 出現在左邊的葉子 - (C) 22,27: 違規 - 這應該是 30 的左子樹，但包含 22,27 < 30，需確認是否正確路由 - (D) 33,36: 正確，在 30-40 之間 - (E) 47,52: 違規 - 超過 40，但父節點最大 key 是 40

主要違規： 1. 葉節點的值沒有正確對應到 router keys 2. 結構違反 B+ tree 的搜尋性質

Q3. Tree Traversal - Postorder (110)¶

There is a binary tree stored in an array as:

\[T[] = \{+, a, *, null, null, -, d, null, null, null, null, b, c\}\]

in which \(T[i]\) is the parent of \(T[2i+1]\) and \(T[2i+2]\), where \(i\) is an index and null means there is no element in the slot.

(a) What is its postorder traversal result?

答案與解析

答案: (C) \(abc-d*+\)

解析: 首先建構樹的結構：

+
/ \
a   *
/ \
-   d
/ \
b   c

Postorder (左→右→根): 1. 訪問左子樹 a → 輸出 a 2. 訪問右子樹 *： - 訪問 - 的左子樹 b → 輸出 b - 訪問 - 的右子樹 c → 輸出 c - 輸出 - - 訪問 d → 輸出 d - 輸出 * 3. 輸出 +

結果: \(abc-d*+\)

Q4. AVL Tree 性質 (112)¶

The following is a binary tree and the alphabet on the node is simply the "name" (instead of value) of the node. Please select the correct statements from the following:

        A
       / \
      B   C
     /   / \
    D   F   G
   /   / \   \
  H   I   J   L
             /
            M

(A) The successor of node B is E.
(B) The successor of node A is C.
(C) The tree is not a AVL tree.
(D) If we remove node J, the result is an AVL tree.
(E) If we remove node H, the result is an AVL tree.

答案與解析

答案: (C)(E)

解析: （假設這是 BST，節點名稱代表 inorder 順序）

計算各節點的平衡因子 (BF = height(left) - height(right))： - A: height(B subtree)=2, height(C subtree)=3 → BF = -1 ✓ - B: height(D)=1, height(right)=0 → BF = 1 ✓ - C: height(F)=2, height(G)=2 → BF = 0 ✓ - G: height(left)=0, height(L)=1 → BF = -1 ✓ - L: height(M)=0, height(right)=0 → BF = 1 ✓

(C) 正確: 需要仔細檢查，樹可能不平衡 (E) 正確: 移除 H 後，D 變成葉子，樹更平衡

Q5. BST Search 序列 (106)¶

Suppose that we have numbers between 1 and 1000 in a binary search tree and want to search for the number 400. Determine whether the following sequences could be or could not be the sequence of nodes examined and explain why or why not.

(a) 32 500 300 350 400

(b) 900 800 200 699 355 385 412 372 400

答案與解析

答案:

(a) 32 500 300 350 400 - 可能

檢查搜尋路徑合理性： - 32 < 400 → 往右 - 500 > 400 → 往左 - 300 < 400 → 往右 - 350 < 400 → 往右 - 400 找到 ✓

(b) 900 800 200 699 355 385 412 372 400 - 可能

900 > 400 → 往左
800 > 400 → 往左
200 < 400 → 往右
699 > 400 → 往左
355 < 400 → 往右
385 < 400 → 往右
412 > 400 → 往左
372 < 400 → 往右
400 找到 ✓

515 > 400 → 往左
1 < 400 → 往右
500 > 400 → 錯誤！

500 > 515，但我們是從 515 往左到 1，再往右應該 < 515。 500 > 400 應該往左，但這違反了 BST 性質（我們已經在 < 515 的子樹中，不應該看到 500 在 1 的右邊同時還 > 400）

Q6. Red-Black Tree 性質 (109)¶

A red-black tree is a binary tree where every node has a color (red or black), and has the following properties:

The root is black.
All paths from the root to a leaf have the same number of black nodes.
Every red node must have two black children.

For ease of discussion we assume that all null pointers point to a special black node. Select all correct statement(s).

(1) If we do not guarantee the first property, but still guarantee the second and the third properties, we will not be able to guarantee that the height of the tree is \(O(\log n)\).
(2) It is possible that there are no red nodes in a red-black tree of 100000 nodes.
(3) We insert a key k into a non-empty red-black tree just like into an ordinary binary search tree as a leaf, attach to it two null pointers to the special black node, and then immediately stop without any adjustment. If we color k red, we may violate the second property above.
(4) Consider the scenario above. If we color k red, we may violate the third property above.
(5) Consider the scenario above. If we color k black, we will violate the second property above.

答案與解析

答案: (4)(5)

解析: - (1) 錯誤: 即使 root 不是黑色，性質 2 和 3 仍能保證 \(O(\log n)\) 高度 - (2) 錯誤: 100000 節點的完全黑色樹無法滿足性質 2（路徑長度不一致） - (3) 錯誤: 插入紅色節點不影響黑色節點數量，性質 2 不會違反 - (4) 正確: 如果父節點是紅色，插入紅色節點會違反性質 3（紅色節點的子節點必須是黑色） - (5) 正確: 插入黑色節點會增加該路徑的黑色節點數，違反性質 2

延伸練習¶

更多樹結構相關題目： - 107 Data Structure.Pdf Q13-Q16 - AVL 操作 - 113 Data Structure.Pdf Q5 - BST Join 操作

Nav