Binary search trees

New idea

Fast search and cheap inserts, at once?

A sorted array searches in O(log n), but inserting means shifting, O(n). A linked list adds at the front cheaply, but finding anything means walking, O(n). Can one structure do both well?

Meet the binary search tree. Like a linked list, it's made of nodes joined by pointers. But each node has two pointers: a left child and a right child. The top node is the root.

One rule makes it work: everything in a node's left side is smaller than it, and everything on its right side is bigger.

To insert, start at the root. Smaller? Go left. Bigger? Go right. Repeat until there's an empty spot, and hang the new node there.