算法与数据结构之集合和映射

集合(Set)

集合:承载元素的容器，每个元素只能存在一次
应用:客户统计，词汇量统计
该集合所包含的操作：

public interface Set<E> {
	void add(E e);
	void remove(E e);
	boolean contains(E e);
	int getSize();
	boolean isEmpty();
}

基于二分搜索树的集合实现

参考：算法与数据结构之二分搜索树(BST)
实现：

public class BSTSet<E extends Comparable<E>> implements Set<E> {

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

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

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

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

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

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

基于链表的集合实现

参考：算法与数据结构之带头节点的链表的实现Java版
实现：

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

	private LinkedList<E> list;
	
	public LinkedListSet() {
		list = new LinkedList<>();
	}

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

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

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

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

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

集合的时间复杂度分析

基于链表的集合复杂度分析

LinkdeListSet：
增 add ： O(n)，对于removeFirst来说时间复杂度是O(1)的，但是由于每次添加元素之前需要判断该元素是否在链表中存在，所以为O(n)
查 contains：O(n)
删 remove：O(n)

基于二分搜索树的集合的复杂度分析

BSTSet：
对于二分搜索树来说，以增加一个元素为例，每次都要淘汰一半的元素，先和根节点比较，如果小于根节点，只看左子树，不看右子树，…
从上面来看，添加节点的轨迹实际上是一个链表，这个链表的长度和这颗树的高度有关，不仅是添加节点的过程，查和删的过程与其相同
所以增，删和查的时间复杂度是O(h)，h代表是树的高度，那么节点的个数和树的高度又有什么关系呢？
首先分析一颗满二叉树的节点和高度之间的关系，我们容易发现，假如这颗树的节点是n，则有2^h - 1 = n----> h = log(n + 1)，所以我们可以说二分搜索树实现的集合中的增删改平均时间复杂度是O(logn)，为什么说是平均时间复杂度呢？因为这是在我们的二分搜索是满二叉树的情况下，也是最优的情况，但是如果我们的二分搜索树稍微有点倾斜大概也是O(logn)的复杂度，大部分情况也是O(logn)。
但是它也存在最差的情况，比如说1,2,3,4,5,6这组数据是有序的，如果将其一次构成一颗二分搜索树，会发现这棵树的每一个节点只有右子树，没有左子树，其实他此时就是一个单链表，此时增删改的时间复杂度为O(n)，这是最坏的情况，解决办法就是平衡二叉树。