紅黑樹

概念

紅黑樹是AVL樹的變種，具體定義如下：紅黑樹也是一棵二叉查找樹，要滿足一下性質

（1）每個節點或者是黑色，或者是紅色。

（2）根節點是黑色。

（3）每個葉子節點（NIL）是黑色。

（4）如果一個節點是紅色的，則它的子節點必須是黑色的。

（5）從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。

定義：從某個節點x出發（不包括該節點）到達一個葉節點的任意一條路徑上，黑色節點的個數稱為該節點的黑高度，記為bh(x)

紅黑樹的黑高度定義為bh(root).

1  證明： 根到任一個葉子的最短可能的路徑上全是黑節點， 而最長路徑根據性質3最壞的情況就是紅黑節點交替，而又根據性質4 最長和最短路徑上的黑節點數目相同，

則最長路徑的長度應小于或等于最短路徑的2倍

引理：

2   定理：一棵含有n個節點的紅黑樹的高度至多為2log(n+1).

原題等價于證明node x底下的subtree最少有2^bh（x）-1   internal node <=>bh(x)=log(n+1)，

對于高度為h的紅黑樹，它的包含的内節點個數至少為 2^{h/2}-1個，因為bh(x)>=h/2,

是以隻要證明 它包含的内節點的個數至少為2^bh(x)-1個。

數學歸納法證明，

對于h=0，則内節點個數是0顯然成立；

假設當x的height為正整數, 且是一個有兩個children的internal node. 每個小孩的black height為bh(x) or bh(x)‐1. (看

該小孩是黑是紅)，假設小孩的subtree都至少有2^（bh（x）-1）-1個internal node

對于節點x，其黑高度為bh(x)，則其左右子樹的黑高度為 bh(x) 或者 bh(x)-1，但是高度減少至少1，節點至少為 2*(2^（bh(x)-1）-1）+1=2^bh(x)-1個. 結論得證

​​http://www.csie.ntu.edu.tw/~hsinmu/courses/lib/exe/fetch.php?media=dsa1_10fall:lecture15.pdf​​