12.10 EFFICIENCY OF BST SEARCH AND RETRIEVAL

The operations take place upon ordered data using a process similar to array binary search. Until the sought value is found, further comparisons will involve either its left-hand sub-tree or its right-hand sub-tree. If the tree is balanced, this amounts to dividing the tree in two at each comparison since there will be an equal number of items in each sub-tree (or nearly so). The best case efficiency for a balanced tree is then the same O(log₂N) as for binary search. However, for a tree that is not balanced the efficiency will fall below this value as illustrated in Figure 12.30.

Figure 12.30. Retrieving a key value