导航菜单
路很长,又很短
博主信息
昵   称:Cocodroid ->关于我
Q     Q:2531075716
博文数:308
阅读量:796962
访问量:73865
至今:
×
云标签 标签球>>
云标签 - Su的技术博客
Tags : 红黑树发表时间: 2019-04-03 00:03:24

上一篇文章史上最清晰的红黑树讲解(上)对Java TreeMap的插入以及插入之后的调整过程给出了详述。本文接着以Java TreeMap为例,从源码层面讲解红黑树的删除,以及删除之后的调整过程。如果还没有看过上一篇文章,请在阅读本文之前大致浏览一下前文,以方便理解。

寻找节点后继

对于一棵二叉查找树,给定节点t,其后继(树种比大于t的最小的那个元素)可以通过如下方式找到:

  1. t的右子树不空,则t的后继是其右子树中最小的那个元素。
  2. t的右孩子为空,则t的后继是其第一个向左走的祖先。

后继节点在红黑树的删除操作中将会用到。

...阅读原文