集合框架 Map篇（3）----TreeMap及红黑树、EnumMap

Map
------
1.HashMap
2.LinkedHashMap
3.IdentityHashMap
4.WeakHashMap
5.TreeMap
6.EnumMap
7.ConcurrentHashMap
8.ConcurrentSkipListMap
--------------------------------------

--------EnumMap----------------------------------------

public class EnumMap<K extends Enum<K>,V> extends AbstractMap<K,V> implements Serializable, Cloneable

与枚举类型键一起使用的专用 Map 实现。枚举映射中所有键都必须来自单个枚举类型，该枚举类型在创建映射时显式或隐式地指定。枚举映射在内部表示为数组。此表示形式非常紧凑且高效。

枚举映射根据其键的自然顺序 来维护（该顺序是声明枚举常量的顺序）。在 collection 视图（keySet()、entrySet() 和 values()）所返回的迭代器中反映了这一点。

eg.:

import java.util.EnumMap;

enum WeekEnum {
 Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday
}

public class EnumMapTest {

 private EnumMap<WeekEnum, String> enumMap = new EnumMap<WeekEnum, String>(WeekEnum.class);

 public EnumMapTest() {
  enumMap.put(WeekEnum.Monday, "星期一，一周开始");
  enumMap.put(WeekEnum.Thursday, "星期二，一周第二天");
  enumMap.put(WeekEnum.Wednesday, "星期三，好好工作……");
  enumMap.put(WeekEnum.Thursday, "星期四，……");
  enumMap.put(WeekEnum.Friday, "星期五，……");
  enumMap.put(WeekEnum.Saturday, "星期六，……");
  enumMap.put(WeekEnum.Sunday, "星期天，休息一下……");
 }

 public String getDayDescription(WeekEnum day) {
  return this.enumMap.get(day);
 }

 public static void main(String[] args) {
       String dayDesc=new EnumMapTest().enumMap.get(WeekEnum.Sunday);
       System.err.println(dayDesc);
 }

}

上面是一个简单的例子。由于EnumMap的具有枚举类型的特点，类型固定且枚举值的个数固定，所以EnumMap效率是比较高的，可以结合具体的应用（特别像例子中的那样，元素的个数较少且较固定时考虑使用EnumMap存储数据）

--------TreeMap------------------------------------------

TreeMap是一种支持排序的Map，其实现方式和HashMap有较大区别，是红黑树数据结构的实现。

/**
*TreeMap中节点的存储结构
*/
static final class Entry<K,V> implements Map.Entry<K,V> {
        /**6个变量域：键、值对、左、右兄弟、父节点、颜色属性 */
        K key;        
        V value;
        Entry<K,V> left = null;//
        Entry<K,V> right = null;
        Entry<K,V> parent;
        boolean color = BLACK;
  ......  
}

put(Object key,Object value):

它是一个典型的基于红黑树的实现，因此要求一定要有key比较的方法，要么传入Comparator实现，要么key对像实现Comparator接口。

/**
*通过“键值对”初始化Entry并把该Entry放到红黑树结构中（如果该key对应的Entry存在，其value就替换为新的value）
*/
public V put(K key, V value) {
        //临时变量t指向根节点
        Entry<K,V> t = root;
         //如果t为空，也就是root为空，TreeMap是空链的情况下，根据键值对创建Entry，并将其置为root根节点
        if (t == null) {
            root = new Entry<K,V>(key, value, null);//父节点为null
            size = 1;//size表示节点的个数
            modCount++;//modCount表示链表的变化次数
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        /** 
        *根据"比较器"comparator为null与否，采取定制比较或默认比较（key的Comparable）不同的方式
        *然后，按照"二叉排序树"的方式从根节点开始查找。如果找到了就覆盖旧的value，并返回旧的value。
        */
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                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;
                else
                    return t.setValue(value);
            } while (t != null);
        }
       /**
       *如果上述遍历没有找到对应的key，则把key-value和最后的遍历得到的parent（也就是待插入位置的parent）
       *构造成新的Entry，作为新的插入节点。
       */
        Entry<K,V> e = new Entry<K,V>(key, value, parent);
         //设置parent和该新节点的关系
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);//插入新节点后，可能会改变原有的红黑树结构，要进行修复
        size++;
        modCount++;
        return null;
    }

