TOP

TreeMap原理实现及常用方法
2019-08-14 00:08:24 】 浏览:41
Tags:TreeMap 原理 实现 常用 方法

前面我们分别讲了Map接口的两个实现类HashMapLinkedHashMap,本章我们讲一下Map接口另一个重要的实现类TreeMap,TreeMap或许不如HashMap那么常用,但存在即合理,它也有自己的应用场景,TreeMap可以实现元素的自动排序。


因为TreeMap的存储结构是红黑树,我们回顾一下红黑树的特点以及基本操作,红黑树的原理可参考关于红黑树(R-B tree)原理,看这篇如何。下图为典型的红黑树:



红黑树规则特点:


红黑树自平衡基本操作:


我们先看一下TreeMap中主要的成员变量


上面的主要成员变量根节点root是Entry类的实体,我们来看一下Entry类的源码


大体的实现结构图如下:



TreeMap构造函数:


put方法为Map的核心方法,TreeMap的put方法大概流程如下:



我们来分析一下源码


put方法源码中通过fixAfterInsertion(e)方法来进行自平衡处理,我们回顾一下插入时自平衡调整的逻辑,下表中看不懂的名词可以参考关于红黑树(R-B tree)原理,看这篇如何


接下来我们看一看这个方法


源码中通过 rotateLeft 进行【左旋】,通过 rotateRight 进行【右旋】。都非常类似,我们就看一下【左旋】的代码,【左旋】规则如下:“逆时针旋转两个节点,让一个节点被其右子节点取代,而该节点成为右子节点的左子节点”。


就算是看了上面的注释还是并不清晰,看下图你就懂了



get方法是通过二分查找的思想,我们看一下源码


remove方法可以分为两个步骤,先是找到这个节点,直接调用了上面介绍的getEntry(Object key),这个步骤我们就不说了,直接说第二个步骤,找到后的删除操作。


通过deleteEntry(p)进行删除操作,删除操作的原理我们在前面已经讲过


操作的操作其实很简单,场景也不多,我们看一下删除后的自平衡操作方法fixAfterDeletion


当待操作节点为左节点时,上面描述了四种场景,而且场景之间可以相互转换,如deleteEntry后进入了场景1,经过场景1的一些列操作后,红黑树的结构并没有调整完成,而是进入了场景2,场景2执行完成后跳出循环,将待操作节点设置为黑色,完成。我们下面用图来说明一下四种场景帮助理解,当然大家最好自己手动画一下。


场景1:


当x是左黑色节点,兄弟节点sib是红色节点,需要兄弟节点由红转黑,父节点由黑转红,按父节点左旋,左旋后树的结构变化了,这时重新赋值sib,这个时候sib指向了x的兄弟节点。



但经过这一系列操作后,并没有结束,而是可能到了场景2,或者场景3和4


场景2:


节点x、x的兄弟节点sib、sib的左子节点和右子节点都为黑色时,需要将该节点sib由黑变红,同时将x指向当前x的父节点



经过场景2的一系列操作后,循环就结束了,我们跳出循环,将节点x设置为黑色,自平衡调整完成。


场景3:


节点x、x的兄弟节点sib、sib的右子节点都为黑色,sib的左子节点为红色时,需要将sib左子节点设置为黑色,sib节点设置为红色,同时按sib右旋,再将sib指向x的兄弟节点



并没有完,场景3的一系列操作后,会进入到场景4


场景4:


节点x、x的兄弟节点sib都为黑色,而sib的左右子节点都为红色或者右子节点为红色、左子节点为黑色,此时需要将sib节点的颜色设置成和x的父节点p相同的颜色,设置x的父节点颜色为黑色,设置sib右孩子的颜色为黑色,左旋x的父节点p,然后将x赋值为root



四种场景讲完了,删除后的自平衡操作不太好理解,代码层面的已经弄明白了,但??果让我自己去实现的话,还是差了一些,还需要再研究。


遍历比较简单,TreeMap的遍历可以使用map.values(), map.keySet(),map.entrySet(),map.forEach(),这里不再多说。


本文详细介绍了TreeMap的基本特点,并对其底层数据结构红黑树进行了回顾,同时讲述了其自动排序的原理,并从源码的角度结合红黑树图形对put方法、get方法、remove方法进行了讲解,最后简单提了一下遍历操作,若有不对之处,请批评指正,望共同进步,谢谢!



TreeMap原理实现及常用方法 https://www.cppentry.com/bencandy.php?fid=54&id=228516

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇LinkedHashMap如何保证顺序性 下一篇HashMap原理(二) 扩容机制及存取..