关于TreeSet的排序对于删除操作的影响

时间:2022-06-07 12:37:25

先贴上准备的代码:

  1. TreeSet<Node> list =newTreeSet<>();
    Node n1 =newNode(1);
    Node n2 =newNode(2);
    Node n3 =newNode(3);
    Node n4 =newNode(4);
    Node n5 =newNode(5);

     

这是Node,继承Comparable接口
 
  1. protected static class Node implements Comparable<Node>
    {
    public int id;
    private int __id;
    private static int ID =1;
    public Node(int id){
    this.id = id;
    this.__id = ID++;
    }
    @Override
    public String toString(){
    return"Node("+__id+") "+id;
    }
    @Override
    public int compareTo(Node o){
    if(o.id>id)
    return ;
    else if(o.id == id)
    return 0;
    else
    return -1;
    }
    }

     

 
 
TreeSet是一个二叉树集合,对于TreeMap的一个封装,增加一个元素,其实就是把元素当成Key,固定一个value放入TreeMap。
如果我们要研究TreeSet的排序,那么不得不了解TreeMap的Entry,其实就是一个二叉树结构,对于TreeSet本身来说,功能都是建立在TreeMap的基础上。
TreeMap$Entry拥有除了Key和Value之外,多了三个属性,left,right,parent。left和right作为二叉树的分叉,parent建立树的上下结构。
插入一个元素,都是根据比较器Compare出大小,然后从根节点开始,建立二叉树。所以在插入和删除的时候,有一个重要的地方,就是当你需要修改某一个元素的时候,必须确保这个元素的排序是没有被影响过的。比如我们上面一个列子,1-5个元素插入之后,当需要删除元素1,就必须保证,Node的id为1,如果id被修改成非1的情况下,再通过remove(Object obj)来删除就不能找到节点,因此删除就不可能了。
 
上测试例子:
 
  1. package examples.base;
    
    import java.util.TreeSet;
    
    public class TestTreeSet {
        public static void main(String[] args) {
            TreeSet<Node> list = new TreeSet<>();
            Node n1 = new Node(1);
            Node n2 = new Node(2);
            Node n3 = new Node(3);
            Node n4 = new Node(4);
            Node n5 = new Node(5);
            Node n = new Node(5);
            list.add(n1);
            list.add(n2);
            list.add(n3);
            list.add(n4);
            list.add(n5);
            list.add(n);
            System.out.println(list);
            System.out.println(list.higher(n3));
            n1.id = 5;
            if(list.remove(n1)){
                System.out.println("true");
            }
            
            list.add(n1);
            System.out.println(list);
            
        }
        
        protected static class Node implements Comparable<Node>
        {
            public int id;
            private int __id;
            private static int ID = 1;
            public Node(int id) {
                this.id = id;
                this.__id = ID++;
            }
            
            @Override
            public String toString() {
                return "Node("+__id+") "+id;
            }
            
            @Override
            public int compareTo(Node o) {
                if(o.id>id)
                    return 1;
                else if(o.id == id)
                    return 0;
                else
                    return -1;
                            
            }
        }
    }

     

结果:
  1. [Node(5)5,Node(4)4,Node(3)3,Node(2)2,Node(1)1]
  2. Node(2)2
  3. true
  4. [Node(1)5,Node(4)4,Node(3)3,Node(2)2,Node(1)5]
删除成功其实只是删除了元素5,而元素1虽然id是5,但是它还是老的排序,所以在二叉树中是定位不到的,而因为id为5的元素存在,而且排序没有被影响,因此删除就能够成功。
最后,我们谨记一个要点:
当我们用TreeSet作为一个自动排序队列的时候,更新元素的位置,必须分三个步骤:
1、remove老的元素
2、修改
3、插入修改后的元素