吃透Java集合系列十二：TreeMap

本文主要是介绍吃透Java集合系列十二：TreeMap，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一：TreeMap整体认识

我们知道HashMap，它保证了以O(1)的时间复杂度进行增、删、改、查，从存储角度考虑，这两种数据结构是非常优秀的。但是HashMap还是有自己的局限性----它不具备统计性能，或者说它的统计性能时间复杂度并不是很好才更准确，所有的统计必须遍历所有Entry，因此时间复杂度为O(N)。
比如Map的Key有1、2、3、4、5、6、7，我现在要统计：

1. 所有Key比3大的键值对有哪些
2. Key最小的和Key最大的是哪两个

就类似这些操作，HashMap做得比较差，此时我们可以使用TreeMap。TreeMap的Key按照自然顺序进行排序或者根据创建映射时提供的Comparator接口进行排序。TreeMap为增、删、改、查这些操作提供了log(N)的时间开销，从存储角度而言，这比HashMap的O(1)时间复杂度要差些；但是在统计性能上，TreeMap同样可以保证log(N)的时间开销，这又比HashMap的O(N)时间复杂度好不少。

因此：如果只需要存储功能，使用HashMap是一种更好的选择；如果还需要保证统计性能或者需要对Key按照一定规则进行排序，那么使用TreeMap是一种更好的选择。

TreeMap是由红黑树来实现的，下面看一下红黑树

二：红黑树

红黑树又称红-黑二叉树，它首先是一颗二叉树，它具体二叉树所有的特性。同时红黑树更是一颗自平衡的排序二叉树。
我们知道一颗基本的二叉树他们都需要满足一个基本性质–即树中的任何节点的值大于它的左子节点，且小于它的右子节点。按照这个基本性质使得树的检索效率大大提高。我们知道在生成二叉树的过程是非常容易失衡的，最坏的情况就是一边倒（只有右/左子树），这样势必会导致二叉树的检索效率大大降低（O(n)），所以为了维持二叉树的平衡，大牛们提出了各种实现的算法，如：AVL，SBT，伸展树，TREAP ，红黑树等等。
平衡二叉树必须具备如下特性：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。也就是说该二叉树的任何一个等等子节点，其左右子树的高度都相近。

红黑树顾名思义就是节点是红色或者黑色的平衡二叉树，它通过颜色的约束来维持着二叉树的平衡。对于一棵有效的红黑树二叉树而言我们必须增加如下规则：

1. 每个节点都只能是红色或者黑色
2. 根节点是黑色
3. 每个叶节点（NIL节点，空节点）是黑色的。
4. 如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这棵树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。所以红黑树它是复杂而高效的，其检索效率O(log n)。下图为一颗典型的红黑二叉树。

红黑树不是重点，具体了解红黑树可以参考：
红黑树系列集锦
红黑树数据结构剖析

三：源码分析

类信息

public class TreeMap<K,V>extends AbstractMap<K,V>implements NavigableMap<K,V>, Cloneable, java.io.Serializable

TreeMap继承AbstractMap，实现NavigableMap、Cloneable、Serializable三个接口。其中AbstractMap表明TreeMap为一个Map即支持key-value的集合， NavigableMap则意味着它支持一系列的导航方法，具备针对给定搜索目标返回最接近匹配项的导航方法 。

属性信息

	//比较器，因为TreeMap是有序的，通过comparator接口我们可以对TreeMap的内部排序进行精密的控制//可以通过构造函数自定义比较器，也可以使用默认比较器private final Comparator<? super K> comparator;//treeMap的根节点private transient Entry<K,V> root = null;//容器大小private transient int size = 0;//修改次数private transient int modCount = 0;

节点的Entry内部类信息

