TreeMap

前言：

TreeMap和HashMap一样实现的是Map接口，但两者的实现方式天差地别。HashMap的底层是hash表+单向链表的形式存储数据，TreeMap底层是通过红黑树存储数据。HashMap因为是基于散列表的实现，所以时间开销为O(1)，TreeMap的时间开销是O(lgn)。TreeMap的优势在于他是基于key值排序的。

红黑树有五大特性：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

他的所有操作都是围绕着这五大特性展开的。这五大特性的最终目的就是为了维持二叉树的相对平衡性。当每次二叉树操作以后，有可能会出现违反特性的情况（也就是出现了失衡状况），这时二叉树需要通过左旋，右旋，重新着色等系列操作，再次找到平衡点。

我的理解是：红黑色的操作就两个要点。第一：遵循二叉查找树的规范，对所有元素进行排序，但这里存在着不确定情况，有可能出现左右子树深度极其不对称的情况，导致最坏时间复杂度出现O(n)的情况。 第二：正因为存在二叉树严重不平衡的情况，所以就出现了红黑二叉树，通过标记每个节点的颜色，动态的调整二叉树的结构，使其始终维持在相对平衡的状态，这样做的好处就是查找性能始终维持在O(lgn)的较高水平。

一、添加元素

在TreeMap中插入元素，原理就是在二叉查找树中插入元素。通过对二叉树节点大小的对比插入相应的位置，时间复杂度为O(lgn)。但是在插入完毕以后，有可能会导致红黑树被破坏的情况，因此需要修复当前结构，重新着色。

put方法： 

  1. public V put(K key, V value) {
  2.     Entry<K,V> t = root;
  3.     if (t == null) {
  4.         compare(key, key); // type (and possibly null) check
  6.         root = new Entry<>(key, value, null);
  7.         size = 1;
  8.         modCount++;
  9.         return null;
  10.     }
  11.     int cmp;
  12.     Entry<K,V> parent;
  13.     // split comparator and comparable paths
  14.     Comparator<? super K> cpr = comparator;
  15.     if (cpr != null) {
  16.         do {
  17.             parent = t;
  18.             cmp = cpr.compare(key, t.key);
  19.             if (cmp < 0)
  20.                 t = t.left;
  21.             else if (cmp > 0)
  22.                 t = t.right;
  23.             else
  24.                 return t.setValue(value);
  25.         } while (t != null);
  26.     }
  27.     else {
  28.         if (key == null)
  29.             throw new NullPointerException();
  30.         @SuppressWarnings("unchecked")
  31.             Comparable<? super K> k = (Comparable<? super K>) key;
  32.         do {
  33.             parent = t;
  34.             cmp = k.compareTo(t.key);
  35.             if (cmp < 0)
  36.                 t = t.left;
  37.             else if (cmp > 0)
  38.                 t = t.right;
  39.             else
  40.                 return t.setValue(value);
  41.         } while (t != null);
  42.     }
  43.     Entry<K,V> e = new Entry<>(key, value, parent);
  44.     if (cmp < 0)
  45.         parent.left = e;
  46.     else
  47.         parent.right = e;
  48.     fixAfterInsertion(e);
  49.     size++;
  50.     modCount++;
  51.     return null;
  52. }

插入元素后调整红黑树结构： 

  1. private void fixAfterInsertion(Entry<K,V> x) {
  2.     x.color = RED;
  4.     while (x != null && x != root && x.parent.color == RED) {
  5.         if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
  6.             Entry<K,V> y = rightOf(parentOf(parentOf(x)));
  7.             if (colorOf(y) == RED) {
  8.                 setColor(parentOf(x), BLACK);
  9.                 setColor(y, BLACK);
  10.                 setColor(parentOf(parentOf(x)), RED);
  11.                 x = parentOf(parentOf(x));
  12.             } else {
  13.                 if (x == rightOf(parentOf(x))) {
  14.                     x = parentOf(x);
  15.                     rotateLeft(x);
  16.                 }
  17.                 setColor(parentOf(x), BLACK);
  18.                 setColor(parentOf(parentOf(x)), RED);
  19.                 rotateRight(parentOf(parentOf(x)));
  20.             }
  21.         } else {
  22.             Entry<K,V> y = leftOf(parentOf(parentOf(x)));
  23.             if (colorOf(y) == RED) {
  24.                 setColor(parentOf(x), BLACK);
  25.                 setColor(y, BLACK);
  26.                 setColor(parentOf(parentOf(x)), RED);
  27.                 x = parentOf(parentOf(x));
  28.             } else {
  29.                 if (x == leftOf(parentOf(x))) {
  30.                     x = parentOf(x);
  31.                     rotateRight(x);
  32.                 }
  33.                 setColor(parentOf(x), BLACK);
  34.                 setColor(parentOf(parentOf(x)), RED);
  35.                 rotateLeft(parentOf(parentOf(x)));
  36.             }
  37.         }
  38.     }
  39.     root.color = BLACK;
  40. }