5
HashMap中红黑树插入节点的调整过程 - daheww
source link: https://www.cnblogs.com/daheww/p/16216250.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
如果有对红黑树的定义及调整过程有过研究，其实很容易理解HashMap中的红黑树插入节点的调整过程。
“红黑树定义及调整过程”的参考文章：《红黑树原理、查找效率、插入及变化规则分析》
下面的流程图就是HashMap源码中，红黑树插入节点的调整过程。这个过程要是写文章讲的话，感觉也没什么意思，其实关键还是需要你要清楚红黑树的定义及调整过程，然后知道数据结构里二叉树左旋、右旋调整的过程。接下来需要做的，就是慢慢啃这段不长的源码。
你看到最后会发现，这个过程中的判断、步骤，都是基于我上面说的：红黑树的定义、红黑树的调整过程、二叉树左旋/右旋调整的过程，然后就是一些指针操作。
二、HashMap源码中红黑树插入节点的调整过程
三、阅读HashMap源码的一些Tips
1. 代码风格
HashMap源码中特别喜欢在判断语句中加赋值语句，形如：if ((xp = x.parent) == null)。它这一行代码做了两件事：
- 把x.parent赋值给xp
- 判断xp是否为null
还喜欢使用连等号，形如：pp = r.parent = p.parent。它这一行代码也做了两件事：
- 把p.parent赋值给r.parent
- 把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
rotateLeft、rotateRight方法中的变量名
p 旋转的关键点pp p的parent节点r p的右子节点节点l p的左子节点节点rl p的右子节点节点的左子节点lr p的左子节点节点的右子节点
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK