Binary search tree
In short: A binary search tree keeps smaller values to the left of each node and larger ones to the right, so a search costs the height of the tree, which balanced trees keep at O(log n).
Problem
The price index crawls
The shop's "price from … to …" filter searches a price index, not the whole catalog. The index is a binary tree: every price is a node, cheaper ones on the left, pricier ones on the right. With 1000 shuffled prices the tree has 22 levels, and writing and looking up every price takes 22,990 comparisons in total: about 23 per price.
This morning the supplier changed the format: the feed now arrives sorted by price. The same 1000 prices, the same code, and the comparisons jump to 1,000,000: 43 times more. The tree now has 1000 levels.
Why does the order of the input matter when the prices are the same?
The idea
Smaller to the left, bigger to the right
A binary search tree (BST) is made of nodes with two links each, left and right. There is one rule: everything in the left subtree of a node is smaller than it, everything in the right subtree is bigger.
So searching is a binary search without an array: at every node you compare and skip a whole subtree. Adding follows the same path until it reaches an empty spot and hangs the new node there. Nothing moves, unlike inserting into a sorted array.
def add(self, price): parent = None cur = self.root level = 1 while cur is not None: self.compares += 1 if price == cur.price: return False parent = cur cur = cur.left if price < cur.price else cur.right level += 1 node = Node(price) if parent is None: self.root = node elif price < parent.price: parent.left = node else: parent.right = node self.size += 1 self.depth = max(self.depth, level) return Truedef add(self, price): parent = None cur = self.root level = 1 while cur is not None: self.compares += 1 if price == cur.price: return False parent = cur cur = cur.left if price < cur.price else cur.right level += 1 node = Node(price) if parent is None: self.root = node elif price < parent.price: parent.left = node else: parent.right = node self.size += 1 self.depth = max(self.depth, level) return Truedef sorted(self): out = [] self._walk(self.root, out) return out
def _walk(self, node, out): if node is None: return self._walk(node.left, out) out.append(node.price) self._walk(node.right, out)Step by step, in words
- An empty price index. Every price walks down from the root: cheaper goes left, pricier goes right.
- 49 comes first. The tree is empty, so 49 becomes the root.
- 12 < 49: left. The spot is empty, so 12 becomes the left child of 49. 89 goes right.
- 24: cheaper than 49 (left), pricier than 12 (right). Two comparisons, and it lands on level 3.
- 32: 49, 12, 24, then right. Three comparisons for 7 prices: each one skips a whole subtree.
- walk: left subtree, the node, right subtree. The prices come out sorted: 6 12 24 32 49 89 159.
The number of comparisons is the number of levels on the path. If the tree is low, about log₂ n levels, every search is O(log n).
See it
Your own tree
A node holds the price and the two links:
class Node: def __init__(self, price): self.price = price self.left = None self.right = Noneadd walks down from the root and remembers the last node (parent). Once it reaches an empty spot, it hangs the new node to the left or to the right of parent. The same price does not go in twice. level counts the levels on the way, so the tree knows how deep it is:
def add(self, price): parent = None cur = self.root level = 1 while cur is not None: self.compares += 1 if price == cur.price: return False parent = cur cur = cur.left if price < cur.price else cur.right level += 1 node = Node(price) if parent is None: self.root = node elif price < parent.price: parent.left = node else: parent.right = node self.size += 1 self.depth = max(self.depth, level) return Truecontains follows the same path, but hangs nothing:
def contains(self, price): cur = self.root while cur is not None: self.compares += 1 if price == cur.price: return True cur = cur.left if price < cur.price else cur.right return FalseThe cheapest price is furthest left, the priciest furthest right (the tree is not empty):
def min(self): node = self.root while node.left is not None: node = node.left return node.price
def max(self): node = self.root while node.right is not None: node = node.right return node.priceIn-order traversal: first the left subtree, then the node, then the right subtree. That way the prices come out sorted. It uses recursion here, because every subtree is a tree again:
def sorted(self): out = [] self._walk(self.root, out) return out
def _walk(self, node, out): if node is None: return self._walk(node.left, out) out.append(node.price) self._walk(node.right, out)tree = PriceTree()for price in [49, 12, 89, 24, 6, 159, 32]: tree.add(price)print(f"in order: {tree.sorted()}")print(f"cheapest: {tree.min()}, priciest: {tree.max()}")for price in [32, 50]: tree.compares = 0 found = tree.contains(price) print(f"{price}: {'yes' if found else 'no'}, comparisons: {tree.compares}")in order: [6, 12, 24, 32, 49, 89, 159]cheapest: 6, priciest: 15932: yes, comparisons: 450: no, comparisons: 232 is found in 4 comparisons: 49, 12, 24, 32. For 50, 2 are enough: 49, then 89, and there is nothing to the left of 89, so 50 is missing.
Try it
How many comparisons?
tree = PriceTree()for price in [50, 30, 70, 20, 40, 60, 80]: tree.add(price)tree.compares = 0tree.contains(65)print(tree.compares)65 > 50: right, to 70. 65 < 70: left, to 60. 65 > 60: right, and that spot is empty. Three comparisons, and 65 is not there.
Try it
Fill in
The cheapest price:
def min(self):
node = self.root
while node. is not None:
node = node.left
return node.priceSmaller values are on the left, so you go left as long as you can. The last node is the smallest.
The idea
Sorted input: the tree becomes a chain
Back to the feed. When the prices arrive sorted, every new one is pricier than all so far. It passes every node on the right and hangs at the far right. Nothing ever goes left, and the tree is a chain: a linked list with useless empty links.
def add(self, price): parent = None cur = self.root level = 1 while cur is not None: self.compares += 1 if price == cur.price: return False parent = cur cur = cur.left if price < cur.price else cur.right level += 1 node = Node(price) if parent is None: self.root = node elif price < parent.price: parent.left = node else: parent.right = node self.size += 1 self.depth = max(self.depth, level) return TrueStep by step, in words
- The supplier feed sends the same 7 prices, but sorted: 6, 12, 24, 32, 49, 89, 159.
- Every new price is pricier than all before it, so it always goes right. Nothing ever goes left.
- Price number i walks past all i before it: 0 + 1 + … + 6 = 21 comparisons. The tree is a chain of 7 levels.
- contains(159) walks all 7 nodes, like a linked list. With 1000 prices: 1000 levels.
- The same prices, balanced: 3 levels instead of 7. AVL and red-black trees keep this shape with rotations.
Price number i walks past i nodes. For n prices that is 0 + 1 + … + (n − 1) when writing, and as much again plus n when searching: exactly n² comparisons. It is the same trap as quick sort's bad pivot: sorted input, and the worst case.
The program from the problem: the same 1000 prices, once sorted, once shuffled:
def shuffled(n): a = [100 + i for i in range(n)] x = 2026 for i in range(n - 1, 0, -1): x = x * 48271 % 2147483647 j = x % (i + 1) a[i], a[j] = a[j], a[i] return a
def report(prices): tree = PriceTree() for p in prices: tree.add(p) for p in prices: tree.contains(p) return f"depth {tree.depth}, comparisons {tree.compares}"feed = [100 + i for i in range(1000)]print(f"ascending: {report(feed)}")print(f"shuffled: {report(shuffled(1000))}")ascending: depth 1000, comparisons 1000000shuffled: depth 22, comparisons 22990Run both inputs in the browser:
- Prices in shuffled order
O(n log n) - Prices in ascending order
O(n²)
| Algorithm | n = 10 | n = 1,000 | n = 5,000 | n = 100,000 |
|---|---|---|---|---|
| Prices in shuffled order | 56 | 22,990 | 157,880 | 4,029,826 |
| Prices in ascending order | 100 | 1,000,000 | 25,000,000 | ≈ 10,000,000,000 |
With shuffled input a search passes on average through about 2 · ln n − 3 nodes (about 12 for 1000 prices), which grows like log n, and everything is O(n log n). With sorted input it is O(n²): for 1000 prices, 1,000,000 comparisons against 22,990. This is the difference between the average and the worst case, and real data is often exactly sorted: by price, by date, by number.
The idea
A balanced tree
Shuffling the input helps, but you can't always do it: the prices arrive one by one while the shop is running. A balanced tree fixes itself: after every add it checks whether one branch has become much longer than the other and rearranges it. That way the height stays O(log n) for any input, and every search, add and remove is O(log n).
The rearranging is a rotation: a node and its child swap places. In a right rotation the left child becomes the parent, the old parent becomes its right child, and the child's right subtree moves to the left of the old parent. The rule "smaller to the left" still holds, and one branch gets one level shorter.
More precisely, if you are curious
A right rotation around 32 in the chain 32 → 24 → 12 (each is the left child of the one before):
32 24 / / \ 24 → 12 32 / 1224 becomes the root and 32 goes to its right. The sorted order is the same: 12, 24, 32.
AVL (Adelson-Velsky and Landis, 1962) keeps the height of the subtree in every node. If the heights of the two children differ by more than 1, it does one or two rotations. The tree is very low (at most about 1.44 · log₂ n), so searching is fast, but adding sometimes does more work.
A red-black tree colors its nodes and keeps two rules: a red node has no red child, and every path from the root to an empty spot passes through the same number of black nodes. That lets one branch be at most twice as long as another, so the height is at most 2 · log₂ n. Adding and removing need recoloring and at most two or three rotations.
What the languages do:
- Java:
TreeMapandTreeSetare red-black trees. Besidesgetandputthey have the ordered operations:firstKey,floorKey(the largest up to a given key),subMap(from, to). They order byComparableor by aComparatoryou pass in. - C#:
SortedSet<T>is a red-black tree, andSortedDictionary<TKey, TValue>is built on top of it.SortedSethasMin,MaxandGetViewBetween(from, to). Watch out forSortedList<TKey, TValue>: it is two sorted arrays, so lookups are O(log n), but adding in the middle is O(n). - Python: there is no built-in balanced tree. The
bisectmodule searches a sorted list in O(log n), butinsortinserts in O(n), because it shifts the elements. Thesortedcontainerspackage (SortedList,SortedDict) is installed separately and is not a tree: it keeps a list of sorted lists of about a thousand elements each. - JavaScript: there is no built-in sorted tree.
MapandSetkeep insertion order, not order by value. What is left is a sorted array with binary search, or a library.
Try it
Find the bug
Someone rewrote add. Five prices go in, but the traversal shows only some of them, and the search can't find 6 and 24:
def add(self, price): parent = None cur = self.root level = 1 while cur is not None: self.compares += 1 if price == cur.price: return False parent = cur cur = cur.left if price < cur.price else cur.right level += 1 node = Node(price) if parent is None: self.root = node elif price > parent.price: parent.left = node else: parent.right = node self.size += 1 self.depth = max(self.depth, level) return Truetree = PriceTree()for price in [49, 12, 89, 24, 6]: tree.add(price)print(f"in order: {tree.sorted()}")print(f"6: {'yes' if tree.contains(6) else 'no'}")print(f"24: {'yes' if tree.contains(24) else 'no'}")in order: [49, 6]6: no24: noWhich line has the bug?
Pick the line with the bug.
The loop walks down correctly to the empty spot, but the node is hung on the other side of parent: the bigger one on the left, the smaller one on the right. There may already be a subtree there and it gets lost, and even if the spot is empty, the next search looks on the correct side and doesn't find it. The comparison must be price < parent.price, the same as in the loop.
Exercise
A price stops being valid
Solve this one in your own editor.
Removing from the index. Add remove(price), which returns whether it removed a price. There are three cases:
- the node is a leaf: just unhook it;
- it has one child: the child takes its place;
- it has two children: find the next bigger price (the leftmost one in the right subtree), put it in place of the removed one and remove it from the right subtree. It has no left child, so that is one of the first two cases.
Put in the prices 49, 12, 89, 24, 6, 159, 32 and remove 12 (two children), 49 (the root, two children) and 70 (missing):
-12: [6, 24, 32, 49, 89, 159]-49: [6, 24, 32, 89, 159]-70: noneroot: 89More tasks
- Prices in a range. Write
between(from, to), which returns the prices fromfromtotoin order, without walking the whole tree: don't go left from a node smaller thanfrom, nor right from a node bigger thanto. - The best within budget. Write
floor(budget): the priciest price that is not over the budget. Compare withfloorKeyin Java orGetViewBetweenin C#. - Height with recursion. Write
height(node)as 1 + the larger of the two children's heights. Run it on the chain of 1000 sorted prices. What happens in Python? And with 100,000 prices in Java?
Test