黑马程序员技术交流社区

标题: 关于集合TreeSet中实现排序的问题 [打印本页]

作者: 何明辉 时间: 2012-7-28 20:47
标题: 关于集合TreeSet中实现排序的问题
本帖最后由何明辉于 2012-7-29 15:17 编辑

集合TreeSet在内存中是以二叉树来进行存放的，这也就决定了要存放的元素必须有比较的行为。但是我不明白TreeSet是如何调用去实现接口Comparable中compareTo的功能？当元素本身具有比较性时，且集合TreeSet也实现了接口Comparator的比较功能，为什么集合TreeSet以集合自身比较为主？求大家能具体的给我讲一讲TreeSet怎么样去调用的，貌似毕老师没讲（当然我知道看TreeSet源代码能够明了），最好有详细的步骤，谢谢

作者: 肖琦 时间: 2012-7-28 21:51

TreeSet的底层是基于TreeMap的，TreeMap的实现时基于红黑树（一种平衡二叉树）。
此树中，任意一个节点的都大于等于它的左子树的最大值、小于等于右子树的最小值。
当你插入一个新值时，红黑树从根节点开始，跟当前节点作比较，如果小于当前节点的值，向左边找，如果大于当前节点的值，向右边找。
这样一直下去，会找到它的位置。然后，为了维护各种红黑性质，它会进行各种的调整，总体来说，它能实现增、删、改、查的时间复杂度都是 O(logn) 。
反正，你要知道，这个过程中要用到比较。

下面是从维基百科上摘抄的一段，让你对红黑树有一个大致的了解，具体内容，由于太复杂了，你还是自己去查阅资料吧。

红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

性质1. 节点是红色或黑色。

性质2. 根是黑色。

性质3. 所有叶子都是黑色（叶子是NIL节点）。

性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

作者: 肖琦 时间: 2012-7-29 13:23

肖琦发表于 2012-7-28 21:51
TreeSet的底层是基于TreeMap的，TreeMap的 ...

不好意思，我有点误解了，我谈谈关于TreeSet我的体会：
TreeSet集合：集合是用来存东西的，TreeSet有一个天生的功能，那就是你每存一个元素进来，他都会拿这个元素来与其他元素比较，然后排序。
但问题是，元素是以一种什么标准排序呢？就不好说了。没有标准他就排不了序，就用不了他。
因此，你存进了的元素应该有个排序的标准，那就得实现Comparable接口，自定义个标准。这样存进来就没问题。
其实还有种解决方式，就是定义TreeSet时你告诉他存元素时按什么标准排序(就是构造时传参)，参数你可以定义一个类(也可以造内部类，更简洁)但必须实现Comparctor接口，实现comparteTo方法比较元素。这种方式在应用中应该用得多点，你想想，很多时候你用的是别人的类，你是没有办法再去改别人写的类的，因此用这种方式就能解决问题。

希望这回讲清楚啦........

作者: 刘海源 时间: 2012-7-29 13:30
TreeSet就要明确是二叉树，可以对元素排序。
就要想到两种排序方式：
自然顺序：Comparable接口，覆盖compareTo(一个参数 )java.lang
比较器：Comparator接口，覆盖compare(两个参数);java.util
判断元素唯一性的依据就是比较方法的返回结果return 0;

作者: 刘海源 时间: 2012-7-29 13:33
补充：
比较器：Comparator接口，覆盖compare(两个参数);java.util
public class ComparatorByLength implements Comparator {

@Override
public int compare(Object o1, Object o2) {

String s1 = (String)o1;
String s2 = (String)o2;

int temp = s1.length() - s2.length();

return temp==0?s1.compareTo(s2):temp;
}

}

自然顺序：Comparable接口，覆盖compareTo(一个参数 )java.lang
public int compareTo(Object o) {

Person p = (Person)o;
int temp = this.age - p.age;
return temp==0?this.name.compareTo(p.name):temp;
}

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

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