Java 8中的红黑树

红黑树

 

红黑树是每个节点都带有颜色属性的平衡二叉查找树 ，颜色为红色或黑色。除了二叉查找树一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

（1） 节点是要么红色或要么是黑色。

（2） 根一定是黑色节点。

（3） 每个叶子结点都带有两个空的黑色结点（称之为NIL节点，它又被称为黑哨兵）。

（4） 每个红色节点的两个子节点都是黑色（或者说从每个叶子到根的所有路径上不能有两个连续的红色节点）。

（5） 从任一节点到它所能到达得叶子节点的所有简单路径都包含相同数目的黑色节点。

这些性质保证了根节点到任意叶子节点的路径长度，最多相差一半（因为路径上的黑色节点相等，差别只是不能相邻的红色节点个数），所以红黑树是一个基本平衡的二叉搜索树，它没有AVL树那么绝对平衡，但是同样的关键字组成的红黑树相比AVL旋转操作要少，而且删除操作也比 AVL 树效率更高，实际应用效果也比 AVL 树更出众。当然红黑树的具体实现也复杂的多。

黑哨兵节点的作用:

红黑树的这5个性质中，第3点是比较难理解的，但它却非常有必要。我们看上面这张图，如果不使用黑哨兵，它完全满足红黑树性质，根结点5到两个叶结点1和叶结点9路径上的黑色结点数都为3个，且没有连续红色节点。

但如果加入黑哨兵后，叶结点的个数变为 8 个黑哨兵，根结点5到这8个叶结点路径上的黑高度就不一样了，所以它并不是一棵红黑树。NIL节点的存在还可以使得红黑树在代码实现方面得到简化，在具体实现过程中我们只需要 1个NIL节点即可。

为了简化代码和减少不必要的开销，在具体的实现中我们定义一个伪根节点 ROOT 且只定义一个 NIL 节点。伪根节点的左子支永远指向 NIL 节点，NIL 节点的左右子支又指向它自身。伪根节点的右子支才表示真正的红黑树。( jdk 中 treemap 的实现,貌似没有用到黑哨兵节点)