static final class Entry<K,V> implements Map.Entry<K,V> {//键K key;//值V value;//左孩子Entry<K,V> left = null;//右孩子Entry<K,V> right = null;//父节点Entry<K,V> parent;//颜色boolean color = BLACK;

put方法

put方法步骤如下：
1.获取根节点，根节点为空，产生一个根节点，将其着色为黑色，退出余下流程
2.获取比较器，如果传入的Comparator接口不为空，使用传入的Comparator接口实现类进行比较；如果传入的Comparator接口为空，将Key强转为Comparable接口进行比较
3.从根节点开始逐一依照规定的排序算法进行比较，取比较值cmp，如果cmp=0，表示插入的Key已存在；如果cmp>0，取当前节点的右子节点；如果cmp<0，取当前节点的左子节点
4.排除插入的Key已存在的情况，第（3）步的比较一直比较到当前节点t的左子节点或右子节点为null，此时t就是我们寻找到的节点，cmp>0则准备往t的右子节点插入新节点，cmp<0则准备往t的左子节点插入新节点
5.new出一个新节点，默认为黑色，根据cmp的值向t的左边或者右边进行插入
6.插入之后进行修复，包括左旋、右旋、重新着色这些操作，让树保持平衡性

public V put(K key, V value) {//用t表示二叉树的当前节点Entry<K,V> t = root;//t为null表示一个空树，即TreeMap中没有任何元素，直接插入if (t == null) {//比较key值，个人觉得这句代码没有任何意义，空树还需要比较、排序？compare(key, key); // type (and possibly null) check//将新的key-value键值对创建为一个Entry节点，并将该节点赋予给rootroot = new Entry<>(key, value, null);//容器的size = 1，表示TreeMap集合中存在一个元素size = 1;//修改次数 + 1modCount++;return null;}int cmp;     //cmp表示key排序的返回结果Entry<K,V> parent;   //父节点// split comparator and comparable pathsComparator<? super K> cpr = comparator;    //指定的排序算法//如果cpr不为空，则采用既定的排序算法进行创建TreeMap集合if (cpr != null) {do {parent = t;      //parent指向上次循环后的t//比较新增节点的key和当前节点key的大小cmp = cpr.compare(key, t.key);//cmp返回值小于0，表示新增节点的key小于当前节点的key，则以当前节点的左子节点作为新的当前节点if (cmp < 0)t = t.left;//cmp返回值大于0，表示新增节点的key大于当前节点的key，则以当前节点的右子节点作为新的当前节点else if (cmp > 0)t = t.right;//cmp返回值等于0，表示两个key值相等，则新值覆盖旧值，并返回新值elsereturn t.setValue(value);} while (t != null);}//如果cpr为空，则采用默认的排序算法进行创建TreeMap集合else {if (key == null)     //key值为空抛出异常throw new NullPointerException();/* 下面处理过程和上面一样 */Comparable<? super K> k = (Comparable<? super K>) key;do {parent = t;cmp = k.compareTo(t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}//将新增节点当做parent的子节点Entry<K,V> e = new Entry<>(key, value, parent);//如果新增节点的key小于parent的key，则当做左子节点if (cmp < 0)parent.left = e;//如果新增节点的key大于parent的key，则当做右子节点elseparent.right = e;/**  上面已经完成了排序二叉树的的构建，将新增节点插入该树中的合适位置*  下面fixAfterInsertion()方法就是对这棵树进行调整、平衡，具体过程参考上面的五种情况*/fixAfterInsertion(e);//TreeMap元素数量 + 1size++;//TreeMap容器修改次数 + 1modCount++;return null;}

第1~第5步都没有什么问题，红黑树最核心的应当是第6步插入数据之后进行的修复工作，对应的Java代码是TreeMap中的fixAfterInsertion方法

	/*** 新增节点后的修复操作* x 表示新增节点*/private void fixAfterInsertion(Entry<K,V> x) {x.color = RED;    //新增节点的颜色为红色//循环 直到 x不是根节点，且x的父节点不为红色while (x != null && x != root && x.parent.color == RED) {//如果X的父节点（P）是其父节点的父节点（G）的左节点if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {//获取X的叔节点(U)Entry<K,V> y = rightOf(parentOf(parentOf(x)));//如果X的叔节点（U） 为红色（情况三）if (colorOf(y) == RED) {     //将X的父节点（P）设置为黑色setColor(parentOf(x), BLACK);//将X的叔节点（U）设置为黑色setColor(y, BLACK);//将X的父节点的父节点（G）设置红色setColor(parentOf(parentOf(x)), RED);x = parentOf(parentOf(x));}//如果X的叔节点（U为黑色）；这里会存在两种情况（情况四、情况五）else {   //如果X节点为其父节点（P）的右子树，则进行左旋转（情况四）if (x == rightOf(parentOf(x))) {//将X的父节点作为Xx = parentOf(x);//右旋转rotateLeft(x);}//（情况五）//将X的父节点（P）设置为黑色setColor(parentOf(x), BLACK);//将X的父节点的父节点（G）设置红色setColor(parentOf(parentOf(x)), RED);//以X的父节点的父节点（G）为中心右旋转rotateRight(parentOf(parentOf(x)));}}//如果X的父节点（P）是其父节点的父节点（G）的右节点else {//获取X的叔节点（U）Entry<K,V> y = leftOf(parentOf(parentOf(x)));//如果X的叔节点（U） 为红色（情况三）if (colorOf(y) == RED) {//将X的父节点（P）设置为黑色setColor(parentOf(x), BLACK);//将X的叔节点（U）设置为黑色setColor(y, BLACK);//将X的父节点的父节点（G）设置红色setColor(parentOf(parentOf(x)), RED);x = parentOf(parentOf(x));}//如果X的叔节点（U为黑色）；这里会存在两种情况（情况四、情况五）else {//如果X节点为其父节点（P）的右子树，则进行左旋转（情况四）if (x == leftOf(parentOf(x))) {//将X的父节点作为Xx = parentOf(x);//右旋转rotateRight(x);}//（情况五）//将X的父节点（P）设置为黑色setColor(parentOf(x), BLACK);//将X的父节点的父节点（G）设置红色setColor(parentOf(parentOf(x)), RED);//以X的父节点的父节点（G）为中心右旋转rotateLeft(parentOf(parentOf(x)));}}}//将根节点G强制设置为黑色root.color = BLACK;}

get方法

get方法相当于put方法就简单多了，从根节点开始循环比较。

• 当key大于当前节点，把当前节点指针指向左孩子继续循环。
• 当key小于当前节点，把当前节点的指针指向右孩子继续循环。
• 当key等于当前节点，则返回当前节点。

public V get(Object key) {// 根据 key 获取到对应的 EntryEntry<K,V> p = getEntry(key);return (p==null ? null : p.value);}
final Entry<K,V> getEntry(Object key) {// 基于比较器的查找if (comparator != null)return getEntryUsingComparator(key);if (key == null)throw new NullPointerException();@SuppressWarnings("unchecked")Comparable<? super K> k = (Comparable<? super K>) key;//从根节点开始查找，当key小于当前节点，左孩子为当前节点继续循环，当key大于当前节点//右孩子为当前节点继续循环，key等于当前节点，则返回当前节点Entry<K,V> p = root;while (p != null) {int cmp = k.compareTo(p.key);if (cmp < 0)p = p.left;else if (cmp > 0)p = p.right;elsereturn p;}return null;}

remove方法
针对于红黑树的增加节点而言，删除显得更加复杂，使原本就复杂的红黑树变得更加复杂。同时删除节点和增加节点一样，同样是找到删除的节点，删除之后调整红黑树。但是这里的删除节点并不是直接删除，而是通过走了“弯路”通过一种捷径来删除的：找到被删除的节点D的子节点C，用C来替代D，不是直接删除D，因为D被C替代了，直接删除C即可。所以这里就将删除父节点D的事情转变为了删除子节点C的事情，这样处理就将复杂的删除事件简单化了。子节点C的规则是：右分支最左边，或者 左分支最右边的。

红-黑二叉树删除节点，最大的麻烦是要保持 各分支黑色节点数目相等。 因为是删除，所以不用担心存在颜色冲突问题——插入才会引起颜色冲突。

红黑树删除节点同样会分成几种情况，这里是按照待删除节点有几个儿子的情况来进行分类：

1. 没有儿子，即为叶结点。直接把父结点的对应儿子指针设为NULL，删除儿子结点就OK了。
2. 只有一个儿子。那么把父结点的相应儿子指针指向儿子的独生子，删除儿子结点也OK了。
3. 有两个儿子。这种情况比较复杂，但还是比较简单。上面提到过用子节点C替代代替待删除节点D，然后删除子节点C即可。

public V remove(Object key) {Entry<K,V> p = getEntry(key);if (p == null)return null;V oldValue = p.value;deleteEntry(p);return oldValue;}
private void deleteEntry(Entry<K,V> p) {modCount++;size--;// If strictly internal, copy successor's element to p and then make p// point to successor.if (p.left != null && p.right != null) {Entry<K,V> s = successor(p);p.key = s.key;p.value = s.value;p = s;} // p has 2 children// Start fixup at replacement node, if it exists.Entry<K,V> replacement = (p.left != null ? p.left : p.right);if (replacement != null) {// Link replacement to parentreplacement.parent = p.parent;if (p.parent == null)root = replacement;else if (p == p.parent.left)p.parent.left  = replacement;elsep.parent.right = replacement;// Null out links so they are OK to use by fixAfterDeletion.p.left = p.right = p.parent = null;// Fix replacementif (p.color == BLACK)fixAfterDeletion(replacement);} else if (p.parent == null) { // return if we are the only node.root = null;} else { //  No children. Use self as phantom replacement and unlink.if (p.color == BLACK)fixAfterDeletion(p);if (p.parent != null) {if (p == p.parent.left)p.parent.left = null;else if (p == p.parent.right)p.parent.right = null;p.parent = null;}}}

删除后的调整

删除元素之后的调整和前面的插入元素调整的过程比起来更复杂。它不是一个简单的在原来过程中取反。我们先从一个最基本的点开始入手。首先一个，我们要进行调整的这个点肯定是因为我们要删除的这个点破坏了红黑树的本质特性。而如果我们删除的这个点是红色的，则它肯定不会破坏里面的属性。因为从前面删除的过程来看，我们这个要删除的点是已经在濒临叶节点的附近了，它要么有一个子节点，要么就是一个叶节点。如果它是红色的，删除了，从上面的节点到叶节点所经历的黑色节点没有变化。所以，这里的一个前置条件就是待删除的节点是黑色的。

在前面的那个前提下，我们要调整红黑树的目的就是要保证，这个原来是黑色的节点被删除后，我们要通过一定的变化，使得他们仍然是合法的红黑树。我们都知道，在一个黑色节点被删除后，从上面的节点到它所在的叶节点路径所经历的黑色节点就少了一个。我们需要做一些调整，使得它少的这个在后面某个地方能够补上。

这篇关于吃透Java集合系列十二：TreeMap的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---