Searching a Binary Search Tree
Chapter Sixty-Five
Syllabus topic Module 2, "Trees: Binary Search Tree"
Pages 199 to 201 of 411
In one line
Searching compares the target with the node and goes left or right, discarding an entire subtree at each step, so the cost is the height of the tree.
The algorithm
search(node, target):
while node is not null:
if target == node.data: found
if target < node.data: node = node.left
else: node = node.right
not found
Four lines, no recursion needed, and each comparison eliminates one of the two subtrees entirely. That is the invariant of chapter 64 being spent.
Run, with the path shown
class BNode:
__slots__ = ("data", "left", "right")
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def insert(root, value):
if root is None:
return BNode(value)
if value < root.data:
root.left = insert(root.left, value)
elif value > root.data:
root.right = insert(root.right, value)
return root
def build(values):
root = None
for value in values:
root = insert(root, value)
return root
def search(root, target):
"""Returns (found, comparisons, path)."""
node, comparisons, path = root, 0, []
while node is not None:
comparisons += 1
path.append(node.data)
if target == node.data:
return True, comparisons, path
node = node.left if target < node.data else node.right
return False, comparisons, path
tree = build([50, 30, 70, 20, 40, 60, 80, 35, 45])
for target in (50, 35, 80, 55):
found, comparisons, path = search(tree, target)
print("search %-3d -> %-5s in %d comparison(s), path: %s"
% (target, found, comparisons, " ".join(str(p) for p in path)))
print()
print("searching for 35 went: 50, left to 30, right to 40, left to 35.")
print("at 50 the whole right subtree (60, 70, 80) was discarded in one comparison.")search 50 -> True in 1 comparison(s), path: 50
search 35 -> True in 4 comparison(s), path: 50 30 40 35
search 80 -> True in 3 comparison(s), path: 50 70 80
search 55 -> False in 3 comparison(s), path: 50 70 60
searching for 35 went: 50, left to 30, right to 40, left to 35.
at 50 the whole right subtree (60, 70, 80) was discarded in one comparison.Note the unsuccessful search for 55: it stops after 3 comparisons, not after examining the whole tree. An unsuccessful search in a BST costs the height, not n, which is the other half of the gain and is easy to forget.
The cost, measured against a linear search
import random
class BNode:
__slots__ = ("data", "left", "right")
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def insert(root, value):
if root is None:
return BNode(value)
if value < root.data:
root.left = insert(root.left, value)
elif value > root.data:
root.right = insert(root.right, value)
return root
def search_comparisons(root, target):
node, comparisons = root, 0
while node is not None:
comparisons += 1
if target == node.data:
return comparisons
node = node.left if target < node.data else node.right
return comparisons
def height(node):
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
random.seed(5)
print("%7s | %8s | %16s | %14s" % ("n", "height", "BST comparisons", "linear, worst"))
for n in (1000, 2000, 4000, 8000):
values = random.sample(range(n * 10), n)
root = None
for value in values:
root = insert(root, value)
sample = random.sample(values, 200)
worst = max(search_comparisons(root, v) for v in sample)
print("%7d | %8d | %16d | %14d" % (n, height(root), worst, n))Searching a Binary Search Tree
n | height | BST comparisons | linear, worst
1000 | 20 | 19 | 1000
2000 | 25 | 23 | 2000
4000 | 25 | 25 | 4000
8000 | 31 | 27 | 8000Eight thousand values, and the worst search among 200 tried took 27 comparisons. The linear search of chapter 16 would take up to 8,000.
Notice also that the heights run to 31 where the ideal for 8,000 nodes is 12. A tree built from random insertions is not perfectly balanced, but it is close enough to be useful: random insertion gives a height of about 1.39 times log2(n), which is a classical result and is what these numbers show.
The three costs
| Case | Comparisons |
|---|---|
| Best | 1, the target is the root |
| Average, random tree | about 1.39 log2(n) |
| Worst, balanced | the height, about log2(n) |
| Worst, degenerate | n, the tree is a line |
The last row is chapter 68, and it is the reason the AVL tree exists.
What searching gives you beyond "is it there"
Three operations fall out of the same walk, and they are why a tree beats a hash table when order matters:
Minimum. Walk left until you cannot. Maximum. Walk right until you cannot. Both cost the height.
Floor and ceiling. The largest value not greater than x, and the smallest not less than x. The same walk, remembering the last turn.
A hash table can do none of these without inspecting every key.
Quick revision
- Search compares with the node and goes left or right, discarding an entire subtree each time.
- Four lines, iterative, no recursion needed.
- An unsuccessful search also costs the height, not n.
- Measured: 8,000 random values gave a height of 31 and a worst search of 27 comparisons, against 8,000
for a linear search.
- A randomly built tree has height about 1.39 log2(n), not the ideal log2(n), but close enough.
- Best case 1 comparison, worst case the height, which is n for a degenerate tree.
- Minimum, maximum, floor and ceiling are the same walk, and a hash table can do none of them.
Test yourself
1. Write the search algorithm. Start at the root. While the node is not null: if the target equals the node's value, it is found; if the target is smaller go left, otherwise go right. If the walk falls off the tree, it is absent.
Searching a Binary Search Tree
2. What does each comparison achieve? It discards one of the two subtrees entirely, which is the invariant of chapter 64 being spent.
3. How much does an unsuccessful search cost? The height of the tree, not n. The walk stops as soon as it falls off the bottom.
4. Give the four cases for the number of comparisons. Best 1; average about 1.39 log2(n) for a randomly built tree; worst for a balanced tree the height, about log2(n); worst for a degenerate tree n.
5. In the measurement, what were the height and worst search for 8,000 values? Height 31 and a worst search of 27 comparisons, against up to 8,000 for a linear search.
6. Name two operations a search tree supports that a hash table cannot. Finding the minimum or maximum, and finding the floor or ceiling of a value. A hash table has no order, so it would have to inspect every key.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.