Optimal Binary Search Trees

 Problem
» Given sequence K = k1 < k2 <··· < kn of n sorted keys,
with a search probability pi for each key ki.
» Want to build a binary search tree (BST)
with minimum expected search cost.
» Actual cost = # of items examined.
» For key ki, cost = depthT(ki)+1, where depthT(ki) = depth of ki in
BST T .

dynprog - 1 Lin / Devi

Intro 1
 Expected Search Cost
E[search cost in T ]
n
  (depthT (ki )  1)  pi
i 1
n n
  depthT (ki )  pi   pi
i 1 i 1
n Sum of probabilities is 1.
 1   depthT (ki )  pi (15.16)
i 1

dynprog - 2 Lin / Devi

Intro 2
 Example
 Consider 5 keys with these search probabilities:
p1 = 0.25, p2 = 0.2, p3 = 0.05, p4 = 0.2, p5 = 0.3.
k2 i depthT(ki) depthT(ki)·pi
1 1 0.25
2 0 0
k1 k4 3 2 0.1
4 1 0.2
5 2 0.6
1.15
k3 k5
Therefore, E[search cost] = 2.15.

dynprog - 3 Lin / Devi

Intro 3
 Example
 p1 = 0.25, p2 = 0.2, p3 = 0.05, p4 = 0.2, p5 = 0.3.

k2 i depthT(ki) depthT(ki)·pi
1 1 0.25
2 0 0
k1 k5 3 3 0.15
4 2 0.4
5 1 0.3
1.10
k4
Therefore, E[search cost] = 2.10.

k3 This tree turns out to be optimal for this set of keys.

dynprog - 4 Lin / Devi

Intro 4
 Example
 Observations:
» Optimal BST may not have smallest height.
» Optimal BST may not have highest-probability key at
root.
 Build by exhaustive checking?
» Construct each n-node BST.
» For each,
assign keys and compute expected search cost.
» But there are (4n/n3/2) different BSTs with n nodes.

dynprog - 5 Lin / Devi

Intro 5
 Optimal Substructure
 Any subtree of a BST contains keys in a contiguous range
ki, ..., kj for some 1 ≤ i ≤ j ≤ n.

T

 If T is an optimal BST and

T contains subtree T with keys ki, ... ,kj ,
then T must be an optimal BST for keys ki, ..., kj.
 Proof: Cut and paste.

dynprog - 6 Lin / Devi

Intro 6
 Optimal Substructure
 One of the keys in ki, …,kj, say kr, where i ≤ r ≤ j,
must be the root of an optimal subtree for these keys.
 Left subtree of kr contains ki,...,kr1.
kr
 Right subtree of kr contains kr+1, ...,kj.

ki kr-1 kr+1 kj
 To find an optimal BST:
» Examine all candidate roots kr , for i ≤ r ≤ j
» Determine all optimal BSTs containing ki,...,kr1 and
containing kr+1,...,kj

dynprog - 7 Lin / Devi

Intro 7
 Recursive Solution
 Find optimal BST for ki,...,kj, where i ≥ 1, j ≤ n, j ≥ i1.
When j = i1, the tree is empty.
 Define e[i, j ] = expected search cost of optimal BST for ki,...,kj.

 If j = i1, then e[i, j ] = 0.

 If j ≥ i,
» Select a root kr, for some i ≤ r ≤ j .
» Recursively make an optimal BSTs
• for ki,..,kr1 as the left subtree, and
• for kr+1,..,kj as the right subtree.

dynprog - 8 Lin / Devi

Intro 8
 Recursive Solution
 When the OPT subtree becomes a subtree of a node:
» Depth of every node in OPT subtree goes up by 1.
» Expected search cost increases by
j
w(i, j )   pl from (15.16)
l i

 If kr is the root of an optimal BST for ki,..,kj :

» e[i, j ] = pr + (e[i, r1] + w(i, r1))+(e[r+1, j] + w(r+1, j))
= e[i, r1] + e[r+1, j] + w(i, j). (because w(i, j)=w(i,r1) + pr + w(r + 1, j))
 But, we don’t know kr. Hence,
0 if j  i  1
e[i, j ]  
min {e[i, r  1]  e[r  1, j ]  w(i, j )} if i  j
ir  j

dynprog - 9 Lin / Devi

Intro 9
 Computing an Optimal Solution
For each subproblem (i,j), store:
 expected search cost in a table e[1 ..n+1 , 0 ..n]
» Will use only entries e[i, j ], where j ≥ i1.
 root[i, j ] = root of subtree with keys ki,..,kj, for 1 ≤ i ≤ j ≤ n.
 w[1..n+1, 0..n] = sum of probabilities
» w[i, i1] = 0 for 1 ≤ i ≤ n.
» w[i, j ] = w[i, j-1] + pj for 1 ≤ i ≤ j ≤ n.

dynprog - 10 Lin / Devi

Intro 10
 Pseudo-code
OPTIMAL-BST(p, q, n)
1. for i ← 1 to n + 1
2. do e[i, i 1] ← 0
Consider all trees with l keys.
3. w[i, i 1] ← 0
4. for l ← 1 to n Fix the first key.
5. do for i ← 1 to nl + 1 Fix the last key
6. do j ←i + l1
7. e[i, j ]←∞
8. w[i, j ] ← w[i, j1] + pj
9. for r ←i to j
10. do t ← e[i, r1] + e[r + 1, j ] + w[i, j ] Determine the root
11. if t < e[i, j ] of the optimal
12. then e[i, j ] ← t (sub)tree
13. root[i, j ] ←r
14. return e and root

Time: O(n3)
dynprog - 11 Lin / Devi
Intro 11
 Elements of Dynamic Programming
 Optimal substructure
 Overlapping subproblems

dynprog - 12 Lin / Devi

Intro 12
 Optimal Substructure
 Show that a solution to a problem consists of making a
choice, which leaves one or more subproblems to solve.
 Suppose that you are given this last choice that leads to an
optimal solution.
 Given this choice, determine which subproblems arise and
how to characterize the resulting space of subproblems.
 Show that the solutions to the subproblems used within
the optimal solution must themselves be optimal. Usually
use cut-and-paste.
 Need to ensure that a wide enough range of choices and
subproblems are considered.
dynprog - 13 Lin / Devi
Intro 13
 Optimal Substructure
 Optimal substructure varies across problem domains:
» 1. How many subproblems are used in an optimal solution.
» 2. How many choices in determining which subproblem(s) to
use.
 Informally, running time depends on (# of subproblems
overall)  (# of choices).
 How many subproblems and choices do the examples
considered contain?
 Dynamic programming uses optimal substructure bottom
up.
» First find optimal solutions to subproblems.
» Then choose which to use in optimal solution to the problem.
dynprog - 14 Lin / Devi
Intro 14
 Optimal Substucture
 Does optimal substructure apply to all optimization
problems? No.
 Applies to determining the shortest path but NOT the
longest simple path of an unweighted directed graph.
 Why?
» Shortest path has independent subproblems.
» Solution to one subproblem does not affect solution to another
subproblem of the same problem.
» Subproblems are not independent in longest simple path.
• Solution to one subproblem affects the solutions to other subproblems.
» Example:

dynprog - 15 Lin / Devi

Intro 15
 Overlapping Subproblems
 The space of subproblems must be “small”.
 The total number of distinct subproblems is a polynomial
in the input size.
» A recursive algorithm is exponential because it solves the same
problems repeatedly.
» If divide-and-conquer is applicable, then each problem solved
will be brand new.

dynprog - 16 Lin / Devi

Intro 16