ADTforMap:Mapstoreselements(entries)sothattheycanbelocatedquicklyusingkeys·Eachelement(entry)isakey-valuepair(k,v),wherekisthekey andvcan be any object to store additionalinformation.Eachkey is unigue.(different entries have differentkeys.)Mapsupportthefollowingmethods:Size(:ReturnthenumberofentriesinMisEmptyO:TestwhetherMisemptyget(k);IfM contains anentryewithkey=k,then returne elsereturnnull.put(k, v): If M does not contain an entry with key=k then add (kv)tothemapandreturnnull;elsereplacetheentrywith(k,v)andreturntheoldvalueBinarySearchTrees
Binary Search Trees 1 ADT for Map: Map stores elements (entries) so that they can be located quickly using keys. •Each element (entry) is a key-value pair (k, v), where k is the key and v can be any object to store additional information. •Each key is unique. (different entries have different keys.) Map support the following methods: Size(): Return the number of entries in M isEmpty(): Test whether M is empty get(k); If M contains an entry e with key=k, then return e else return null. put(k, v): If M does not contain an entry with key=k then add (k, v) to the map and return null; else replace the entry with (k, v) and return the old value
MethodsofMap(continued)remove(k):removefromMthenetrywithkey=kandreturnitsvalue;if Mhasnosuchentrywithkey=kthenreturnnull.keysO;Returnaniterablecollection containingallkeys storedin Mvalues():Returnan iterablecollection containingall valuesinMentriesO:returnaniterablecollection containing all key-valueentriesinM.Remakrs:hashtableisanimplementationofMap2BinarySearchTrees
Binary Search Trees 2 Methods of Map (continued) remove(k): remove from M the netry with key=k and return its value; if M has no such entry with key=k then return null. keys(); Return an iterable collection containing all keys stored in M values(): Return an iterable collection containing all values in M entries(): return an iterable collection containing all key-value entries in M. Remakrs: hash table is an implementation of Map
ADT forDictionary:ADictionarystoreselements(entries)Eachelement (entry)isakey-valuepair(k,v),wherekisthekey and v can be any objectto store additionalinformation..The keyisNOT uniqueDictionary supportthefollowingmethods:sizeOReturnthenumberofentriesinDisEmptyO:TestwhetherDisemptyfind(k):IfDcontainsanentryewithkey=k,thenreturneelsereturnnullfindAll(k):Returnaniterablecollectioncontainingall entrieswithkey-kinsert(k, v): Insert an entry into D, returningthe entry createdremove(e):remove fromD an entye,returingtheremoved entryor nullifewas notinDentriesO:returnan iterablecollectionofthekey-value entries inD3BinarySearchTrees
Binary Search Trees 3 ADT for Dictionary: A Dictionary stores elements (entries). •Each element (entry) is a key-value pair (k, v), where k is the key and v can be any object to store additional information. •The key is NOT unique. Dictionary support the following methods: size(): Return the number of entries in D isEmpty(): Test whether D is empty find(k): If D contains an entry e with key=k, then return e else return null. findAll(k): Return an iterable collection containing all entries with key=k. insert(k, v): Insert an entry into D, returning the entry created. remove(e): remove from D an enty e, returing the removed entry or null if e was not in D. entries(): return an iterable collection of the key-value entries in D
Part-F1BinarySearch TreesBinarySearchTrees
Binary Search Trees 4 Part-F1 Binary Search Trees < > =
品品Search TreesTree data structure that can be used toimplement adictionaryfind(k):If D contains an entry e with key=kthen return e else return null.findAll(k):Returnan iterable collectioncontaining all entries withkey=kinsert(k,v):Insert an entry into D,returningtheentry created.remove(e:removefrom D an enty e,returingtheremoved entry or null if ewasnot in D5BinarySearchTrees
Binary Search Trees 5 Search Trees Tree data structure that can be used to implement a dictionary. find(k): If D contains an entry e with key=k, then return e else return null. findAll(k): Return an iterable collection containing all entries with key=k. insert(k, v): Insert an entry into D, returning the entry created. remove(e): remove from D an enty e, returing the removed entry or null if e was not in D