Java JDK TreeMap.java 2650-2651行可以优化

[hunterhug]

此文章Golang实现的2-3-4的红黑树： https://github.com/hunterhug/goa.c/blob/master/code/rbt/main.go#L305

参考的Java JDK (openjdk稳定版本) 中 java.util.TreeMap。

发现Java中的代码2650-2651行有一个不必要的函数进入:

            // Fix replacement
            if (p.color == BLACK)
                fixAfterDeletion(replacement);

可以改为

       setColor(replacement, BLACK);

为此，可以节省 fixAfterDeletion 函数中的一次 while判断，因为那种场景下，不会进入while循环。

分析如下：

删除节点时需要一直在左子树左选择，一直到没有左子树。到最后会有以下两种情况：

两种情况：

case1. 删除的节点是红色节点。
case2. 删除的节点是黑色节点。

case1因为红色节点下面必然有两个黑色儿子，红黑树定义的，所以case1这种情况不会进入fixAfterDeletion这个逻辑，因为它有两个子节点，可以继续向左边选择。

case2，删除的节点是黑色的，它不会有两个儿子，因为有的话，在上面的逻辑会继续选择到左边，它只有一个儿子，它的儿子不可以是黑色，因为破环平衡了，同一个路径只能有相同数量的黑色链接。所以这个儿子一定是红色。

然后fixAfterDeletion函数里面对于replace红色他不进入while循环，直接赋值黑色。

所以我说treemap进入这个fix函数多此一举啊，可以不进去，优化一下，可以少判断一次while。

[hunterhug]

总结：

按照画图思维和红黑树的定义，进入那个逻辑时，

p(在go实现里是node) 一定是黑色的，replacement一定是红色的，所以可以不进入函数，直接渲染黑色节点。

所以可以不用进入fixAfterDeletion函数，在外层渲染节点颜色即可。