容器学习四：TreeMap源码分析-排序二叉树和红黑树

一.排序二叉树

1. 排序二叉树是一种特殊结构的二叉树，可以非常方便地对树中所有节点进行排序和检索。

2. 排序二叉树要么是一棵空二叉树，要么是具有下列性质的二叉树：

   1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值。

   2. 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值。

 

二.排序二叉树添加节点

     以根节点当前节点开始搜索，拿被添加的节点的值和当前节点的值比较。

1. 如果被添加的节点的值更小，则以当前节点的左子节点作为新的当前节点。
2. 如果被添加的节点的值更大，则以当前节点的右子节点作为新的当前节点。

3. 重复12两个步骤，直到新的当前节点为空，则此地方就是添加节点的地方。

 

三.排序二叉树删除节点

1. 被删除的节点是叶子节点，只需将它从其父节点中删除即可。
2. 被删除节点 p 只有左子树，将 p 的左子树 pL 添加成 p 的父节点的左或者右子树即可(见图2.1)；被删除节点 p 只有右子树，将 p 的右子树 pR 添加成 p 的父节点的左或者右子树即可(见图2.2)。左还是右取决于 p 是其父节点 q 的左、右子节点。
3. 若被删除节点 p 的左、右子树均非空，有两种做法：
   1. 以 p 节点的中序前趋(见图3.1.1)或后继(见图3.1.2)替代 p 所指节点，然后再从原排序二叉树中删去中序前趋或后继节点即可。（也就是用大于 p 的最小节点或小于 p 的最大节点代替 p 节点即可）。
   2. 将 pL 设为 p 的父节点 q 的左或右子节点（取决于 p 是其父节点 q 的左、右子节点），将 pR 设 为 p 节点的中序前趋节点 s 的右子节点（s 是 pL 最右下的节点，也就是 pL 子树中最大的节点）。(见图3.2)

 

四.排序二叉树检索节点

     以根节点当前节点开始检索，拿被检索的节点的值和当前节点的值比较。

1. 如果被检索的节点的值更小，则以当前节点的左子节点作为新的当前节点。
2. 如果被检索的节点的值更大，则以当前节点的右子节点作为新的当前节点。

3. 重复12两个步骤，直到被检索的节点的值和当前节点的值相等，如果找不到返回null。

 

五.红黑树

1. 排序二叉树虽然可以快速检索，但在最坏的情况下：如果插入的节点集本身就是有序的，要么是由小 到大排列，要么是由大到小排列，那么最后得到的排序二叉树将变成链表：所有节点只有左节点（如果插 入节点集本身是大到小排列）；或所有节点只有右节点（如果插入节点集本身是小到大排列）。在这种情 况下，排序二叉树就变成了普通链表，其检索效率就会很差。
2. 为了改变排序二叉树存在的不足，Rudolf Bayer 与 1972 年发明了另一种改进后的排序二叉树：红黑 树，他将这种排序二叉树称为“对称二叉 B 树”，而红黑树这个名字则由 Leo J. Guibas 和 Robert Sedgewick 于 1978 年首次提出。
3. 红黑树是一个更高效的检索二叉树，因此常常用来实现关联数组。典型地，JDK 提供的集合类 TreeMap 本身就是一个红黑树的实现。

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

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

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

   3. 性质 3：所有的叶节点都是空节点（即 null），并且是黑色的。

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

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

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

6. 性质 4 则保证了从根节点到叶子节点的最长路径的长度不会超过任何其他路径的两倍。假如有一棵黑 色高度为 3 的红黑树：从根节点到叶节点的最短路径长度是 2，该路径上全是黑色节点（黑节点 - 黑节点 - 黑节点）。最长路径也只可能为 4，在每个黑色节点之间插入一个红色节点（黑节点 - 红节点 - 黑节点 - 红节点 - 黑节点），性质 4 保证绝不可能插入更多的红色节点。由此可见，红黑树中最长路 径就是一条红黑交替的路径。

7. 由此我们可以得出结论：对于给定的黑色高度为 N 的红黑树，从根到叶子节点的最短路径长度为 N-1 ，最长路径长度为 2 * (N-1)。

