avl trees the treemap classwhich uses standard binary search tree as its data structureshould be an efficient map data structurebut its worst-case performance for the various operations is linear timebecause it is possible that series of operations results in tree with linear height in this sectionwe describe simple balancing strategy that guarantees worst-case logarithmic running time for all the fundamental map operations definition of an avl tree the simple correction is to add rule to the binary search tree definition that will maintain logarithmic height for the tree although we originally defined the height of subtree rooted at position of tree to be the number of edges on the longest path from to leaf (see section )it is easier for explanation in this section to consider the height to be the number of nodes on such longest path by this definitiona leaf position has height while we trivially define the height of "nullchild to be in this sectionwe consider the following height-balance propertywhich characterizes the structure of binary search tree in terms of the heights of its nodes height-balance propertyfor every position of the heights of the children of differ by at most any binary search tree that satisfies the height-balance property is said to be an avl treenamed after the initials of its inventorsadel'son-vel'skii and landis an example of an avl tree is shown in figure figure an example of an avl tree the keys of the items are shown inside the nodesand the heights of the nodes are shown above the nodes (with empty subtrees having height