(01) 當(dāng)樹的高度h=0時，
? ? 內(nèi)節(jié)點個數(shù)是0，bh(x) 為0，2^bh(x)-1 也為 0。顯然，原命題成立。

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

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

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

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

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

???