不要慕码人我要切诺基
(01) 当树的高度h=0时， 内节点个数是0，bh(x) 为0，2bh(x)-1 也为 0。显然，原命题成立。(02) 当h>0，且树的高度为 h-1 时，它包含的节点个数至少为 2bh(x)-1-1。这个是根据(01)推断出来的！ 下面，由树的高度为 h-1 的已知条件推出“树的高度为 h 时，它所包含的节点树为 2bh(x)-1”。 当树的高度为 h 时， 对于节点x(x为根节点)，其黑高度为bh(x)。 对于节点x的左右子树，它们黑高度为 bh(x) 或者 bh(x)-1。 根据(02)的已知条件，我们已知 "x的左右子树，即高度为 h-1 的节点，它包含的节点至少为 2bh(x)-1-1 个"； 所以，节点x所包含的节点至少为 ( 2bh(x)-1-1 ) + ( 2bh(x)-1-1 ) + 1 = 2^bh(x)-1。即节点x所包含的节点至少为 2bh(x)-1。 因此，原命题成立。 由(01)、(02)得出，"高度为h的红黑树，它的包含的内节点个数至少为 2^bh(x)-1个"。 因此，“一棵含有n个节点的红黑树的高度至多为2log(n+1)”。