黑马程序员技术交流社区

标题: TreeSet的比较问题 [打印本页]

---

作者: 黄敏文    时间: 2011-9-4 14:59
标题: TreeSet的比较问题
[code=java]
package cn.itcast.utils;

import java.util.Iterator;
import java.util.TreeSet;

/*
* 按照学生的年龄进行排序，如果年龄相同则按姓名的自然顺序进行排序
*/
public class TreeSetTest {
        public static void main(String[] args) {
                TreeSet ts = new TreeSet();
                ts.add(new Student("lisi02", 22));
                ts.add(new Student("lisi007", 20));
                ts.add(new Student("lisi09", 19));
                ts.add(new Student("lisi08", 19));
//                 ts.add(new Student("lisi01", 40));

                for (Iterator it = ts.iterator(); it.hasNext();) {
                        Student s = (Student) it.next();
                        System.out.println(s.getName() + "::" + s.getAge());
                }
        }
}

//让学生实现Comparable接口，从而具备比较性
class Student implements Comparable {
        private String name;
        private int age;

        public Student(String name, int age) {
                this.name = name;
                this.age = age;
        }

        @Override
        public int compareTo(Object o) {
                if (!(o instanceof Student)) {
                        throw new RuntimeException("不是学生对象");
                }

                Student s = (Student) o;

                System.out.println(this.getName() + "...compareto..." + s.getName());

                if (this.getAge() > s.getAge()) {
                        return 1;
                }

                if (this.getAge() == s.getAge()) {
                        return this.getName().compareTo(s.getName());
                }

                return -1;
        }

        public String getName() {
                return name;
        }

        public void setName(String name) {
                this.name = name;
        }

        public int getAge() {
                return age;
        }

        public void setAge(int age) {
                this.age = age;
        }

}
[/code]

打印结果如下：

lisi007...compareto...lisi02
lisi09...compareto...lisi02
lisi09...compareto...lisi007
lisi08...compareto...lisi007
lisi08...compareto...lisi09
lisi08::19
lisi09::19
lisi007::20
lisi02::22

疑问：lisi08为什么没有跟lisi02进行比较，而是直接和lisi007,lisi09比较

---

作者: 李治    时间: 2011-9-4 19:56
标题: 回复 楼主 的帖子
TreeSet里面应该是使用二分插入排序来实现的：
当把lisi09插入之后，情况应该是这样的：
lisi09::19
lisi007::20
lisi02::22
二分插入排序就是首先和中间的比较，也就是lisi007
lisi08的年龄比lisi007小，它就不会和lisi02比较了，
就是去和lisi09比较。
大概就是这样样子。

---

作者: 匿名    时间: 2011-9-4 20:41
标题: 回复 沙发 的帖子
[quote]TreeSet里面应该是使用二分插入排序来实现的：
[/quote]

二分插入是二叉树么

---

作者: 匿名    时间: 2011-9-5 09:42
标题: 回复 藤椅 的帖子
我觉得应该不是。你可以看看源码就知道了。

---

作者: 匿名    时间: 2011-9-10 14:22
不是同一个概念，二叉树是一种数据组成结构，二分插入是一种查找法。
二叉树的某种遍历法似乎倒是跟二分查找法相似。

---

作者: 匿名    时间: 2011-9-10 19:56
我记得是用红黑树实现的。具体如何也不知道，但效率略低于hashset，因为他是有序的

---

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

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