Section 31.12 Sets and Maps
Our basic BST can easily be adapted to implement a set. All we would need to do is ensure that duplicate values are not inserted. We can do this by modifying the insert function to check for equality and simply do nothing if the value is already present.
We can also use a BST to implement a map, This would take a little more work, since we would need to store key-value pairs in each node instead of just a single value. This would require modifying any logic that compares values to instead compare keys. But the overall structure of the tree and the algorithms for insertion, searching, and deletion would remain largely the same.
The C++ standard library specification for
std::set and std::map guarantee logarithmic time complexity for insertion, deletion, and lookup operations by using balanced binary search trees as the underlying data structure.Our simple implementation of a BST should offer \(O(\log n)\) time complexity for insertion, deletion, and lookup operations on a randomly ordered set of data. However, we can’t provide any guarantees about performance because our tree can become unbalanced with certain patterns of insertions and deletions.
To give a strong guarantee of \(O(\log n)\) performance no matter what sequence of operations are performed, library implementations of these structures rely on specialized versions of binary search trees called self-balancing binary search trees that maintain balance automatically during insertions and deletions. We will explore these in the next chapter.
You have attempted of activities on this page.
