9.4.8 Binary Search Tree Overview

Easily constructed binary search trees allow efficient insertion and deletion and can also be searched in average time O(1g n). More complex construction, insertion, and deletion algorithms for balanced binary search trees guarantee search, insertion, and deletion in worst-case time O(1g n). Binary search trees allow easy access to records in sorted order, and balanced binary search trees also allow O(lg i) access to the ith record in sorted order. It is not necessary to estimate in advance how many entries will be made in a binary search tree, as it is for hash tables. Hash tables can be searched very quickly, on the average, when properly constructed, but they do not allow records to be easily enumerated in sorted order.