(logn(expectedthe ordered dictionary adt in an ordered dictionarywe want to perform the usual dictionary operationsbut also maintain an order relation for the keys in our dictionary we can use comparator to provide the order relation among keysas we did for the ordered search table and skip list dictionary implementations described above indeedall of the dictionary implementations discussed in use comparator to store the dictionary in nondecreasing key order when the entries of dictionary are stored in orderwe can provide efficient implementations for additional methods in the dictionary adt for examplewe could consider adding the following methods to the dictionary adt so as to define the ordered dictionary adt first()return an entry with smallest key last()return an entry with largest key successors( )return an iterator of the entries with keys greater than or equal to kin nondecreasing order predecessors( )return an iterator of the entries with keys less than or equal to kin nonincreasing order implementing an ordered dictionary the ordered nature of the operations above makes the use of an unordered list or hash table inappropriate for implementing the dictionarybecause neither of these data structures maintains any ordering information for the keys in the dictionary indeedhash tables achieve their best search speeds when their keys are distributed almost at random thuswe should consider an ordered search table or skip list (or data structure from when dealing with ordered dictionaries for exampleusing skip list to implement an ordered dictionarywe can implement methods first(and last(in ( time by accessing the second and second to last positions of the bottom list also methods successors(kand predecessors(kcan be implemented to run in (lognexpected time moreoverthe iterators returned by the successors(kand predecessors(kmethods could be implemented using reference to current