摘要
先证明高度是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之间.此文进一步完善了红黑树的性质.
Firstly, it is proved that an almost-red-black tree of height h has at least 2┌h/2┐＋2└h/2┘-2-2 nodes. Secondly, it is proved that the height of an almost-red-black tree with n nodes is at most 2└log2（n＋2）┘＋└log2（n＋2）-└log2（n＋2）┘/log2 3-1┘-2. Finally, it is proved that the height of a red-black tree with n nodes is at 2└log2（n＋2）┘＋└log2（n＋2）-└log2（n＋2）┘/log2 3-1┘-2, which is more precise than the original formula, 2└log2（n＋1）┘＋1. The height of a red-black tree with n nodes is between └log2（ n ＋ 1）┘ and 2└log2（n＋2）-└log2（n＋2）┘/log2 3-1┘-2. The properties of red-black trees are further perfected.
出处
《苏州大学学报（自然科学版）》
CAS
2006年第3期33-36,共4页
Journal of Soochow University(Natural Science Edition)
关键词
红黑树
对称二叉B-树
2—3—4树
准红黑树
高度
黑高度
red-black tree
symmetric binary B-tree
2-3-4 tree
almost-red-black tree
height
black-height
