Summary

In this chapter, we saw a collection of searchable and modifiable data structures. All of these allowed you to insert new elements or delete elements while still remaining searchable and that too quite optimally. We saw binary search trees in which a search follows the paths of the tree from the root. Binary search trees can be modified optimally while still remaining searchable if they are of the self-balancing type. We studied two different kinds of self-balancing trees: AVL trees and red-black trees. Red-black trees are less balanced than AVL trees, but they involve a fewer number of rotations than AVL trees. In the end, we went through the hash table, which is a different kind of searchable structure. Although the worst case complexity of search or insertion is O(n), hash tables provide constant time search and average time insertion (O(lg n)) in most cases. If a hash table does not keep growing, the average insertion and deletion operations will also be constant time.

In the...