performance of avl trees by proposition the height of an avl tree with items is guaranteed to be (log nbecause the standard binary search tree operation had running times bounded by the height (see table )and because the additional work in maintaining balance factors and restructuring an avl tree can be bounded by the length of path in the treethe traditional map operations run in worst-case logarithmic time with an avl tree we summarize these results in table and illustrate this performance in figure 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 (log no(log no(log no(log no(log no(log no(log no( log no(ntable worst-case running times of operations for an -item sorted map realized as an avl tree twith denoting the number of items reported by find range height time per level ( avl tree to( (log ndown phase ( up phase worst-case time: (log nfigure illustrating the running time of searches and updates in an avl tree the time performance is ( per levelbroken into down phasewhich typically involves searchingand an up phasewhich typically involves updating height values and performing local trinode restructurings (rotations