当某条路径最短时,这条路径必然都是由黑色节点构成。当某条路径长度最长时,这条路径必然是由红色和黑色节点相间构成(性质4限定了不能出现两个连续的红色节点)。而性质5又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点。此时,在路径最长的情况下,路径上红色节点数量 = 黑色节点数量。该路径长度为两倍黑色节点数量,也就是最短路径长度的2倍。举例说明一下,请看下图:
上图画出了从根节点 M 出发的到其叶子节点的最长和最短路径。这里偷懒只画出了两条最长路径,实际上最长路径有4条,分别为:
M -> Q -> O -> N
M -> Q -> O -> p
M -> Q -> Y -> X
M -> Q -> Y -> Z
1
2
3
4
长度为4,最短路径为 M -> E,长度为2。最长路径的长度正好为最短路径长度的2倍。
前面说了关于红黑树的一些性质,这里还需要补充一些其他方面的东西。在红黑树简介一节中说到红黑树被发明出来的时候并不叫红黑树,而是叫做对称二叉 B 树,从名字中可发现红黑树和 B 树(这里指的是2-3树)或许有一定的关联,事实也正是如此。如果对红黑树的性质稍加修改,就能让红黑树和B树形成一一对应的关系。关于红黑树和 B 树关系的细节这里不展开说明了,有兴趣的同学可以参考《算法》第4版,那本书上讲的很透彻。
旋转操作
在分析插入和删除操作前,这里需要插个队,先说明一下旋转操作,这个操作在后续操作中都会用得到。旋转操作分为左旋和右旋,左旋是将某个节点旋转为其右孩子的左孩子,而右旋是节点旋转为其左孩子的右孩子。这话听起来有点绕,所以还是请看下图:
上图包含了左旋和右旋的示意图,这里以右旋为例进行说明,右旋节点 M 的步骤如下:
将节点 M 的左孩子引用指向节点 E 的右孩子
将节点 E 的右孩子引用指向节点 M,完成旋转
上面分析了右旋操作,左旋操作与此类似,大家有兴趣自己画图试试吧,这里不再赘述了。旋转操作本身并不复杂,这里先分析到这吧。