红黑树的高度

摘要

先证明高度是h的准红黑树至少有2「h/2(┐)+2(└)h/2」-2个结点.再证明有n个结点的准红黑树的高度至多是2(└)log2(n+2)」+(└)log2(n+2)- (└)log2(n+2)」/log23-1」-2.最后证明有n个结点的红黑树的高度至多是2(└)log2(n+2)」+(└)log2(n+2)-(└)log2(n+2)」/log23-1」-2,该式比原来的2(└)log2(n+1)」+1准确.有n个结点的红黑树的高度在(└)log2(n+1)」和2(└)log2(n+2)」+(└)log2(n+2)- (└)log2(n+2」/log23-1」-2之间.此文进一步完善了红黑树的性质.