集合
集合的基本功能：
publicinterfaceSetE{voidadd(Ee);voidremove(Ee);booleancontains(Ee);intgetSize();booleanisEmpty();}基于二分搜索树的集合实现
publicclassBSTSetEextendsComparableEimplementsSetE{privateBSTEbst;publicBSTSet(){bst=newBST();}
Overridepublicvoidadd(Ee){bst.add(e);}Overridepublicvoidremove(Ee){bst.del(e);}Overridepublicbooleancontains(Ee){returnbst.contains(e);}OverridepublicintgetSize(){returnbst.size();}OverridepublicbooleanisEmpty(){returnbst.isEmpty();}}基于链表的集合实现publicclassLinkedListSetEimplementsSetE{privateLinkedListElinkedList;publicLinkedListSet(){linkedList=newLinkedList();}
Overridepublicvoidadd(Ee){if(!contains(e)){linkedList.addFirst(e);}}Overridepublicvoidremove(Ee){if(contains(e)){linkedList.removeElement(e);}}Overridepublicbooleancontains(Ee){returnlinkedList.contains(e);}OverridepublicintgetSize(){returnlinkedList.getSize();}OverridepublicbooleanisEmpty(){returnlinkedList.isEmpty();}}时间复杂度分析操作LinkedListSetBSTSetaddO(n)平均情况：O(logn)最差情况：O(n)containsO(n)平均情况：O(logn)最差情况：O(n)removeO(n)平均情况：O(logn)最差情况：O(n)映射映射的基本功能：
publicinterfaceMapK,V{voidadd(Kkey,Vvalue);Vremove(Kkey);booleancontains(Kkey);Vget(Kkey);voidset(Kkey,VnewValue);intgetSize();booleanisEmpty();}基于二分搜索树的映射实现
publicclassBSTMapKextendsComparableK,VimplementsMapK,V{privateclassNode{publicKkey;publicVvalue;publicNodeleft,right;publicNode(Kkey,Vvalue){this.key=key;this.value=value;this.left=null;this.right=null;}}privateNoderoot;privateintsize;//返回以node为根节点的二分搜索树中，key所在的节点privateNodegetNode(Nodenode,Kkey){if(node==null){returnnull;}if(key.