7.3.3 A Binary Tree

Binary Trees combine the fast search time of an ordered array, O(log₂n) on the average, with the insertion ease of alinked list. Worst case (See Exercise 2) is still O(n) for retrievals.

Example 4 shows our example for a binary tree.

In Example 4, the tree is reasonable well balanced.

Binary trees are space-efficient since they consume an amount of space proportional to the number of nodes. Since new nodes are added as leaves, scoping is difficult unless separate trees are maintained for each scope.

Outputting an alphabetized list of names is also quite easy.

If the tree is allowed to become unbalanced, searching can degrade to a linear search. Exercise 2 discusses a worst case for a binary tree implementation. Exercise 6 discusses the use of AVL trees for symbol tables.