75. 關於紅黑樹(Red-Black Tree)，下列哪項是正確的?
(A)根(root)總是紅色的
(B)節點總是黑色的
(C)從根到葉子(leaf node)的任何路徑中，黑色節點的數量相同
(D)一個紅色節點總是有紅色的子節點

答案：登入後查看
統計： A(11), B(13), C(65), D(13), E(0) #3120488

詳解 (共 3 筆)

#5862136
紅黑樹是一種自平衡的二叉搜索樹，其特點是...
(共 211 字，隱藏中）
前往觀看
10
0
#6342689
https://medium.com/%40imprld01/red-black-tree-%E7%B4%85%E9%BB%91%E6%A8%B9-8d793e692d70
0
0
#6477457

好的，我們來分析關於紅黑樹 (Red-Black Tree) 的各項敘述，找出正確的一個。

紅黑樹是一種自平衡二元搜尋樹，它透過滿足以下五個性質來保證樹的平衡：

  1. 節點顏色： 每個節點都是紅色或黑色。
  2. 根節點： 根節點總是黑色的。
  3. 紅色節點限制： 如果一個節點是紅色的，那麼它的子節點（如果存在）必須都是黑色的。
  4. 路徑黑色節點數： 從根節點到任意葉節點（或空節點，通常被視為黑色的虛擬葉節點）的任何路徑上，所包含的黑色節點數量必須相同。這個數量稱為樹的「黑色高度」。
  5. 空節點： 所有的葉節點（NIL 節點，表示空子樹）都是黑色的。

現在我們來逐一分析選項：

  • (A) 根(root)總是紅色的

    • 根據紅黑樹的性質 2，根節點總是黑色的。
    • 因此，這個敘述是錯誤的。

  • (B) 節點總是黑色的

    • 根據紅黑樹的性質 1，節點可以是紅色或黑色。
    • 因此，這個敘述是錯誤的。

  • (C) 從根到葉子(leaf node)的任何路徑中，黑色節點的數量相同

    • 根據紅黑樹的性質 4，這是紅黑樹的一個核心特性，稱為「黑色高度一致性」。
    • 因此，這個敘述是正確的。

  • (D) 一個紅色節點總是有紅色的子節點

    • 根據紅黑樹的性質 3，如果一個節點是紅色的，那麼它的子節點必須都是黑色的。
    • 因此，這個敘述是錯誤的。

綜上所述，只有選項 (C) 的敘述是正確的。

The final answer is C​

0
0