/** 红黑树插入后修复算法（该算法来源于CLR--算法3作者的姓氏第一个字母） */
 private void fixAfterInsertion(Entry<K,V> x) {
     //默认新插入的节点颜色为红色（这是为了尽量不改变红黑树黑节点的个数，具体可以查看"红黑树"的属性）
        x.color = RED;
        /** 直到 x 节点的父节点不是根，且 x 的父节点不是红色
  (由于当x的父亲节点是黑色节点的时候，直接插入不会影响到红黑树的性质，所有就没有必要进行下面的操作了,
   所以插入时，只考虑其父亲节点为红色的情况，只有这种情况下红黑树才需要修复操作)*/
while (x != null && x != root && x.parent.color == RED) {
  /**
  *新插入节点x的父节点为红色的时候又分为一下几种情况：
  *1 x 的父节点P是其父节点G的左子节点：
  *1.1 x的父亲节点p的兄弟节点为红色.解决办法：父设黑，父的兄设黑，父的父设红并以父的父为新节点往上遍历直到root涂黑。
  *1.2 x的父亲节点p的兄弟节点为黑色.(此时，又分x是其父的左和右孩子两种情况)
  *  1.2.1 x是其父右子。解决办法： x变黑，父的父变红，父左旋转，父的父右旋转。
  *  1.2.2 x是其父左子。解决办法：父变黑，父的父变红，          父的父右旋转，
  *
  *2 x 的父节点P是其父节点G的右子节点（道理同上）
  */
  
            // 1 如果 x 的父节点P是其父节点G的左子节点
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                Entry<K,V> y = rightOf(parentOf(parentOf(x)));
                //1.1 如果x的父亲节点p的兄弟节点为红色
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);//将x的父亲节点设为黑色
                    setColor(y, BLACK);          //将x的父亲节点兄弟节点设为黑色
                    setColor(parentOf(parentOf(x)), RED);//将x的父亲节点的父亲节点设为红色
                    x = parentOf(parentOf(x));           //将x设为其父亲节点的父亲节点，以便继续往上遍历
                } else {//1.2 如果x的父亲节点p的兄弟节点为黑色
                    if (x == rightOf(parentOf(x))) {//1.2.1 下面左转的目的是变成1.2.2的情况
                        x = parentOf(x);//x指向其父
                        rotateLeft(x);  //当前的x指向左旋转
                    }
                    //1.2.2情况的处理
                    setColor(parentOf(x), BLACK); //父设黑
                    setColor(parentOf(parentOf(x)), RED);//父父设红
                    rotateRight(parentOf(parentOf(x)));//父父右旋转
                }
            } else {//2 道理同上，只是出现right的地方换成了left，出现left的地方换成了right
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        //最后将root根节点置黑，以满足“红黑树”黑头黑尾的性质。
        root.color = BLACK;
    } 

---------------

TreeMap的删除操作的实现：

