作者，李敏，叩丁狼教育高级讲师，原创文章，转载请注明出处。
TreeMap 是基于红黑树的实现，是有序的.当我们在开发中需要用到<font color="red">有序的且按大小排列顺序的、不重复的、有映射关系的业务场景</font>时,TreeMap 这个容器可以帮助我们方便的开发.
TreeMap特性
TreeMap实现了两个重要的接口:
image.png
SortedMap接口,表示其具备可排序的功能.
元素有序.TreeMap 保证元素有序,使用的是比较的方式.在存储数据的时候,需要对存储的key进行比较.所以,它不允许存储null键,但是可以存储null值.
如何进行比较呢?
- 要保存的元素自己具有比较功能,即:自然排序,元素需要实现Comparable接口.
- 使用一个比较器,可以比较两个对象.即:定制排序,需要在创建TreeMap对象的时候,传递一个比较器(Comparator)给构造器.
NavigableMap接口,表示其具备可导航的功能.
导航:在这个接口中,定义了大量的对范围进行查找的方法.比如,大于某一个元素的集合.这些操作都是查询操作.而TreeMap采用的是红黑树的结构,来存储数据,从而保证效率.
那什么是红黑树呢?
红黑树是一种具有红色和黑色链接的平衡查找树.
有点抽象...
既然TreeMap都已经是红黑树的实现了,那我们完全可以看着源码,来说红黑树呀.
显而易见的是:因为TreeMap需要使用红黑树的数据结构来组织元素,所以我们要查看源码,也是查看添加元素或者删除元素.本文主要是简单<font color="red">阅读添加元素的源码(其实删除的原理是一样的)</font>.
TreeMap添加元素
TreeMap包含一个根节点
image.png
这里我们可以先看看根节点的类型,Entry有哪些字段
image.png
所以,在已知一个节点对象的情况下,就可以获取到它的左孩子,右孩子,以及父节点等信息.
下面我们来看看添加元素的代码(删除了一些不影响阅读的代码)
image.png
这里也说明了:<font color="red">左孩子都比其父节点小,右孩子都比父节点大</font>.
这里有个方法不太好理解:fixAfterInsertion, 这个方法具体是做什么的呢?
说这个方法之前,我们需要了解一下,红黑树基于链表结构,除了最基本的添加元素外,还有一个重要的操作:旋转着色.
旋转着色
旋转着色的目的:就是为了保证红黑树的特性.
红黑树的特性:
- 每个节点或者是黑色，或者是红色。
- <font color="red">根节点是黑色</font>。
- 每个叶子节点（NIL）是黑色。
- 如果一个节点是红色的，则它的子节点必须是黑色的。
- <font color="red">从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点</font>。
我们可以想象一种极端的现象,比如,现在我们先后保存key分别为10,20,30,40的这些元素.如果没有一些额外的操作,那么就将是这种情况:
image.png
我们现在接着看fixAfterInsertion方法的源码:
image.png
右旋操作
image.png
左旋操作
image.png
所以,我们在添加完毕元素之后,为了红黑树能够达到平衡状态,需要旋转着色.这一段代码的阅读,其实也就是最核心的,红黑树的原理.
下面,我们就来玩一玩,添加几个元素试试(分析了源码之后,源码咋说,我们就咋做).
存储数据的简单应用
1.添加元素10
image.png
添加节点应该是红色,此时为根节点 ,设置为黑色.
2.添加元素85
image.png
3.添加元素15
image.png
4.添加元素70
image.png
5.添加元素20
image.png
6.添加元素60
image.png
7.添加元素30
image.png
8.添加元素50
image.png
所以,最终效果如下图:
image.png
结论
本文主要是从TreeMap源码上来简单讲解红黑树的实现过程.学习或者工作,多看看源码,也许收获会非常丰富.
WechatIMG9.jpeg
网友评论