HashMap中红黑树插入节点的调整过程

一、引言

如果有对红黑树的定义及调整过程有过研究,其实很容易理解HashMap中的红黑树插入节点的调整过程。

“红黑树定义及调整过程”的参考文章:《红黑树原理、查找效率、插入及变化规则分析》

下面的流程图就是HashMap源码中,红黑树插入节点的调整过程。这个过程要是写文章讲的话,感觉也没什么意思,其实关键还是需要你要清楚红黑树的定义及调整过程,然后知道数据结构里二叉树左旋、右旋调整的过程。接下来需要做的,就是慢慢啃这段不长的源码。

你看到最后会发现,这个过程中的判断、步骤,都是基于我上面说的:红黑树的定义、红黑树的调整过程、二叉树左旋/右旋调整的过程,然后就是一些指针操作。

二、HashMap源码中红黑树插入节点的调整过程

HashMap中红黑树插入节点的调整过程

三、阅读HashMap源码的一些Tips

1. 代码风格

HashMap源码中特别喜欢在判断语句中加赋值语句,形如:if ((xp = x.parent) == null)。它这一行代码做了两件事:

  1. 把x.parent赋值给xp
  2. 判断xp是否为null

还喜欢使用连等号,形如:pp = r.parent = p.parent。它这一行代码也做了两件事:

  1. 把p.parent赋值给r.parent
  2. 把r.parent赋值给pp

这种代码风格我看着很不习惯,但是看多了后,也就习惯了。

2. 变量名

源码中的树指针的变量命名其实很有规律:r对应右子树,l对应左子树,p对应父节点,pp对应爷爷节点。
举个例子:变量名pr的含义是,父节点的右子树。

balanceInsertion方法中的变量名

root x所在树的根节点 x    要插入的节点 xp   x的parent节点 xpp  x的parent的parent -> 爷爷节点 xppl x的爷爷节点的左子树 xppr x的爷爷节点的右子树                    +-----+              +----+     +----+              |    +-----+    |              |      xpp      |           +--v--+         +--v--+    +------+     |         |     |    |      +-----+         +-----+    |        xppl            xppr +--v--+      xp |     | +-----+    x  

rotateLeftrotateRight方法中的变量名

p    旋转的关键点 pp   p的parent节点 r    p的右子节点节点 l    p的左子节点节点 rl   p的右子节点节点的左子节点 lr   p的左子节点节点的右子节点 
发表评论

相关文章