【数据结构】基于二分搜索树和链表的集合（Set）实现

集合（Set）：是一种高层数据结构，需要用底层数据结构来实现，集合中每个元素只能存在一个，常用于去重。

典型应用：客户统计，词汇量统计。

---

（一）接口Set<E>

public interface Set<E> {

    public void addFirst(E e);
    public void remove(E e);
    public boolean isEmpty();
    public boolean contains(E e);
    public int getSize();
}

 

---

（二）基于二分搜索树集合实现

 

 

 

---

（三）基于链表的集合实现

这里采用自己前几节复实现的链表，而不是用标准库库自带的链表。

public class LinkedListSet<E> implements Set<E>{
    private LinkedList<E> list;

    //构造函数
    public  LinkedListSet(){
        list=new LinkedList<>();
    }
    @Override
    public void addFirst(E e) {//重组逻辑，不能添加重复元素
        if(contains(e)){
            System.out.println("添加失败，元素已存在！");
        }else{
            list.add(e);
        }

    }

    @Override
    public void remove(E e) {
        if (contains(e)){
            list.remove(e);
        }else{
            System.out.println("删除失败，元素不存在！");
        }
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public boolean contains(E e) {
        return list.contains(e);
    }

    @Override
    public int getSize() {
        return list.size();
    }
}

---

（五）两种实现方式的复杂度分析

（1）LinkedListSet

增 add    O(n)
查 contains  O(n)
删 remove    O(n)

（2）BSTSet

增 add    O(h)
查 contains  O(h)
删 remove    O(h)
h:二分搜索树的高度
h与n的关系分析：（1）最优情况：满二叉树，h=log2(n+1),故O（h）=O（logn）
                             （2）最坏情况：当二分搜索树是链表时，h=n，O（h）=O（n）