汇合

应用二分搜寻树实现不可反复的汇合

创立 Set 接口以及实现类。

public interface Set<E> {void add(E e);
        void remove(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 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();
        }
}

应用链表来实现不可反复的汇合

public class LinkedListSet<E> implements Set<E> {
        private LinkedList<E> linkedList;
        public LinkedListSet() {linkedList = new LinkedList<>();
        }
        @Override
        public void add(E e) {
            // 判断是否存在以后元素 e
            if (!linkedList.contains(e)){linkedList.addFirst(e);
            }
        }
        @Override
        public void remove(E e) {linkedList.removeElement(e);
        }
        @Override
        public boolean contains(E e) {return linkedList.contains(e);
        }
        @Override
        public int getSize() {return linkedList.getSize();
        }
        @Override
        public boolean isEmpty() {return linkedList.isEmpty();
        }
}

汇合复杂度剖析