紅黑樹的性質：
- 每個節點要么是紅色，要么是黑色。
- 根是黑色的。
- 每片葉子 (NIL) 都是黑色的。
- 如果一個節點是紅色的，那么它的兩個子節點都是黑色的。
- 對于每個節點，從節點到后代葉子的所有簡單路徑都包含相同數量的黑色節點。
根據性質，這些紅黑樹是有效的還是無效的？
一種。 
我認為這是有效的
B. 
我認為這是有效的，但我不確定因為有兩個相鄰的紅色節點？
C。 
我認為這是有效的，但我不確定因為有兩個相鄰的紅色節點？
D. 
我認為這是無效的，因為它違反了屬性 4？
我理解 RBtree 的這些屬性嗎？如果沒有，我錯在哪里？
uj5u.com熱心網友回復：
A, B & D 是有效的紅黑樹
C 不是有效的紅黑樹，因為從根到葉的黑色高度不同。在某些路徑中為 2，在其他路徑中為 1。它違反了您所說的第 5 條規則。
如果 12 的右孩子是黑色的，而 25 的左孩子是黑色的，那么它就是一棵紅黑樹。
uj5u.com熱心網友回復：
你已經正確地列出了紅黑樹的屬性。在四棵樹中，只有 C 不是有效的紅黑樹：
一種。
這是一個有效的樹。
我認為這是有效的，但我不確定因為有兩個相鄰的紅色節點？
這是有效的。紅色節點是兄弟節點沒有問題。他們只是不應該處于親子關系中。
C。
我認為這是有效的，但我不確定因為有兩個相鄰的紅色節點？
它無效。不是因為相鄰的紅色節點，而是因為屬性 5。標簽為 12 的節點具有到其葉子的路徑，其中黑色節點的數量不等。節點 25 相同。
作為一般規則，一個紅色節點永遠不可能有一個 NIL-leaf 作為子節點。它的子節點要么都是 NIL-leaves，要么都是（黑色）內部節點。這是從屬性得出的。
D.
我認為這是無效的，因為它違反了屬性 4？
Property 4 is not violated: the children of the red nodes are NIL leaves (not visualised here), which are black. The fact that these red nodes have black NIL leaves as siblings is irrelevant: there are no rules that concern siblings. So this is valid.
For an example that combines characteristics of tree C and D, see this valid tree depicted in the 
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313561.html