TreeSet details

TreeSet Detailed explanation

TreeSet Basic operation

Put it in TreeSet The elements in the collection : Disorder cannot be repeated , But it can be sorted automatically by the size of the elements

 		//  Set creation 
        TreeSet<Integer> ts = new TreeSet<>();
        //  Additive elements 
        ts.add(1);
        ts.add(100);
        ts.add(10);
        ts.add(0);
        ts.add(15);
		// Iterator traversal 
        Iterator<Integer> it = ts.iterator();
        while(it.hasNext()){
    
            Integer next = it.next();
            System.out.println(next);
        }
		// enhance for Loop traversal 
        for (Integer i:
             ts) {
    
            System.out.println(i);
        }

Running results :

0
1
10
15
100

1. TreeSet The bottom layer of the set is actually a TreeMap, and TreeMap At the bottom of the set is a binary tree , Will also be TreeSet Elements in a collection are called sortable combinations

One of the application scenarios : When the user information is displayed on the page, it is in ascending or descending order according to the birthday

	 There is a lot of data in the database :
    userid  name    birth
    -----------------------
    1       zs      1980-11-11
    2       ls      1980-10-11
    3       ww      1981-11-11
    4       zl      2001-12-23
     Write a program to take data from the database , When the user information is displayed on the page, it is in ascending or descending order according to the birthday .
     It can be used at this time TreeSet aggregate , because TreeSet Gather and put in , Take it out in an orderly way 

TreeSet aggregate , Custom types cannot be sorted ！！！

example:

public class TreeSetTest03 {

    public static void main(String[] args) {

        Person p1 = new Person(32);
        Person p2 = new Person(20);
        Person p3 = new Person(25);
        TreeSet<Person> ts = new TreeSet<>();
        ts.add(p1);
        ts.add(p2);
        ts.add(p3);
        for (Person x:
             ts) {
            System.out.println(x);
        }
    }

}
class Person{
    int age;
    public Person(int age){
        this.age = age;
    }
    //  rewrite toString Method 
    @Override
    public String toString() {
        return "Person{" +
                "age=" + age +
                '}';
    }
}

Running results :

Exception in thread "main" java.lang.ClassCastException: com.lxz.review1.Person cannot be cast to java.lang.Comparable
	at java.util.TreeMap.compare(TreeMap.java:1294)
	at java.util.TreeMap.put(TreeMap.java:538)
	at java.util.TreeSet.add(TreeSet.java:255)
	at com.lxz.review1.TreeSetTest03.main(TreeSetTest03.java:23)

The program threw an exception as a result of running :Person cannot be cast to java.lang.Comparable. The program cannot sort because no custom type was specified Person The rules of comparison between objects , It doesn't say who is big or who is small ！

stay TreeSet There are two ways to implement custom type sorting in

1. Mode one : Put it in TreeSet The elements in the collection need Realization java.lang.Comparable Interface

public class TreeSetTest04 {

    public static void main(String[] args) {

        Person1 p1 = new Person1(32);
        Person1 p2 = new Person1(20);
        Person1 p3 = new Person1(25);
        TreeSet<Person1> ts = new TreeSet<>();
        ts.add(p1);
        ts.add(p2);
        ts.add(p3);
        for (Person1 x:
                ts) {
            System.out.println(x);
        }
    }

}

/**
 *  Put it in TreeSet The elements in the collection need to implement java.lang.Comparable Interface 
 *  And realize compareTo Method .equals Don't write 
 */
class Person1 implements  Comparable<Person1>{
    int age;
    public Person1(int age){
        this.age = age;
    }
    //  rewrite toString Method 
    @Override
    public String toString() {
        return "Person1{" +
                "age=" + age +
                '}';
    }
    /**
     *  You need to write comparison logic or comparison rules in this comparison method , Compare by what 
     *  Take the parameters k And every one of the sets key Compare , The return value may be greater than 0  Less than 0  Or equal to 0
     *  The comparison rules are ultimately specified by the programmer ;  For example, in ascending order of age , Or in descending order of age .
     * @param o
     * @return
     */
    @Override
    public int compareTo(Person1 o) { // c1.compareTo(c2)
        return this.age-o.age; // >0 =0 <0  It's possible 
    }
}

