通过分析 JDK 源代码研究 TreeMap 红黑树算法实现

核心提示： 但在红黑树上进行插入操作和删除操作会导致树不再符合红黑树的特征，因此插入操作和删除操作都需要进行一定的维护，通过分析 JDK 源代码研究 TreeMap 红黑树算法实现(10)，以保证插入节点、删除节点后的树依然是红黑树，添加节点后的修复上面 put(K key, V value) 方法中①号代

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

添加节点后的修复

上面 put(K key, V value) 方法中①号代码处使用fixAfterInsertion(e) 方法来修复红黑树——因此每次插入节点后必须进行简单修复，使该排序二叉树满足红黑树的要求。

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

（1）以排序二叉树的方法插入新节点，并将它设为红色。

（2）进行颜色调换和树旋转。

插入后的修复

在插入操作中，红黑树的性质 1 和性质 3 两个永远不会发生改变，因此无需考虑红黑树的这两个特性。

这种颜色调用和树旋转就比较复杂了，下面将分情况进行介绍。在介绍中，我们把新插入的节点定义为 N 节点，N 节点的父节点定义为 P 节点，P 节点的兄弟节点定义为 U 节点，P 节点父节点定义为 G 节点。

下面分成不同情形来分析插入操作

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

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

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

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

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

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