Card 07/ 09
Binary Search Tree vs Sorted Array and Hash Table
A balanced tree keeps keys in order and changes cheaply; the other two do only one of those.
A balanced binary search tree, a sorted array and a hash table can all store a set of keys and find one quickly, but they differ in whether they keep the keys in order and in what a change costs. This card covers the three side by side and the kind of workload each one suits.
A balanced binary search tree is one that keeps its height O(log n) by rearranging a few nodes whenever a key is inserted or deleted. The two common designs are the AVL tree, which keeps the heights of every node's two subtrees within one of each other, and the red-black tree, which uses a looser rule and rearranges less often; Java's TreeMap is a red-black tree. A plain binary search tree only matches the middle column below when its keys happen to arrive in a favourable order.
The operations that separate the three are the ones that depend on order. A range query asks for every key between two values, such as every order placed between 9:00 and 9:15. Ordered iteration visits every key from smallest to largest. A successor query asks for the next key above a given one, which may not be in the structure itself. In the table, n is the number of keys and k the number a range query returns.
| Operation | Balanced BST | Sorted array | Hash table |
|---|---|---|---|
| Look up a key | O(log n) | O(log n), by binary search | O(1) expected |
| Insert or delete a key | O(log n) | O(n), to shift the later keys along | O(1) expected |
| Smallest or largest key | O(log n) | O(1), at either end | O(n), every key checked |
| Next key above a given value | O(log n) | O(log n) | O(n), every key checked |
| Every key in a range | O(log n + k) | O(log n + k) | O(n), every key checked |
| Every key in sorted order | O(n) | O(n) | O(n log n), to sort them first |
| Memory beyond the keys | Two links per key | Little or none | Empty slots kept spare |
Each column wins somewhere. The hash table is fastest for looking up, inserting and deleting single keys, and it is the right choice whenever no question about order is ever asked. It scatters keys by their hash codes, so it has no idea which key comes next, and every ordered question becomes a scan of all n keys. The sorted array answers every ordered question as well as the tree does, uses the least memory and reads its neighbours fastest, but each insert or delete shifts up to n keys, so it suits data that is built once and then only read. The balanced tree is never the fastest at any single row, and it is the only one that is never slow: O(log n) for changes and for ordered questions alike.
The decision rule: lookups by exact key only, choose a hash table. Ordered questions on data that rarely changes, choose a sorted array. Ordered questions on data that changes often, such as a leaderboard, a booking calendar or an order book, choose a balanced binary search tree, which in Java means TreeMap or TreeSet.
← → move through sections and cards