TreeSet

TreeSet简介

红-黑树的数据结构，默认对元素进行自然排序

TreeSet 是一个有序的集合，它的作用是提供有序的Set集合。它继承于AbstractSet抽象类，实现了NavigableSet<E>, Cloneable, java.io.Serializable接口。

TreeSet 继承于AbstractSet，所以它是一个Set集合，具有Set的属性和方法。

TreeSet 实现了NavigableSet接口，意味着它支持一系列的导航方法。比如查找与指定目标最匹配项。

TreeSet 实现了Cloneable接口，意味着它能被克隆。

TreeSet 实现了java.io.Serializable接口，意味着它支持序列化。

TreeSet是基于TreeMap实现的。TreeSet中的元素支持2种排序方式：自然排序 或者 根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。

TreeSet为基本操作（add、remove 和 contains）提供受保证的 log(n) 时间开销。 另外，TreeSet是非同步的。 它的iterator 方法返回的迭代器是fail-fast的。

特点：

• 元素有序，这里的顺序不是指存储和取出的顺序，而是按照一定的规则进行排序，具体排序方式取决于构造方法

  TreeSet():根据其元素的自然非序进行排序

  TreeSet(Comparator comparator):根据指定的比较器进行排序

• 没有带索引的方法，所以不能使用普通for循环遍历

• 由于是Set集合，所以不包含重复元素的集合

TreeSet自然顺序

即类要实现Comparable接口，并重写compareTo()方法，TreeSet对象调用add()方法时，会将存入的对象提升为Comparable类型，然后调用对象中的compareTo()方法进行比较，根据比较的返回值进行存储。

因为TreeSet底层是二叉树，当compareTo方法返回0时，不存储；当compareTo方法返回正数时，存入二叉树的右子树；当compareTo方法返回负数时，存入二叉树的左子树。如果一个类没有实现Comparable接口就将该类对象存入TreeSet集合，会发生类型转换异常。

TreeSet自定义排序

方式一：元素自身具备比较性

元素自身具备比较性，需要元素实现Comparable接口，重写compareTo方法，也就是让元素自身具备比较性，这种方式叫做元素的自然排序也叫做默认排序。

让元素自身具备比较性

也就是元素需要实现Comparable接口，覆盖compareTo 方法。

案例：创建Student类，有姓名，年龄。存入集合后，先根据年龄大小，再根据姓名来进行排序插入集合中

public class Student implements Comparable<Student> {
    public String name;
    public int age;

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

    @Override
    public int compareTo(Student o) {
        int i = this.age-o.age;
        int n = i==0?this.name.compareTo(o.name):i;
        return n;
    }
}

重写compareTo()方法，返回值有三种情况

1. 返回值为0：不插入集合
2. 返回值为1：往后插入集合
3. 返回值为-1：往前插入集合

public class Demo {
    public static void main(String[] args) {
        Student s1 = new Student("xishi",25);
        Student s2 = new Student("yangyuhuan",29);
        Student s3 = new Student("diaochan",28);
        Student s4 = new Student("wangzhaojun",30);
        Student s5 = new Student("libai",30);
        Student s6 = new Student("libai",30);

        TreeSet<Student> ts = new TreeSet<>();

        ts.add(s1);
        ts.add(s2);
        ts.add(s3);
        ts.add(s4);
        ts.add(s5);
        ts.add(s6);

        for(Student s : ts){
            System.out.println(s.name+"---"+s.age);
        }

    }
}

让容器自身具备比较性，自定义比较器。

需求：当元素自身不具备比较性，或者元素自身具备的比较性不是所需的。

那么这时只能让容器自身具备。

定义一个类实现Comparator 接口，覆盖compare方法。

并将该接口的子类对象作为参数传递给TreeSet集合的构造函数。

当Comparable比较方式，及Comparator比较方式同时存在，以Comparator比较方式为主。

public class Demo5 {
	public static void main(String[] args) {
		TreeSet ts = new TreeSet(new MyComparator());
		ts.add(new Book("think in java", 100));
		ts.add(new Book("java 核心技术", 75));
		ts.add(new Book("现代操作系统", 50));
		ts.add(new Book("java就业教程", 35));
		ts.add(new Book("think in java", 100));
		ts.add(new Book("ccc in java", 100));
 
		System.out.println(ts); 
	}
}
 
class MyComparator implements Comparator {
 
	public int compare(Object o1, Object o2) {
		Book b1 = (Book) o1;
		Book b2 = (Book) o2;
		System.out.println(b1+" comparator "+b2);
		if (b1.getPrice() > b2.getPrice()) {
			return 1;
		}
		if (b1.getPrice() < b2.getPrice()) {
			return -1;
		}
		return b1.getName().compareTo(b2.getName());
	}
 
}
 
class Book {
	private String name;
	private double price;
 
	public Book() {
 
	}
 
	public String getName() {
		return name;
	}
 
	public void setName(String name) {
		this.name = name;
	}
 
	public double getPrice() {
		return price;
	}
 
	public void setPrice(double price) {
		this.price = price;
	}
 
	public Book(String name, double price) {
 
		this.name = name;
		this.price = price;
	}
 
	@Override
	public String toString() {
		return "Book [name=" + name + ", price=" + price + "]";
	}
 
}