2. Mode two : In the constructor TreeSet perhaps TreeMap Give it when you assemble Pass a comparator object

public class TreeSetTest06 {

    public static void main(String[] args) {
        //  Create TreeSet When we gather , You need to use this comparator .
        // TreeSet<WuGui> wuGui = new TreeSet<>(); //  That's not good , Without passing a comparator through the constructor .
        //  Pass a comparator to the constructor 
        TreeSet<WuGui> wuGui = new TreeSet<>(new WuGuiComparator()); //  According to the underlying source code, the parameter of one of the construction methods is the comparator 
        //  You can use anonymous inner classes 
        wuGui.add(new WuGui(100));
        wuGui.add(new WuGui(10));
        wuGui.add(new WuGui(1000));
        for (WuGui wugui:
             wuGui) {
            System.out.println(wugui);
        }
    }
}
class WuGui {
    int age;
    public WuGui(int age) {
        this.age = age;
    }
    @Override
    public String toString() {
        return "WuGui{" +
                "age=" + age +
                '}';
    }
}
//  Write a comparator here alone 
//  Comparator implements java.util.Comparator Interface  (Comparable yes java.lang Under bag .Comparator yes java.util Under bag .)
class WuGuiComparator implements Comparator<WuGui>{
    @Override
    public int compare(WuGui o1, WuGui o2) {
        //  Specify comparison rules 
        //  Sort by age 
        return o1.age-o2.age;
    }
}

note:

1. Comparison rules often change : Comparator The design of the interface complies with OCP principle ( The swappable )
2. The comparison rules are fixed : Comparable

example: First sort by age in ascending order , If the age is the same, then sort by name in ascending order ( Implemented using Comparable Interface method )

public class TreeSetTest05 {
    public static void main(String[] args) {
        TreeSet<Vip> vips = new TreeSet<>();
        vips.add(new Vip("zhangsi",20));
        vips.add(new Vip("zhangsan",20));
        vips.add(new Vip("liuxiangzheng",18));
        for (Vip vip:
             vips) {
            System.out.println(vip);
        }
    }
}
class Vip implements Comparable<Vip>{
    String name;
    int age;

    public Vip(String name,int age){
        this.name = name;
        this.age = age;
    }
    @Override
    public String toString() {
        return "Vip{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public int compareTo(Vip o) {
        if(this.age==o.age){
            //  Age is the same, according to the ascending order of names 
            // note： this.name  Is string ,String Realized compareTo Method , So you can call it directly 
            return this.name.compareTo(o.name);
        }else{
            //  Different ages 
            return this.age-o.age;
        }
    }
}

summary :

1. For custom types , Want to be in TreeSet Sort in , Must be realized Comparable Interface or writing Comparator The comparator , Make their comparison rules ！JDK The data type provided by the user does not need to be implemented by the programmer Comparable Interface or writing Comparator The comparator is implemented because its underlying source code Comparable Interface , With comparison rules , So it can be sorted ！
2. Comparable Interface CompareTo The return value of the method is important :

 return 0 It means the same ,value Will be covered 
 return >0, Will continue to look for... On the right subtree 
 return <0, Will continue to look for... In the left tree 

3. TreeSet Underlying principle :

• TreeSet/TreeMap The bottom layer is Self balanced binary trees (TreeSet The bottom is TreeMap): Follow the principle of small on the left and large on the right , The process of storage is also the process of sorting

• Three ways to traverse a binary tree : (note: The left is always on the left of the right )

  • The former sequence traversal : Root left and right
  • In the sequence traversal : Left root right ( Satisfy Self balanced binary trees Storage method of , When the middle order traversal takes out the data, it is the automatically sorted data )
  • After the sequence traversal : Left and right

• TreeSet/TreeMap The set uses ： In the sequence traversal

• The traversal of binary tree can be regarded as a recursive process , That is to divide a tree into left subtrees 、 root 、 The process of right subtree , Until it can no longer be divided into a subtree