The binary search algorithm and sorting algorithms combined together lead to the idea of having a container that keeps items sorted by default. One such container is the std::set, based on a balanced tree. Before discussing the balanced tree itself, let's take a look at the binary search tree, a perfect candidate for fast lookups.
The idea of the binary search tree is that the values of the left-hand subtree of a node are less than the node's value. By contrast, the values of the right-hand subtree of a node are greater than the node's value. Here's an example of a binary search tree:
As you can see in the preceding diagram, the element with the value 15 resides in the left-hand subtree because it's less than 30 (the root element). On the other hand, the element with the value 60 resides in the right-hand subtree because it...
