(01) 當樹的高度h=0時，
? ? 內節點個數是0，bh(x) 為0，2^bh(x)-1 也為 0。顯然，原命題成立。

(02) 當h>0，且樹的高度為 h-1 時，它包含的節點個數至少為 2^bh(x)-1-1。這個是根據(01)推斷出來的！

? ? 下面，由樹的高度為 h-1 的已知條件推出“樹的高度為 h 時，它所包含的節點樹為 2^bh(x)-1”。

? ? 當樹的高度為 h 時，
? ? 對于節點x(x為根節點)，其黑高度為bh(x)。
? ? 對于節點x的左右子樹，它們黑高度為 bh(x) 或者 bh(x)-1。
? ? 根據(02)的已知條件，我們已知 "x的左右子樹，即高度為 h-1 的節點，它包含的節點至少為 2^bh(x)-1-1 個"；

? ? 所以，節點x所包含的節點至少為 ( 2^bh(x)-1-1 ) + ( 2^bh(x)-1-1 ) + 1 = 2^^bh(x)-1。即節點x所包含的節點至少為 2^bh(x)-1。
? ? 因此，原命題成立。

? ? 由(01)、(02)得出，"高度為h的紅黑樹，它的包含的內節點個數至少為 2^^bh(x)-1個"。
? ? 因此，“一棵含有n個節點的紅黑樹的高度至多為2log(n+1)”。

???