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的。谢谢了！
相关阅读
好像核心用C++的公司更成功project architecture方面有什么好书值得推荐的？简单说说这几年机器学习的形势 (转载)cassandra query speed求助一道填空题，请教。江湖险恶啊多少公司用 java guice 这烂玩意？IntelliJ热部署经常失败是什么原因？请教移动开发的framework问题react is total crap问个问题，关于隐藏实现细节, C plusplus探讨一下API Gateway和Proxy的关系Java基于DI解决runtime dependency和异步执行，有啥好轮子？VisualStudio的LoadTest咋入门？headless chrome要出来了 不用再将就破phantom了90后贪玩CEO,被扎克伯格相中,创20亿收购神话(图)再挖一个语言坑：scala流年不顺msft买错了，应该买亚麻啊用python生成傻shell脚本如何？为了反对游戏审查条例 一位从业者众筹3万准备起诉广电 (转载)