private void deleteEntry(Entry<K,V> p) { 
    modCount++; //修改次数加1
    size--;           //节点个数减1
    // 如果被删除节点的左子树、右子树都不为空
    if (p.left != null && p.right != null)    { 
        // 用 p 节点的中序后继节点代替 p 节点
        Entry<K,V> s = successor (p); 
        p.key = s.key; 
        p.value = s.value; 
        p = s; 
    } 

    /**

    *经过上面的操作（用 p 节点的中序后继节点代替 p 节点），实际要执行的删除操作就

    *变成了针对p的中序后继节点（如果存在的话）的操作：

    *既然要删除的节点是后继节点，那么要删除的节点的左子树一定为空，所以：

    * 1 当（删除的节点）p为黑色时就有两种情况：

    *   1.1 p的左右均为null；

    *   1.2 p的左为空，右子树为一单个红色节点（并且该红色节点的左右为null，如果不为空就不会满足红黑树的性质了）

    * 2 当p为红色时：其左右子树比为null（也只有这样才能满足红黑树的性质）

    */      
    // 如果 p 节点的左节点存在，replacement 代表左节点；否则代表右节点。
    Entry<K,V> replacement = (p.left != null ? p.left : p.right); 
    if (replacement != null)    { //1.2的情况
        replacement.parent = p.parent; 
        // 如果 p 没有父节点，则 replacemment 变成父节点
        if (p.parent == null) 
            root = replacement; 
        // 如果 p 节点是其父节点的左子节点，则把其父左设为replacement
        else if (p == p.parent.left) 
            p.parent.left  = replacement; 
        // 如果 p 节点是其父节点的右子节点，则把其父右设为replacement
        else 
            p.parent.right = replacement; 
        p.left = p.right = p.parent = null; 
        // 由于当p是红色节点时，直接删除后不会影响到红黑树的高度，所以就不用修复，当为黑节点时需修复红黑树
        if (p.color == BLACK) 
            fixAfterDeletion(replacement);       

    }  else if (p.parent == null) {  // 如果 p 节点没有父节点，置为空链
        root = null; 
    }  else   { 1.1或2的情况：即要删除的p节点的左右子树均为null
        if (p.color == BLACK) //如果是p为黑色，就进行修复（红色时不必）
            // 修复红黑树
            fixAfterDeletion(p);                      

       if (p.parent != null)  { //在p父不为空的情况下，对其父的左（或右）节点进行删除后的置空处理
            // 如果 p 是其父节点的左子节点
            if (p == p.parent.left) 
                p.parent.left = null; 
            // 如果 p 是其父节点的右子节点
            else if (p == p.parent.right) 
                p.parent.right = null; 
            p.parent = null; 
        } 
    } 
------

// 删除节点后修复红黑树
private void fixAfterDeletion(Entry<K,V> x) 
{ 

/**

*由于x为红的情况不存在修复的情况，所以

*当x为黑色是修复存在如下情况：

*1 x 是其父节点的左子节点

*   1.1 当删除的节点有一个红孩子时。解决办法：红孩子目前属于删除节点父的一个孩子，把该孩子变成黑色。

*   1.2 当删除的节点左右子为null的情况下：

*        1.2.1 删除节点的兄弟节点为红色。解决办法：父变红，兄变黑，父左旋转。

*        1.2.2 删除节点的兄弟节点为黑色。（又有多种情况）

*                1.2.2.1 兄有两个黑子节点。解决办法：兄变红，子变黑，红父时变黑（黑父时，从黑父往上遍历）

*                1.2.2.2 兄的子节点左黑右红。解决办法：兄变父色，父变黑，兄红子变黑，父左旋转。

*                1.2.2.3 兄的子节点左红右黑。解决办法：兄红子变父色，父变黑，兄右旋转，父左旋转。

*2 x 是其父节点的右子节点（道理同上）

*/
    // 直到 x 不是根节点，且 x 的颜色是黑色
    while (x != root && colorOf(x) == BLACK)   { 
        // 如果 x 是其父节点的左子节点
        if (x == leftOf(parentOf(x)))  { //1 情况
            // 获取 x 节点的兄弟节点
            Entry<K,V> sib = rightOf(parentOf(x)); 
            // 如果 sib 节点是红色
            if (colorOf(sib) == RED) { //1.2.1 情况
                // 将 sib 节点设为黑色
                setColor(sib, BLACK); 
                // 将 x 的父节点设为红色
                setColor(parentOf(x), RED); 
                rotateLeft(parentOf(x)); 
                // 再次将 sib 设为 x 的父节点的右子节点
                sib = rightOf(parentOf(x)); 
            } 
            // 如果 sib 的两个子节点都是黑色
            if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { // 1.2.2.1 情况
                // 将 sib 设为红色
                setColor(sib, RED); 
                // 让 x 等于 x 的父节点，继续遍历
                x = parentOf(x); 
            } else { 
                // 如果 sib 的只有右子节点是黑色
                if (colorOf(rightOf(sib)) == BLACK) { // 1.2.2.3 情况，下面几行操作是先将其转换成1.2.2.2的情况
                    // 将 sib 的左子节点也设为黑色
                    setColor(leftOf(sib), BLACK); 
                    // 将 sib 设为红色
                    setColor(sib, RED); 
                    rotateRight(sib); 
                    sib = rightOf(parentOf(x)); 
                } 

                // 1.2.2.2 情况
                // 设置 sib 的颜色与 x 的父节点的颜色相同
                setColor(sib, colorOf(parentOf(x))); 
                // 将 x 的父节点设为黑色
                setColor(parentOf(x), BLACK); 
                // 将 sib 的右子节点设为黑色
                setColor(rightOf(sib), BLACK); 
                rotateLeft(parentOf(x)); 
                x = root; 
            } 
        } else { // 2情况（道理同上）

            // 获取 x 节点的兄弟节点
            Entry<K,V> sib = leftOf(parentOf(x)); 
            // 如果 sib 的颜色是红色
            if (colorOf(sib) == RED)  { 
                // 将 sib 的颜色设为黑色
                setColor(sib, BLACK); 
                // 将 sib 的父节点设为红色
                setColor(parentOf(x), RED); 
                rotateRight(parentOf(x)); 
                sib = leftOf(parentOf(x)); 
            } 
            // 如果 sib 的两个子节点都是黑色
            if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { 
                // 将 sib 设为红色
                setColor(sib, RED); 
                // 让 x 等于 x 的父节点
                x = parentOf(x); 
            } else { 
                // 如果 sib 只有左子节点是黑色
                if (colorOf(leftOf(sib)) == BLACK)  { 
                    // 将 sib 的右子节点也设为黑色
                    setColor(rightOf(sib), BLACK); 
                    // 将 sib 设为红色
                    setColor(sib, RED); 
                    rotateLeft(sib); 
                    sib = leftOf(parentOf(x)); 
                } 
                // 将 sib 的颜色设为与 x 的父节点颜色相同
                setColor(sib, colorOf(parentOf(x))); 
                // 将 x 的父节点设为黑色
                setColor(parentOf(x), BLACK); 
                // 将 sib 的左子节点设为黑色
                setColor(leftOf(sib), BLACK); 
                rotateRight(parentOf(x)); 
                x = root; 
            } 
        } 
    } 

    //最终设置root为黑色
    setColor(x, BLACK); 
} 

-----------------------------------------------------------------------

---------红黑树（R-B Tree）--------------------

红黑树：一种二叉查找树（Binary Search Tree），但在每个结点上增加一个存储位表示结点的颜色（Red or Black）

通过对任何一条从根到叶子的路径上各个结点着色方式的限制，使得：

--红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

--红黑树能保证在最坏的情况下，基本的动态几何操作的时间均为O(lgn)

*红黑树上每个结点内含有5个域：color、key、left、right、Entry。

*红黑树满足以下条件：（黑头，黑尾，两红不相挨）

----每个结点要么红的，要么黑的

----根结点是黑的

----每个叶子结点，即空结点（NULL）是黑的

----如果结点是红的，那么它的两个儿子都是黑的

----对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点

对于给定的黑色高度为 N 的红黑树，从根到叶子节点的最短路径长度为 N-1，最长路径长度为 2 * (N-1)

红黑树通过上面这种限制来保证它大致是平衡的——因为红黑树的高度不会无限增高，这样保证红黑树在最坏情况下都是高效的，不会出现普通排序二叉树的最坏的情况（插入数据时的有序情况下导致的）。



另外上面TreeMap中蓝色的注释部分，其实表示的就是红黑树在插入和删除元素时的修复情况。



网上有很多关于红黑树的详细解析，这里也就不再做过多的解释了。

关于红黑树的介绍 推荐：
                                        http://blog.csdn.net/v_JULY_v/article/details/6105630

------------------------------------