Binary search trees

A balanced binary search tree of 1,023 keys finds any of them in at most 10 comparisons; built from sorted input, the same keys can take 1,023.

Binary search, built into the shape

Binary search on a sorted array finds a key in about log₂ n checks, but inserting into a sorted array moves values. A hash table inserts quickly, but it forgets order: it cannot easily tell you the smallest key or the next key after 40. A binary search tree (BST) aims for both. It is made of nodes, like a linked list, but each node has two pointers, left and right. The top node is the root; a node with no children is a leaf.

One rule makes it a search tree: for every node, all keys in its left subtree are smaller, and all keys in its right subtree are larger. To search for a key, start at the root and compare. Equal means found. Smaller means go left, larger means go right. Each comparison throws away a whole subtree, just as binary search throws away half the list. Searching the tree 50, 30, 70, 20, 40, 60, 80 for 60 compares with 50, then 70, then 60: 3 comparisons.

Inserting follows the same path. Go left or right until the pointer you need is empty, and hang the new node there. Inserting 45 compares with 50 (go left), 30 (go right) and 40 (go right), and 40 has no right child, so 45 becomes it. Deleting a node that is not a leaf takes one more idea: MIT's notes swap its item with the next or previous key in order and delete from there instead. The counting rule in the lab is one comparison per node on the path.

Height is everything

How many comparisons can a search take? At most one per level, so the cost depends on the tree's height, the number of edges on the longest path from the root down to a leaf. MIT's notes put it this way: tree operations run in O(h) time. The tree 50, 30, 70, 20, 40, 60, 80 has height 2, so no search needs more than 3 comparisons. A perfectly balanced tree with 1,023 nodes has height 9 and needs at most 10.

But the shape depends on insertion order. Insert 10, 20, 30, 40, 50, 60, 70 in sorted order and each key is larger than everything before it, so each new node goes to the right of the last one. The tree becomes a chain of height 6, and searching for 70 takes 7 comparisons: a linked list with extra pointers. With 1,023 sorted keys the worst search takes 1,023 comparisons instead of 10.

Balanced trees fix this by reshaping themselves after each insert or delete. The first scheme was the AVL tree, from Georgy Adelson-Velsky and Evgenii Landis in 1962, which MIT's lecture 7 covers. It keeps, at every node, the heights of the two subtrees within 1 of each other, and repairs any break with small local moves called rotations. That keeps the height O(log n), so search, insert and delete stay O(log n) whatever order the keys arrive in.

Keys in order for free

A BST keeps more than membership. Visit the left subtree, then the node, then the right subtree, recursively, and the keys come out in sorted order. This in-order walk (MIT calls it traversal order) is how a BST answers "smallest key", "largest key" and "next key after 40", the order operations of MIT's Set interface that a hash table cannot do quickly.