e*r
2 楼
资料说红黑树的高度最高不超过2lgN. 想知道这个系数"2"是怎么来的。
最好能给出一个输入串，生成的红黑树，高度为2logN的。谢谢了！
最好能给出一个输入串，生成的红黑树，高度为2logN的。谢谢了！
e*r
3 楼
找到答案了：
http://www.frontfree.net/view/article_606.html
从根结点到叶结点的黑色结点数被称为树的“黑色高度”(black-height)。前面关于红
黑树的性质保证了从根结点到叶结点的路径长度不会超过任何其他路径的两倍。
我们来解释一下这个结论。考虑一棵黑色高度为3的红黑树：从根结点到叶结点的最短
路径长度显然是2(黑-黑-黑)，最长路径为4(黑-红-黑-红-黑)。由于性质4，不可能在
最长路经中加入更多的黑色结点，此外根据性质3，红色结点的子结点必须是黑色的，
因此在同一简单路径中不允许有两个连续的红色结点。综上，我们能够建立的最长路经
将是一个红黑交替的路径。
由此我们可以得出结论：对于给定的黑色高度为n的红黑树，从根到叶结点的简单路径
的最短长度为n-1，最大长度为2(n-1)。
http://www.frontfree.net/view/article_606.html
从根结点到叶结点的黑色结点数被称为树的“黑色高度”(black-height)。前面关于红
黑树的性质保证了从根结点到叶结点的路径长度不会超过任何其他路径的两倍。
我们来解释一下这个结论。考虑一棵黑色高度为3的红黑树：从根结点到叶结点的最短
路径长度显然是2(黑-黑-黑)，最长路径为4(黑-红-黑-红-黑)。由于性质4，不可能在
最长路经中加入更多的黑色结点，此外根据性质3，红色结点的子结点必须是黑色的，
因此在同一简单路径中不允许有两个连续的红色结点。综上，我们能够建立的最长路经
将是一个红黑交替的路径。
由此我们可以得出结论：对于给定的黑色高度为n的红黑树，从根到叶结点的简单路径
的最短长度为n-1，最大长度为2(n-1)。
t*t
4 楼
指个方向
almost complete BT高度大约是log N
红黑树的特性: 每个根到叶子的路径上黑节点的数目都一样, 且红节点最多占一半
所以最高的叶子高度不会超过最低叶子的两倍
【在 e***r 的大作中提到】
: 资料说红黑树的高度最高不超过2lgN. 想知道这个系数"2"是怎么来的。
: 最好能给出一个输入串，生成的红黑树，高度为2logN的。谢谢了！
almost complete BT高度大约是log N
红黑树的特性: 每个根到叶子的路径上黑节点的数目都一样, 且红节点最多占一半
所以最高的叶子高度不会超过最低叶子的两倍
【在 e***r 的大作中提到】
: 资料说红黑树的高度最高不超过2lgN. 想知道这个系数"2"是怎么来的。
: 最好能给出一个输入串，生成的红黑树，高度为2logN的。谢谢了！
相关阅读
问一个java的面试题 (转载)问个C语言里面全局变量和本地变量引用问题Share a video about designpython+GAE 词典机器人问个内存的问题新手问题：javascript做的网页如何post和get数据?请教: eclipse setup problem请教一个转行的问题这个版求助：帮忙修复一个损坏的文本文件，有包子黑客怎么入门Excel VBA中mode 函数求助设计一个string class，是应该用linked list还是array?Financial software development job opening at State StreetLooking for a PHP programmer什么样的device需要操作系统呢？Job opening程序中的各个变量/数组的内存地址是否会混在一起?关于windows简单编程，那种入门最好？大家推荐一本新手用的学Visual C＃的书啊？？