Slide 14.5: An AVL tree

Slide 14.4: A binary search tree (cont.)
Slide 14.6: An AVL tree (cont.)
Home

An AVL Tree

An unbalanced tree is one of the major problems that a binary search tree may have. AVL trees were introduced to guarantee that balanced trees are always created. The definition of an AVL tree is

A balanced binary search tree where the height of the two subtrees of a node differs by at most one.

The figure below shows some examples of AVL and non-AVL trees. In each of the non-AVL trees, the root of the subtree that is not in balance is marked with an X.

The operations used to build and maintain AVL trees will not be covered in this course. Just note that look-up, insertion, and deletion are O(log₂n), where n is the number of nodes in the tree.

^†By setting a maximum allowable height difference of any two subtrees, AVL trees guarantee a minimum level of performance in searching.

^‡However, AVL trees are not themselves directly applicable to most file structure problems because, like all strictly binary trees, they have too many levels—they are too deep.