`

集合框架 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

------------------------------------
分享到:
评论

相关推荐

    java集合框架全面进阶.pdf

    7. **Java集合框架中的重要类和方法**:包括但不限于Collection、Set、List、Map、Iterator、EnumSet、EnumMap、SortedSet、NavigableSet、SortedMap、NavigableMap以及它们的实现类。 在Java集合框架的发展史上,...

    Java 集合框架介绍.ppt

    常见的实现有`HashMap`(哈希表实现)、`Hashtable`(线程安全的哈希表实现)和`TreeMap`(红黑树实现,保证排序)。 3. **迭代器接口**: - `Iterator`:用于遍历集合中的元素,提供了`next()`和`remove()`等方法...

    集合框架.zip

    - **Map接口**:存储键值对的数据结构,HashMap(哈希表,无序)和TreeMap(红黑树,有序)是最常用的实现。 2. **泛型** 集合框架引入了泛型,允许在创建集合时指定元素类型,从而在编译时检查类型安全,避免了...

    全面接触java集合框架(word版)

    后者基于红黑树,保持元素排序。 - `HashMap` 和 `TreeMap`: 分别实现了 `Map` 接口,前者快速查找,后者保持键的排序。 - `Stack` 和 `Deque`: `Stack` 是 `Vector` 的子类,实现后进先出(LIFO)结构,而 `Deque...

    Java 集合框架

    - **TreeMap**:基于红黑树的Map实现,键按自然顺序或自定义比较器排序。 - **LinkedHashMap**:保持插入顺序或访问顺序的Map实现,适合需要保持元素顺序的情况。 3. **工具类:** - **Collections**:提供了一...

    学习Java集合框架全面介绍.pdf

    - `TreeMap`:基于红黑树实现,提供了排序的键值对,元素按照键的自然顺序或自定义比较器排序。 - `Hashtable`:线程安全的`Map`实现,类似于早期版本的`HashMap`,但不接受`null`键和值。 - `LinkedHashMap`:保留...

    Java中常用Map测试示例

    `Map`接口还有其他实现,如`TreeMap`,它基于红黑树,提供有序的键值对,`LinkedHashMap`保持插入顺序或访问顺序,`ConcurrentHashMap`则适用于多线程环境下的并发操作。 在实际应用中,选择哪种`Map`实现取决于...

    java知识点总结

    - 使用红黑树实现的排序集合,不允许重复元素。 - 保持元素的自然顺序或根据提供的比较器进行排序。 - 添加、删除和查找操作的时间复杂度为O(log n)。 5. **EnumSet** - 专门用于枚举类型的集合,效率极高。 -...

    高级编程-java实验报告.docx

    - **TreeMap**: 基于红黑树,保证了键的有序性,插入、删除和查找的时间复杂度为O(log n)。 5. **枚举类型(Enum)**: - Java枚举是一种特殊的数据类型,用于定义一组有限的常量。它们可以包含方法和字段,与其他...

    java-collection-all-in-one.pdf

    TreeMap基于红黑树实现,可以根据键的自然顺序或构造时提供的Comparator进行排序。HashMap和TreeMap都允许null键和多个null值,但性能不同。HashMap提供了更快速的插入和检索,而TreeMap则在保持元素有序时有优势。 ...

    j2se集合课件是java的基础课程章节之一

    而TreeMap则基于红黑树,提供有序的键值对,支持根据键的自然排序或自定义比较器进行排序。 Java集合框架还包含了Queue(队列)、Deque(双端队列)、Stack(栈)等接口和实现,例如LinkedList可以作为双端队列使用...

    JCFInternals.zip

    - `TreeMap`:基于红黑树实现,键值对有序,支持排序和区间操作。 3. **泛型与类型安全**: Java集合框架广泛使用泛型来确保类型安全,避免了强制类型转换,并提高了代码可读性。 4. **迭代器与泛型迭代器**: ...

    Java面试题

    - 使用哈希表实现,包含数组+链表(或红黑树)。 - 默认初始容量为16,扩容时容量翻倍。 - 遍历方式:通常使用`Iterator`。 #### 四、HashTable与HashMap的区别 - **线程安全性**:`HashTable`是线程安全的,而`...

    集合类实惠有好用的,资源

    3. **TreeSet与TreeMap**:TreeSet和TreeMap都基于红黑树数据结构,它们维护了元素的排序顺序。TreeSet按照自然排序或自定义比较器进行排序,而TreeMap则根据键的自然排序或提供的比较器对键进行排序。 4. **Queue...

    Java:Java集合

    - `TreeSet` 和 `TreeMap`:基于红黑树的`Set`和`Map`,保证排序性,适合需要有序集合的情况。 3. **泛型**:Java集合框架广泛使用泛型,使得集合可以持有特定类型的对象,增强了类型安全性和代码可读性。 4. **...

    高级java工程师面试考纲,java高级工程师进阶知识地图

    深入学习`ArrayList`(基于数组的列表实现)、`LinkedList`(双向链表实现...集合)、`LinkedHashSet`(保持插入顺序的`HashSet`)、`TreeSet`(可排序的`Set`实现)、`HashMap`(散列表实现)、`LinkedHashMap`(保持...

    Java-Collections-Homework:Java基础课程的家庭作业

    `TreeMap`实现了`SortedMap`接口,内部是红黑树,保证了键的排序。 5. **迭代器(Iterator)**:用于遍历集合中的元素,`Iterator`接口提供了`hasNext()`和`next()`方法,分别检查和获取下一个元素。 6. **泛型...

    java.util包总结

    TreeSet则基于红黑树,保证元素排序。 3. Queue接口:Queue接口表示一种FIFO(先进先出)的集合,提供了enqueue和dequeue操作。LinkedList也实现了Queue接口,此外,PriorityQueue提供了一种根据元素优先级排序的...

Global site tag (gtag.js) - Google Analytics