教甄◆電腦科專業題庫下載題庫

紅黑樹是每個節點都帶有顏色屬性的二元搜尋樹，顏色為紅色或黑色。在二元搜尋樹強制一般要求以外，對於任何有效的紅黑樹我們增加了如下的額外要求:

性質1. 節點是紅色或黑色。

性質2. 根是黑色。

性質3. 所有葉子都是黑色（葉子是NIL節點）。

性質4. 每個紅色節點必須有兩個黑色的子節點。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點。)

性質5. 從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。