红黑二叉树

红黑二叉树

      红黑二叉树(简称：红黑树)，它首先是一棵二叉树，同时也是一棵自平衡的排序二叉树。

      红黑树在原有的排序二叉树增加了如下几个要求：

      1. 每个节点要么是红色，要么是黑色。

      2. 根节点永远是黑色的。

      3. 所有的叶节点都是空节点(即 null)，并且是黑色的。

      4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的路径上不会有两个连续的红色节点)

      5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

      这些约束强化了红黑树的关键性质：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。这样就让树大致上是平衡的。

      红黑树是一个更高效的检索二叉树，JDK 提供的集合类 TreeMap、TreeSet 本身就是一个红黑树的实现。

红黑树的基本操作：插入、删除、左旋、右旋、着色。 每插入或者删除一个节点，可能会导致树不在符合红黑树的特征，需要进行修复，进行 “左旋、右旋、着色”操作，使树继续保持红黑树的特性。