continue marching up looking for moreall the way to the root stillsince the height of is (logn)where is the number of entriesby proposition (logntrinode restructurings are sufficient to restore the height-balance property performance of avl trees we summarize the analysis of the performance of an avl tree as follows operations findinsertand remove visit the nodes along root-to-leaf path of tpluspossiblytheir siblingsand spend ( time per node thussince the height of is (lognby proposition each of the above operations takes (logntime we leave the implementation and analysis of an efficient version of the operation findall as an interesting exercise in table we summarize the performance of dictionary implemented with an avl tree we illustrate this performance in figure table performance of an -entry dictionary realized by an avl treewhere denotes the size of the collection returned by findall the space usage is (noperation time sizeisempty ( findinsertremove (lognfindall (logn sfigure 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