operation in [ ] [kv delete( )del [kt find position(kt first) last) find min) find maxt before( ) after(pt find lt( ) find le( ) find gt( ) find ge(kt find range(startstopiter( )reversed(trunning time (ho(ho(ho(ho(ho(ho(ho( ho(ntable worst-case running times of the operations for treemap we denote the current height of the tree with hand the number of items reported by find range as the space usage is ( )where is the number of items stored in the map binary search tree is therefore an efficient implementation of map with entries only if its height is small in the best caset has height log( ) which yields logarithmic-time performance for all the map operations in the worst casehowevert has height nin which case it would look and feel like an ordered list implementation of map such worst-case configuration arisesfor exampleif we insert items with keys in increasing or decreasing order (see figure figure example of binary search tree with linear heightobtained by inserting entries with keys in increasing order we can nevertheless take comfort thaton averagea binary search tree with keys generated from random series of insertions and removals of keys has expected height (log )the justification of this statement is beyond the scope of the bookrequiring careful mathematical language to precisely define what we mean by random series of insertions and removalsand sophisticated probability theory in applications where one cannot guarantee the random nature of updatesit is better to rely on variations of search treespresented in the remainder of this that guarantee worst-case height of (log )and thus (log nworstcase time for searchesinsertionsand deletions