DictionariesApplicationDictionary With DuplicatesDictionary OperationsHash Table DictionariesBin PackingBin Packing HeuristicsBest Fit ExampleBest FitSlide 10Slide 11Slide 12Slide 13Implementation Of Best FitSlide 15Complexity Of Best FitIndexed Binary Search TreeExample Indexed Binary Search TreeleftSize And RankSlide 20get(index) And remove(index)Slide 22Linear List As Indexed Binary TreePerformanceExperimental ResultsSlide 26FocusDictionaries•Collection of items.•Each item is a pair.(key, element)Pairs have different keys.Application•Collection of student records in this class.(key, element) = (student name, linear list of assignment and exam scores)All keys are distinct.•Collection of in-use domain names.(godaddy.com, owner information)All keys are distinct.Dictionary With Duplicates•Keys are not required to be distinct.•Word dictionary.Items/pairs are of the form (word, meaning).May have two or more entries for the same word.•(bolt, a threaded pin)•(bolt, a crash of thunder)•(bolt, to shoot forth suddenly)•(bolt, a gulp)•(bolt, a standard roll of cloth)•etc.Dictionary Operations•Static Dictionary.initialize/createget(theKey) (a.k.a. search)CD ROM word dictionaryCD ROM geographic database of cities, rivers, roads, auto navigation system, etc.•Dynamic Dictionary.get(theKey) (a.k.a. search)put(theKey, theElement) (a.k.a. insert)remove(theKey) (a.k.a. delete)Hash Table Dictionaries•O(1) expected time for get, put, and remove.•O(n) worst-case time for get, put, and remove.O(log n) if overflows handled by balanced search trees.•Not suitable for nearest match queries.Get element with smallest key >= theKey.•Not suitable for range queries.•Not suitable for indexed operations.Get element with third smallest key.Remove element with 5th smallest key.Bin Packing•n items to be packed into bins•each item has a size•each bin has a capacity of c•minimize number of binsBin Packing Heuristics•Best Fit.Items are packed one at a time in given order.To determine the bin for an item, first determine set S of bins into which the item fits.If S is empty, then start a new bin and put item into this new bin.Otherwise, pack into bin of S that has least available capacity.Best Fit Examplen = 4weights = [4, 7, 3, 6]capacity = 10Pack red item into first bin.Best Fitn = 4weights = [4, 7, 3, 6]capacity = 10Pack blue item next.Doesn’t fit, so start a new bin.Best Fitn = 4weights = [4, 7, 3, 6]capacity = 10Best Fitn = 4weights = [4, 7, 3, 6]capacity = 10Pack yellow item into second bin.Best Fitn = 4weights = [4, 7, 3, 6]capacity = 10Pack green item into first bin.Best Fitn = 4weights = [4, 7, 3, 6]capacity = 10Optimal packing.Implementation Of Best Fit•Use a dynamic dictionary (with duplicates) in which the items are of the form (available capacity, bin index).•Pack an item whose requirement is s.Find a bin with smallest available capacity >= s.Reduce available capacity of this bin by s.•May be done by removing old pair and inserting new one.If no such bin, start a new bin.•Insert a new pair into the dictionary.Best Fit Example•12 active bins.• Pack item whose size is 22.201062 815403025 35718Complexity Of Best Fit•Use a balanced binary search tree (with duplicates) in which the pairs are (available capacity, bin index).•O(n) get, put, and remove/put operations, where n is the number of items to be packed.•O(n log n).Indexed Binary Search Tree•Binary search tree.•Each node has an additional field.leftSize = number of nodes in its left subtreeExample Indexed Binary Search Tree201062 815403025 35718001140070013leftSize values are in redleftSize And RankRank of an element is its position in inorder (inorder = ascending key order).[2,6,7,8,10,15,18,20,25,30,35,40]rank(2) = 0rank(15) = 5rank(20) = 7lextSize(x) = rank(x) with respect to elements in subtree rooted at xleftSize And Rank201062 815403025 35718001140070013sorted list = [2,6,7,8,10,15,18,20,25,30,35,40]get(index) And remove(index)7201062 815403025 3571800114000013sorted list = [2,6,7,8,10,15,18,20,25,30,35,40]get(index) And remove(index)•if index = x.leftSize desired element is x.element•if index < x.leftSize desired element is index’th element in left subtree of x•if index > x.leftSize desired element is (index – x.leftSize – 1)’th element in right subtree of xLinear List As Indexed Binary Treeheba dflji kcg001140070013list = [a,b,c,d,e,f,g,h,i,j,k,l]Performance•Linear List.get(index)put(index, element)remove(index)•Array.O(1), O(n), O(n).•Chain.O(n), O(n), O(n).•Indexed AVL Tree (IAVL)O(log n), O(log n), O(log n).Experimental Results•40,000 of each operation.•Java code on a 350MHz PCPerformanceIndexed AVL Tree (IAVL)Operation Array Chain IAVLget 5.6ms 157sec 63msaverage puts 5.8sec 115sec 392msworst-case puts 11.8sec 157sec 544msaverage removes 5.8sec 149sec 1.5secworst-case removes 11.7sec 157sec 1.6secFocus•Tree structures for static and dynamic