Slide 14.6: An AVL tree (cont.)

An AVL Tree (Cont.)

Consider the following input keys: B C G E F D A . The completely balanced search tree made up from the input keys is shown on the left.

The AVL tree resulting from the same input keys, arriving in the same sequence, is illustrated on the right.

The worst-case search performance in an AVL tree is guaranteed to approximate that of a completely balanced tree:

For a completely balanced tree, to find a key, given N possible keys, looks at log₂(N+1) levels of the tree.
For an AVL tree, the search could look at 1.44×log₂(N+2) levels.

For example, if N = 1000000, in the worst case:

A completely balanced tree requires seeking to log₂(1000000+1) = 20 levels.
An AVL tree requires seeking to 1.44×log₂(1000000+2) = 29 levels.

When we are using secondary storage, a procedure that requires more than 5 or 6 seeks to find a key is less than desirable; 20 or 29 seeks are unacceptable.

The height balancing using AVL methods is with a cost O(log₂n) that is acceptable in most applications. Thus, the AVL trees solve the problem of keeping an index in sorted order, but the search problem is not yet solved.