黑马程序员技术交流社区

标题: 在集合中，TreeSet是如何实现有序存放的呢？ [打印本页]

---

作者: 于汝国    时间: 2011-12-21 12:43
标题: 在集合中，TreeSet是如何实现有序存放的呢？


在集合中，HashSet是散列存放的，而TreeSet是有序存放的，那么TreeSet是如何实现有序存放的呢？

---

作者: 海中的游弋草    时间: 2011-12-21 12:53
TreeSet实现了Set接口，该接口有TreeMap示例支持，此类保证排序后的set按照升序排列元素，根据使用的构造不同方法，可能会按照元素的自然排序进行排序，或按照在创建SEt 时所提供的比较器进行排序。
TreeSet是一个有序集合，元素中安升序排序，缺省是按照自然顺序排序，意味着TreeSet中元素要实现Comparable接口；

---

作者: 王冀    时间: 2011-12-21 13:10


TreeSet类内部使用了一个TreeMap对象。其中使用了二叉排序树的结构。

插入新节点的方法如下：

1.     public V put(K key, V value) {
   
2.         Entry<K,V> t = root;
   
3.         if (t == null) {  //如果不存在根节点则创建一个
   
4.             root = new Entry<K,V>(key, value, null);
   
5.             size = 1;
   
6.             modCount++;
   
7.             return null;
   
8.         }
   
9.         int cmp;
   
10.         Entry<K,V> parent;
    
11.         Comparator<? super K> cpr = comparator;
    
12.         if (cpr != null) {   //判断有没有比较器。
    
13.             do {                    //从根开始向下查找插入的位置（直到叶节点）
    
14.                 parent = t;
    
15.                 cmp = cpr.compare(key, t.key);
    
16.                 if (cmp < 0)
    
17.                     t = t.left;
    
18.                 else if (cmp > 0)
    
19.                     t = t.right;
    
20.                 else
    
21.                     return t.setValue(value);
    
22.             } while (t != null);
    
23.         }
    
24.         else {
    
25.             if (key == null)
    
26.                 throw new NullPointerException();
    
27.             Comparable<? super K> k = (Comparable<? super K>) key;
    
28.             do {
    
29.                 parent = t;
    
30.                 cmp = k.compareTo(t.key);
    
31.                 if (cmp < 0)
    
32.                     t = t.left;
    
33.                 else if (cmp > 0)
    
34.                     t = t.right;
    
35.                 else
    
36.                     return t.setValue(value);
    
37.             } while (t != null);
    
38.         }
    
39.         Entry<K,V> e = new Entry<K,V>(key, value, parent);  //插入新节点。
    
40.         if (cmp < 0)
    
41.             parent.left = e;
    
42.         else
    
43.             parent.right = e;
    
44.         fixAfterInsertion(e);
    
45.         size++;
    
46.         modCount++;
    
47.         return null;
    
48.     }
    

复制代码

---

作者: 于汝国    时间: 2011-12-21 16:08
虽然不是很明白，但同样感谢各位！谢谢！

---

作者: 刘基军    时间: 2011-12-21 16:48
TreeSet，默认是自然排序，底层数据结构是二叉树。
毕向东老师的视频对应部分有讲，如何排序及二叉树，建议看一下。

---

作者: 奔→跑    时间: 2011-12-21 22:43
TreeSet，默认是自然排序，底层数据结构是二叉树。

需要实现comparable接口。
和覆盖CompareTo()方法；

---

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

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