Slide 14.3: A binary search tree (cont.)
Slide 14.5: An AVL tree
Home

A Binary Search Tree (Cont.)

A Balanced Binary Search Tree
The advantages of a binary search tree are shown only if the tree is balanced. The definition of a balanced tree is
A tree where the height of the shortest path to a leaf does not differ from the height of the longest path by more than one level.
For example, the following eight keys are entered to the previous tree in the sequence in which they appear:     LV NP MB TM LA UF ND TS NK.
The resulting tree is not balanced because the height difference of the path KF—FB—CL—AX and the path KF—SD—PA—NR—LV—NP—MB—ND—NK is more than 1.

Search performance for such an unbalanced tree is very poor because it needs many disk seeks. For example, it needs to check 9 nodes to search for the key NK.

In conclusion, a binary search tree is not able to fully solve the two problems mentioned previously because