A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 何明辉 中级黑马   /  2012-7-28 20:47  /  3016 人查看  /  4 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 何明辉 于 2012-7-29 15:17 编辑

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

4 个回复

倒序浏览
TreeSet的底层是基于TreeMap的,TreeMap的实现时基于红黑树(一种平衡二叉树)。
此树中,任意一个节点的都 大于等于它的左子树的最大值、小于等于右子树的最小值。
当你插入一个新值时,红黑树从根节点开始,跟当前节点作比较,如果小于当前节点的值,向左边找,如果大于当前节点的值,向右边找。
这样一直下去,会找到它的位置。然后,为了维护各种红黑性质,它会进行各种的调整,总体来说,它能实现 增、删、改、查 的时间复杂度都是 O(logn)
反正,你要知道,这个过程中要用到比较。
下面是从维基百科上摘抄的一段,让你对红黑树有一个大致的了解,具体内容,由于太复杂了,你还是自己去查阅资料吧。

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

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

性质2. 根是黑色。

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

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

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




点评

非常感谢你能帮我回答问题,但二叉树的原理我也知道。我问的是集合TreeSer如何调用接口Comparable去实现compareTo的比较功能,还有当集合中实现了比较器Comparator的功能时无论元素本身是否覆用接口CompareTo的比较   发表于 2012-7-29 13:04

评分

参与人数 1技术分 +1 收起 理由
蒋映辉 + 1

查看全部评分

回复 使用道具 举报
肖琦 发表于 2012-7-28 21:51
TreeSet的底层是基于TreeMap的,TreeMap的 ...

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

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

回复 使用道具 举报
                                                                   TreeSet就要明确是二叉树,可以对元素排序。
                                就要想到两种排序方式:
                                自然顺序:Comparable接口,覆盖compareTo(一个参数 )java.lang
                                比较器:Comparator接口,覆盖compare(两个参数);java.util
                                判断元素唯一性的依据就是比较方法的返回结果return 0;
回复 使用道具 举报
补充:
比较器: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;
        }
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马