| 红黑树的高度 |
| |
| 引用本文： | 唐自立. 红黑树的高度[J]. 苏州大学学报(医学版), 2006, 22(3): 33-36 |
| |
| 作者姓名： | 唐自立 |
| |
| 作者单位： | 苏州大学计算机科学与技术学院 江苏苏州215006 |
| |
| 摘 要： | 先证明高度是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之间.此文进一步完善了红黑树的性质.
|
| 关 键 词： | 红黑树 对称二叉B-树 2-3-4树 准红黑树 高度 黑高度 |
| 文章编号： | 1000-2073(2006)03-0033-04 |
| 收稿时间： | 2006-01-06 |
| 修稿时间： | 2006-01-06 |
Height of a red-black tree |
| |
| TANG Zi-li. Height of a red-black tree[J]. Journal of Suzhou University(Natural Science), 2006, 22(3): 33-36 |
| |
| Authors: | TANG Zi-li |
| |
| Affiliation: | School of Computer Science and Technology, Suzhou Univ. , Suzhou 215006, China |
| |
| Abstract: | |
| |
| Keywords: | red-black tree symmetric binary B-tree 2-3-4 tree almost-red-black tree height black-height |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
