532
Graphs and Trees
praCTiCe 25
a. Draw the decision tree for the binary search algorithm on a sorted list of five elements.
b. Find the depth of the tree and compare to 1 + :log 5;.
■
Lower Bounds on Searching
We have used decision trees to represent the actions of two particular search algorithms. Such a tree could be used to represent the actions of any algorithm that
solves the search problem by comparing the target element to the list elements.
The internal nodes of such a tree would represent the comparisons done, and the
depth of the tree would be the worst-case number of comparisons over all possible
cases. What can be said about such a tree when we don’t know the particulars of
the algorithm involved? We can say that x must be compared to every element
in the list at least once (perhaps more than once if the algorithm is quite stupid).
For if there is some list element that escapes being compared to x, the algorithm
cannot say whether that element equals x and thus cannot decide with certainty
whether x belongs to the list. Comparisons are internal nodes in the decision tree.
Therefore, if m is the number of internal nodes in the decision tree T 1 for any
search algorithm acting on an n-element list, then m ≥ n.
Before proceeding further with decision trees, we need some additional facts
about binary trees in general. The number of nodes at each level in a full binary tree
follows a geometric progression: 1 node at level 0, 2
1
nodes at level 1, 2
2
nodes at level
2, and so on. In a full binary tree of depth d, the total number of nodes is therefore
1 + 2 + 2
2
+ 2
3
+ c + 2
d
= 2
d+1
− 1
(see Example 15 of Chapter 2). A full binary tree has the maximum number of
nodes for a given depth of any binary tree. This gives us fact 1:
1. Any binary tree of depth d has at most 2
d+1
− 1 nodes.
Fact 2, which we’ll prove momentarily, is
2. Any binary tree with m nodes has depth ≥ :log m;.
To prove fact 2, we’ll use a proof by contradiction. Suppose a binary tree has m
nodes and depth d < :log m;. Then d ≤ :log m; − 1. From fact 1,
m ≤ 2
d+1
− 1 ≤ 2
(:log m; −1) +1
− 1
= 2
:log m;
− 1 ≤ 2
log m
− 1 = m − 1
or
m ≤ m − 1
—a contradiction. Therefore d ≥ :log m;.
Now back to decision trees representing search algorithms on n-element
lists. Temporarily strip the leaves from tree T 1 (with m internal nodes) to create a
new tree T 2 with m nodes, m ≥ n. By fact 2, T 2 has depth d ≥ :log m; ≥ :log n;.
Graphs and Trees
praCTiCe 25
a. Draw the decision tree for the binary search algorithm on a sorted list of five elements.
b. Find the depth of the tree and compare to 1 + :log 5;.
■
Lower Bounds on Searching
We have used decision trees to represent the actions of two particular search algorithms. Such a tree could be used to represent the actions of any algorithm that
solves the search problem by comparing the target element to the list elements.
The internal nodes of such a tree would represent the comparisons done, and the
depth of the tree would be the worst-case number of comparisons over all possible
cases. What can be said about such a tree when we don’t know the particulars of
the algorithm involved? We can say that x must be compared to every element
in the list at least once (perhaps more than once if the algorithm is quite stupid).
For if there is some list element that escapes being compared to x, the algorithm
cannot say whether that element equals x and thus cannot decide with certainty
whether x belongs to the list. Comparisons are internal nodes in the decision tree.
Therefore, if m is the number of internal nodes in the decision tree T 1 for any
search algorithm acting on an n-element list, then m ≥ n.
Before proceeding further with decision trees, we need some additional facts
about binary trees in general. The number of nodes at each level in a full binary tree
follows a geometric progression: 1 node at level 0, 2
1
nodes at level 1, 2
2
nodes at level
2, and so on. In a full binary tree of depth d, the total number of nodes is therefore
1 + 2 + 2
2
+ 2
3
+ c + 2
d
= 2
d+1
− 1
(see Example 15 of Chapter 2). A full binary tree has the maximum number of
nodes for a given depth of any binary tree. This gives us fact 1:
1. Any binary tree of depth d has at most 2
d+1
− 1 nodes.
Fact 2, which we’ll prove momentarily, is
2. Any binary tree with m nodes has depth ≥ :log m;.
To prove fact 2, we’ll use a proof by contradiction. Suppose a binary tree has m
nodes and depth d < :log m;. Then d ≤ :log m; − 1. From fact 1,
m ≤ 2
d+1
− 1 ≤ 2
(:log m; −1) +1
− 1
= 2
:log m;
− 1 ≤ 2
log m
− 1 = m − 1
or
m ≤ m − 1
—a contradiction. Therefore d ≥ :log m;.
Now back to decision trees representing search algorithms on n-element
lists. Temporarily strip the leaves from tree T 1 (with m internal nodes) to create a
new tree T 2 with m nodes, m ≥ n. By fact 2, T 2 has depth d ≥ :log m; ≥ :log n;.