avl trees in the previous sectionwe discussed what should be an efficient dictionary data structurebut the worst-case performance it achieves for the various operations is linear timewhich is no better than the performance of listand array-based dictionary implementations (such as unordered lists and search tables discussed in in this sectionwe describe simple way of correcting this problem so as to achieve logarithmic time for all the fundamental dictionary 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 the rule we consider in this section is the following height-balance propertywhich characterizes the structure of binary search tree in terms of the heights of its internal nodes (recall from section that the height of node in tree is the length of longest path from to an external node)height-balance propertyfor every internal node of tthe 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 entries are shown inside the nodesand the heights of the nodes are shown next to the nodes