Binary search trees

Overview

Shows how ordering the children of a tree gives fast search, insert and delete on average.

In a binary search tree, every key in the left subtree is smaller than the node's key and every key in the right subtree is larger. Search follows one path from the root, so the cost is the height of the tree.

If keys are inserted in sorted order the tree degenerates into a list, which is why balanced variants exist.