TreeMap了解吗

简介

TreeMap 是一个有序的key-value集合,它是通过红黑树实现的。

TreeMap 继承于AbstractMap,所以它是一个Map,即一个key-value集合。

TreeMap 实现了NavigableMap接口,意味着它支持一系列的导航方法。比如返回有序的key集合。(这里需要学习)

TreeMap 实现了Cloneable接口,意味着它能被克隆。

TreeMap 实现了java.io.Serializable接口,意味着它支持序列化。

 

TreeMap基于红黑树(Red-Black tree)实现。该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法。

TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。

另外,TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。

 

基于红黑二叉树的NavigableMap的实现,线程非安全,不允许null,key不可以重复,value允许重复,存入TreeMap的元素应当实现Comparable接口或者实现Comparator接口,会按照排序后的顺序迭代元素,两个相比较的key不得抛出classCastException。主要用于存入元素的时候对元素进行自动排序,迭代输出的时候就按排序顺序输出

TreeMap数据结构

java.lang.Object

   ↳     java.util.AbstractMap<K, V>

         ↳     java.util.TreeMap<K, V>

 

public class TreeMap<K,V>

    extends AbstractMap<K,V>

    implements NavigableMap<K,V>, Cloneable, java.io.Serializable {}

 

从图中可以看出:
(1) TreeMap实现继承于AbstractMap,并且实现了NavigableMap接口。
(2) TreeMap的本质是R-B Tree(红黑树),它包含几个重要的成员变量: rootsizecomparator
root 是红黑数的根节点。它是Entry类型,Entry是红黑数的节点,它包含了红黑数的6个基本组成成分:key(键)、value(值)、left(左孩子)、right(右孩子)、parent(父节点)、color(颜色)。Entry节点根据key进行排序,Entry节点包含的内容为value。 
红黑数排序时,根据Entry中的key进行排序;Entry中的key比较大小是根据比较器comparator来进行判断的。
size是红黑数中节点的个数。

TreeMap遍历方式

1 遍历TreeMap的键值对

第一步:根据entrySet()获取TreeMap的“键值对”的Set集合。
第二步:通过Iterator迭代器遍历“第一步”得到的集合。

// 假设map是TreeMap对象

// map中的key是String类型,value是Integer类型

Integer integ = null;

Iterator iter = map.entrySet().iterator();

while(iter.hasNext()) {

    Map.Entry entry = (Map.Entry)iter.next();

    // 获取key

    key = (String)entry.getKey();

        // 获取value

    integ = (Integer)entry.getValue();

}

补充知识

Java中Map的entrySet()详解

由于Map中存放的元素均为键值对,故每一个键值对必然存在一个映射关系。
Map中采用Entry内部类来表示一个映射项,映射项包含Key和Value

Map.Entry里面包含getKey()和getValue()方法

Set<Entry<T,V>> entrySet()

该方法返回值就是这个map中各个键值对映射关系的集合。

可使用它对map进行遍历。

Java中Iterator详解

迭代器是一种设计模式,它是一个对象,它可以遍历并选择序列中的对象,而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象,因为创建它的代价小。

Java中的Iterator功能比较简单,并且只能单向移动:

  (1) 使用方法iterator()要求容器返回一个Iterator。第一次调用Iterator的next()方法时,它返回序列的第一个元素。注意:iterator()方法是java.lang.Iterable接口,被Collection继承。

  (2) 使用next()获得序列中的下一个元素。

  (3) 使用hasNext()检查序列中是否还有元素。

  (4) 使用remove()将迭代器新返回的元素删除。

Iterator是Java迭代器最简单的实现,为List设计的ListIterator具有更多的功能,它可以从两个方向遍历List,也可以从List中插入和删除元素。

2 遍历TreeMap的键

第一步:根据keySet()获取TreeMap的“键”的Set集合。
第二步:通过Iterator迭代器遍历“第一步”得到的集合。

// 假设map是TreeMap对象

// map中的key是String类型,value是Integer类型

String key = null;

Integer integ = null;

Iterator iter = map.keySet().iterator();

while (iter.hasNext()) {

        // 获取key

    key = (String)iter.next();

        // 根据key,获取value

    integ = (Integer)map.get(key);

}

3 遍历TreeMap的值

第一步:根据value()获取TreeMap的“值”的集合。
第二步:通过Iterator迭代器遍历“第一步”得到的集合。

// 假设map是TreeMap对象

// map中的key是String类型,value是Integer类型

Integer value = null;

Collection c = map.values();

Iterator iter= c.iterator();

while (iter.hasNext()) {

    value = (Integer)iter.next();

}

 红黑树

红黑树是一种自平衡二叉树,在平衡二叉树的基础上每个节点又增加了一个颜色的属性,节点的颜色只能是红色或黑色。具有以下性质:

(1)节点要么是红色,要么是黑色,

(2)根节点只能是黑色;

(3)红黑树中所有的叶子节点后面再接上左右两个空节点,这样可以保持算法的一致性,而且所有的空节点都是黑色;

(4)红色节点的父节点和左右孩子节点都是黑色,及黑红相间;

(5)在任何一棵子树中,从根节点向下走到空节点的路径上所经过的黑节点的数目相同,红黑树确保没有一条路径会比其他路径长出两倍,因而近乎平衡的。

左旋和右旋

 将右子树的左子树链接到父亲节点的右孩子结点,父亲节点作为ptr结点的左孩子结点便完成了旋转。

当前节点ptr,与父亲节点和当前节点的左孩子结点位于一条直线上时,使用右单旋进行平衡。 

插入

情况1

情况2

情况3

 

 

情况4

 

情况5

 

总结

红黑树的删除还没有研究???

参考链接

https://www.cnblogs.com/fanzhidongyzby/p/3187912.html

红黑树数据结构剖析

https://blog.csdn.net/cyywxy/article/details/81151104

TreeMap底层实现原理