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(红黑树)，它包含几个重要的成员变量： root, size, comparator。
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底层实现原理