【imitation】評論
紅黑樹是每個節點都帶有顏色屬性的二元搜尋樹，顏色為紅色或黑色。在二元搜尋樹強制一般要求以外，對於任何有效的紅黑樹我們增加了如下的額外要求:性質1. 節點是紅色或黑色。性質2. 根是黑色。性質3. 所有葉子都是黑色（葉子是NIL節點）。性質4. 每個紅色節點必須有兩個黑色的子節點。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點。)性質5. 從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。
【william】評論
红黑树是满二叉树，空叶结点也看作结点阶为 k 的红黑树路径长度最短是 k，最长是 2k（从根到叶的简单路径长度）阶为 k 的红黑树树高最小是 k+1，最高是 2k+1阶为 k 的红黑树的内部结点最少是一棵完全满二叉树，内部结点数最少是 2^k-1n 个内部结点的红黑树树高,最大是 2log2(n+1)+1