黑马程序员技术交流社区

标题: 红黑树 [打印本页]

作者: 胡超 时间: 2013-12-15 15:59
标题: 红黑树
红黑树在原有的排序二叉树上增加了如下几个要求：1.每个节点要么是红色，要么是黑色。
2.根节点永远为黑色。
3.所有的叶子节点都是空节点（即null），并且是黑色的。
4.每个红色节点的两个子节点都是黑色的。(从每个叶子到根的路径上不会有两个连续的红色节点)
5.从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

上面的第三点中指出红黑树的每个叶子节点都是空节点，而且叶子节点都是黑色，但是java实现的红黑树将使用null来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，反而看到每个叶子节点都是红色的。

根据第五点，红黑树从根节点到每个叶子节点的路径都包含相同数量的黑色节点，因此从根节点到叶子节点的路径中包含的黑色节点数被称为数的“黑色高度（Black -height）”。

第四点则保证了从根节点到叶子节点的最长路径的长度不会超过其他路径的2倍。因此，红黑树中最长的路径就是一条红黑交替的路径。

由此可以得出结论：对于给定的黑色高度为N的红黑树，丛根到叶子节点的最短路径长度为N-1,最长路径长度为2*（N-1）。

作者: 胡永城 时间: 2013-12-15 16:01
有长见识了，+3

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2