8. 排序二叉树的深度直接影响了检索的性能，正如前面指出，当插入节点本身就是由小到大排列 时，排序二叉树将变成一个链表，这种排序二叉树的检索性能最低：N 个节点的二叉树深度就是 N-1。

   红黑树通过上面这种限制来保证它大致是平衡的——因为红黑树的高度不会无限增高，这样保证红黑 树在最坏情况下都是高效的，不会出现普通排序二叉树的情况。

   由于红黑树只是一个特殊的排序二叉树，因此对红黑树上的只读操作与普通排序二叉树上的只读操作 完全相同，只是红黑树保持了大致平衡，因此检索性能比排序二叉树要好很多。

   但在红黑树上进行插入操作和删除操作会导致树不再符合红黑树的特征，因此插入操作和删除操作都 需要进行一定的维护，以保证插入节点、删除节点后的树依然是红黑树。

五.红黑树插入节点后的修复

     插入操作按如下步骤进行：

1. 以排序二叉树的方法插入新节点，并将它设为红色。
2. 进行颜色调换和树旋转（在插入操作中，红黑树的性质 1 和性质 3 两个永远不会发生改变，因此无需考虑红黑树的这两个特 性）。为了介绍的方便，我们把新插入的节点定义 为 N 节点，N 节点的父节点定义为 P 节点，P 节点的兄弟节点定义为 U 节点，P 节点父节点定义为 G 节点。

   1. 情形 1：新节点 N 是树的根节点，没有父节点

      在这种情形下，直接将它设置为黑色以满足性质 2。

   2. 情形 2：新节点的父节点 P 是黑色

      在这种情况下，新插入的节点是红色的，因此依然满足性质 4。而且因为新节点 N 有两个黑色叶子节 点；但是由于新节点 N 是红色，通过它的每个子节点的路径依然保持相同的黑色节点数，因此依然满足 性质 5。

   3. 情形 3：如果父节点 P 和父节点的兄弟节点 U 都是红色

      在这种情况下，程序应该将 P 节点、U 节点都设置为黑色，并将 P 节点的父节点设为红色（用来保 持性质 5）。现在新节点 N 有了一个黑色的父节点 P。由于从 P 节点、U 节点到根节点的任何路径都必 须通过 G 节点，在这些路径上的黑节点数目没有改变（原来有叶子和 G 节点两个黑色节点，现在有叶子 和 P 两个黑色节点）。

   4. 情形 4：父节点 P 是红色、而其兄弟节点 U 是黑色或缺少；且新节点 N 是父节点 P 的右子节点， 而父节点 P 又是其父节点 G 的左子节点。

      在这种情形下，我们进行一次左旋转对新节点和其父节点进行，接着按情形 5 处理以前的父节点 P（ 也就是把 P 当成新插入的节点即可）。这导致某些路径通过它们以前不通过的新节点 N 或父节点 P 的 其中之一，但是这两个节点都是红色的，因此不会影响性质 5。

   5. 情形 5：父节点 P 是红色、而其兄弟节点 U 是黑色或缺少；且新节点 N 是其父节点的左子节点，而 父节点 P 又是其父节点 G 的左子节点。

      在这种情形下，需要对节点 G 的一次右旋转，在旋转产生的树中，以前的父节点 P 现在是新节点 N 和节点 G 的父节点。由于以前的节点 G 是黑色，否则父节点 P 就不可能是红色，我们切换以前的父节 点 P 和节点 G 的颜色，使之满足性质 4，性质 5 也仍然保持满足，因为通过这三个节点中任何一个的 所有路径以前都通过节点 G，现在它们都通过以前的父节点 P。在各自的情形下，这都是三个节点中唯一 的黑色节点。

六.红黑树删除节点后的修复

     与添加节点之后的修复类似的是，TreeMap 删除节点之后也需要进行类似的修复操作，通过这种修复 来保证该排序二叉树依然满足红黑树特征。大家可以参考插入节点之后的修复来分析删除之后的修复。