红黑树的高度

摘要

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