4.7. Dictionary Implementation Using a BST¶

A simple implementation for the Dictionary ADT can be based on sorted or unsorted lists. When implementing the dictionary with an unsorted list, inserting a new record into the dictionary can be performed quickly by putting it at the end of the list. However, searching an unsorted list for a particular record requires \(\Theta(n)\) time in the average case. For a large database, this is probably much too slow. Alternatively, the records can be stored in a sorted list. If the list is implemented using a linked list, then no speedup to the search operation will result from storing the records in sorted order. On the other hand, if we use a sorted array-based list to implement the dictionary, then binary search can be used to find a record in only \(\Theta(\log n)\) time. However, insertion will now require \(\Theta(n)\) time on average because, once the proper location for the new record in the sorted list has been found, many records might be shifted to make room for the new record.

Is there some way to organize a collection of records so that inserting records and searching for records can both be done quickly? We can do this with a binary search tree (BST). The advantage of using the BST is that all major operations (insert, search, and remove) are \(\Theta(\log n)\) in the average case. Of course, if the tree is badly balanced, then the cost can be as bad as \(\Theta(n)\).