Binary Search Tree
BST properties, operation costs, and the worst-case degeneration into a linked list.
~/posts/binary-search-tree $ cat post.md
Trees of trees
Red-black trees, search trees, and the various near-optimal trees are all binary trees. A binary tree is a tree where every node has at most two children — by that definition, a linked list is a degenerate binary tree. The structure’s value comes from the fact that the left and right children aren’t interchangeable; that’s what lets it carry ordering information. One sleeper point: a BST with zero nodes is still a BST (the empty tree counts), just as a binary tree can have zero nodes.
Definition
A binary search tree is either empty, or a binary tree that satisfies all of:
- If the left subtree of any node is non-empty, every node in it has a value less than the node’s value.
- If the right subtree of any node is non-empty, every node in it has a value greater than the node’s value.
- Both subtrees of any node are themselves BSTs.
- No two nodes share a key.
The takeaway is that every node’s value is in a predictable relation
to the values in its subtrees. Lookup, insert, and delete each cost
O(log n) on average. Lookup is obvious; insert and delete hit that
bound because a BST doesn’t require the whole tree to be sorted — an
insert just walks down to a valid slot and links the new node in.
Worst case
A linked list is a degenerate binary tree. If every insertion goes to
the same side (say, always the left), the tree’s height equals the
number of nodes and the BST degenerates into a linear structure.
Linear structures take O(n) for lookup, insert, and delete — which
is also a BST’s worst case.