上一篇文章史上最清晰的红黑树讲解(上)对Java TreeMap的插入以及插入之后的调整过程给出了详述。本文接着以Java TreeMap为例,从源码层面讲解红黑树的删除,以及删除之后的调整过程。如果还没有看过上一篇文章,请在阅读本文之前大致浏览一下前文,以方便理解。
寻找节点后继
对于一棵二叉查找树,给定节点t,其后继(树种比大于t的最小的那个元素)可以通过如下方式找到:
- t的右子树不空,则t的后继是其右子树中最小的那个元素。
- t的右孩子为空,则t的后继是其第一个向左走的祖先。
后继节点在红黑树的删除操作中将会用到。
...阅读原文