红黑树添加新节点转换疑惑

我不确定我是不是正确理解了你的问题。

37 和 66 都是红色，只是算法的中间步骤，算法还没有结束。之后依靠 flipColors，红节点向上转移。请参考后两页 ppt。

如果最终 42 是整棵树的根节点，42 会在最后转为黑色。因为根节点永远是黑色的。参考我们写的代码第 95 行：https://git.imooc.com/class-104/Play-Algorithms-and-Data-Structures/src/master/26-Red-Black-Tree/07-Adding-Elements-in-Red-Black-Tree/src/RBTree.java

所以，是的，如果这棵树就这三个节点，最终和他们都是黑色的。

你可以尝试一下，用这个例子，使用我们自己写的代码，用单步跟踪的方式观察一下，每添加一个节点，各个节点的 color 是怎么变化的？再理解一遍这个过程。

继续加油！：）