Binary search trees

A binary search tree stores keys in sorted order using a branching structure: at each node, smaller keys go to the left and larger keys go to the right. To find a key you start at the top and go left or right at each step, like a game of higher-or-lower. That takes as many steps as the tree is tall. If keys arrive in sorted order the tree degenerates into a long stick and search becomes a linear walk, so practical versions such as AVL and red-black trees rebalance themselves with small rotations to stay around log n levels deep. They back ordered maps and sets, like C++’s std::map and Java’s TreeMap.