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

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

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

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

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

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

???