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

核心提示： 查看原图（大图）TreeMap 删除节点采用图 5 所示右边的情形进行维护——也就是用被删除节点的右子树中最小节点与被删节点交换的方式进行维护，TreeMap 删除节点的方法由如下方法实现：privatevoiddeleteEntry(Entry<K,V>p)

查看原图（大图）

TreeMap 删除节点采用图 5 所示右边的情形进行维护——也就是用被删除节点的右子树中最小节点与被删节点交换的方式进行维护。

TreeMap 删除节点的方法由如下方法实现：

　private　void　deleteEntry(Entry<K,V>　p)　
　{　
　　modCount++;　
　　size--;　
　　//　如果被删除节点的左子树、右子树都不为空　
　　if　(p.left　!=　null　&&　p.right　!=　null)　
　　{　
　　　　//　用　p　节点的中序后继节点代替　p　节点　
　　　　Entry<K,V>　s　=　successor　(p);　
　　　　p.key　=　s.key;　
　　　　p.value　=　s.value;　
　　　　p　=　s;　
　　}　
　　//　如果　p　节点的左节点存在，replacement　代表左节点；否则代表右节点。　
　　Entry<K,V>　replacement　=　(p.left　!=　null　?　p.left　:　p.right);　
　　if　(replacement　!=　null)　
　　{　
　　　　replacement.parent　=　p.parent;　
　　　　//　如果　p　没有父节点，则　replacemment　变成父节点　
　　　　if　(p.parent　==　null)　
　　　　　　root　=　replacement;　
　　　　//　如果　p　节点是其父节点的左子节点　
　　　　else　if　(p　==　p.parent.left)　
　　　　　　p.parent.left　=　replacement;　
　　　　//　如果　p　节点是其父节点的右子节点　
　　　　else　
　　　　　　p.parent.right　=　replacement;　
　　　　p.left　=　p.right　=　p.parent　=　null;　
　　　　//　修复红黑树　
　　　　if　(p.color　==　BLACK)　
　　　　　　fixAfterDeletion(replacement);　　　　//　①　
　　}　
　　//　如果　p　节点没有父节点　
　　else　if　(p.parent　==　null)　
　　{　
　　　　root　=　null;　
　　}　
　　else　
　　{　
　　　　if　(p.color　==　BLACK)　
　　　　　　//　修复红黑树　
　　　　　　fixAfterDeletion(p);　　　　　　　　　//　②　
　　　　if　(p.parent　!=　null)　
　　　　{　
　　　　　　//　如果　p　是其父节点的左子节点　
　　　　　　if　(p　==　p.parent.left)　
　　　　　　　　p.parent.left　=　null;　
　　　　　　//　如果　p　是其父节点的右子节点　
　　　　　　else　if　(p　==　p.parent.right)　
　　　　　　　　p.parent.right　=　null;　
　　　　　　p.parent　=　null;　
　　　　}　
　　}　
　}