A binary search tree (BST) is a binary tree with one rule: for every node, all keys in its left subtree are smaller, and all keys in its right subtree are larger. That's what makes searching fast: each comparison rules out a whole subtree.
A neat consequence: visiting left subtree, then the node, then right subtree (an in-order traversal) lists the keys in sorted order. Step through it:
Start at the root. If the key matches, you're done. If it's smaller, go left; if larger, go right. Fall off the tree (reach an empty spot) and the key isn't there.
Search for the new key. Where the search falls off the tree is exactly where the key belongs: attach it there as a new leaf. Nothing else moves.
Find the node first; call it D. Then it depends on how many children D has:
| D has | What to do |
|---|---|
| No children | Just remove it. |
| One child | The child (with its whole subtree) moves up into D's place. |
| Two children | Replace D with its in-order successor, S: the smallest key in D's right subtree. Find it by going right once, then left as far as possible. S has no left child, so taking it out of its old spot is one of the easy cases. |
Why the successor? It is the next key in sorted order, so it is larger than everything in D's left subtree and smaller than everything else in the right subtree: a perfect stand-in. The predecessor (the largest key on the left) works just as well; these pages use the successor.
Every operation walks one path from the root, so it costs O(height). With random keys the height stays around O(log n). Insert keys in sorted order, though, and every new key goes right, so the tree becomes a chain with height n:
Self-balancing trees fix this by restructuring after each insert: AVL trees and red-black trees.