黑马程序员技术交流社区

标题: TreeSet和TreeMap是怎么样实现排序的 [打印本页]

---

作者: 刘忠德    时间: 2012-1-1 15:42
标题: TreeSet和TreeMap是怎么样实现排序的


RT，TreeSet和TreeMap是怎么样实现排序的呢？

---

作者: 李爱霞    时间: 2012-1-1 15:45
TreeSet类内部使用了一个TreeMap对象。其中使用了二叉排序树的结构。

插入新节点的方法如下：
    public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {  //如果不存在根节点则创建一个
            root = new Entry<K,V>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        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);
        }
        Entry<K,V> e = new Entry<K,V>(key, value, parent);  //插入新节点。
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

---

作者: 颜宗茂    时间: 2012-1-1 16:20
注意的是它们不在使用哈希表,存储方式是一个特殊的二叉树,既然是有序的,自然要求元素是可以比较大小的,如果构造函数指定Comparator的话,就使用这个Comparator比较大小,如果没有指定Comparator的话,就使用自然排序(元素要实现Comparable接口).如果这两个都不可用,就会出错的.

---

作者: 詹英鹏    时间: 2012-1-1 17:10
哈希表HashMap，红黑树TreeMap，链表LinkedList，动态数组ArrayList等数据结构的迭代。

既然TreeMap是有序的,自然要求元素是可以比较大小的,如果构造函数指定Comparator的话,就使用这个Comparator比较大小,如果没有指定Comparator的话,就使用自然排序(元素要实现Comparable接口).如果这两个都不可用,就等着出错吧.
有关Java的排序:http://blog.csdn.net/treeroot/archive/2004/10/19/142636.aspx

因为是二叉树,所以一般查找时间复杂度为 o(lg(n)),这个效率当然没有HashMap的效率高.不过TreeMap比HashMap功能强大,如果不需要排序的话当然不会用TreeMap,如果需要排序的话,HashMap无法胜任,当然要用TreeMap了,它可以求子Map.所以这个是适用场合问题,无法比较他们.

另外,我们习惯了,有Map就会跟一个Set,我们都可以猜到TreeSet和通过TreeMap实现的一个SortedSet的实现.不过我觉的TreeSet好像比TreeMap用的场合多一些,求子集是很常用的呀!!

---

作者: 刘忠德    时间: 2012-1-2 10:17
谢谢楼上 的解答，了解了~~

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2