一文看懂 HashMap 中的红黑树实现原理( 二 )

2025-12-28 HashMap

一文看懂 HashMap 中的红黑树实现原理

文章插图

同样的，右旋方法 rotateRight 如下：
/* * 右旋逻辑 */static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) {//root:表示根节点//p:表示要调整的节点//l:表示p的左节点//pp:表示p的parent节点//lr:表示p的左孩子的右孩子节点 TreeNode<K,V> l, pp, lr;//l判断，如果l为空则旋转没有意义 if (p != null && (l = p.left) != null) {//多个等号的连接操作从右往左看，设置lr的父亲为p if ((lr = p.left = l.right) != null) lr.parent = p;//判断p的父亲，为空，为根节点，根节点的话就设置为黑色 if ((pp = l.parent = p.parent) == null) (root = l).red = false;//判断p节点是右儿子还是左儿子 else if (pp.right == p) pp.right = l; else pp.left = l; l.right = p; p.parent = l; } return root;}03、操作示例介绍
3.1、插入调整过程图解

一文看懂 HashMap 中的红黑树实现原理

文章插图

3.2、删除调整过程图解

一文看懂 HashMap 中的红黑树实现原理

文章插图

3.3、查询过程图解

一文看懂 HashMap 中的红黑树实现原理

文章插图

04、总结
至此，红黑树的实现就基本完成了，关于红黑树的结构，有很多种情况，情况也比较复杂，但是整体调整流程，基本都是先调整结构然后调整颜色，直到最后满足红黑树特性要求为止。

推荐阅读

上一篇：HotStuff算法详解

下一篇：没有了