Binary Search Trees

For every node: keys in the left subtree $<$ node $<$ keys in the right subtree. Searching follows one path from the root, so it takes $O(h)$ where $h$ is the height.

A balanced tree has $h \approx \log_2 n$; inserting sorted data into a plain BST makes it a linked list ($h = n$). Self-balancing trees — AVL and red-black trees (used by C++ std::map and Java TreeMap) — keep operations at $O(\log n)$.