数据结构学习笔记 - 07 集合

介绍

对于集合来说，主要涉及增、查、删的操作，不涉及改的操作。

集合的应用，比如词汇量统计，客户统计等。

集合分为有序集合与无序集合；二分搜索树实现的集合，包括 Java 中的 TreeSet 使用红黑树实现，都是有序集合，因为这个集合中的元素是有序排列的。

但是很多时候可能使用集合不会使用到集合的有序性，那么性能更好的无序集合就更适合。这里使用链表实现的集合虽然也是无序的，但是性能不好，但是如果使用哈希表实现，性能就很好了。

实现

定义集合的接口：

public interface Set<E> {

    /**
     * 添加元素 e
     */
    void add(E e);

    /**
     * 删除元素 e
     */
    void remove(E e);

    /**
     * 查看集合是否包含元素 e
     */
    boolean contains(E e);

    /**
     * 查看集合中元素的数量
     */
    int getSize();

    /**
     * 查看当前集合是否为空。
     */
    boolean isEmpty();
}

使用二分搜索树实现的集合：

public class BSTSet<E extends Comparable<E>> implements Set<E> {
    private BST<E> bst;

    public BSTSet() {
        bst = new BST<>();
    }

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

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

    @Override
    public void add(E e) {
        bst.add(e);
    }

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

    @Override
    public void remove(E e) {
        bst.remove(e);
    }
}

使用链表实现的集合：

public class LinkedListSet<E> implements Set<E> {

    private LinkedList<E> linkedList;

    public LinkedListSet() {
        linkedList = new LinkedList<>();
    }

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

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

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

    @Override
    public void add(E e) {
        if (!linkedList.contains(e)) {
            linkedList.addFirst(e);
        }
    }

    @Override
    public void remove(E e) {
        linkedList.removeElements(e);
    }
}

分析

	链表集合	二分搜索树集合（平均）	二分搜索树集合（最差）
增 add	O(n)	O(logn)	O(n)
查 contains	O(n)	O(logn)	O(n)
删 remove	O(n)	O(logn)	O(n)

对于链表集合来说，本身在链表头增加一个元素或者删除一个元素，都是 O(1) 级别的。但是为了查重，都需要遍历查询一边，链表的查询是 O(n) 级别的，所以最终增删也是 O(n) 级别的。

对于二分搜索树集合，它的增查删其实只是寻找了树的层树，我们用 h 表示。最好的情况，也就是树是满的情况下层数和元素数的关系是 2^h - 1 = n，h = log(n + 1) (log底是 2)。那么最好情况的复杂度就是 O(logn) 级别的，这其实很接近 O(1) 级别，在数据量大的时候要比 O(n) 好得多。但是对于二分搜索树来说，如果添加元素的时候恰好是从小到大或者相反地插入元素，这棵树就退化成链表了。要解决这个问题，就要使用平衡二叉树。

二分搜索树集合属于有序集合，有序集合都是基于搜索树实现的。如果我们需要使用集合的有序性这一特点，就要考虑使用搜索树来实现。比如有序集合更适合得到集合中的最大元素，最小元素等。

链表集合属于无序集合。无序集合也可以使用哈希表来实现，哈希表实现的集合性能比搜索树实现的更好。