Optimal Binary Search Trees: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
(9 intermediate revisions by the same user not shown)
Line 7: Line 7:


=Internal=
=Internal=
* [[Algorithms#Dynamic_Programming_Algorithms|Dynamic Programming Algorithms]]
* [[Dynamic_Programming#Canonical_Use|Dynamic Programming]]
* [[Binary_Search_Trees#Computing_Optimal_Binary_Search_Trees|Binary Search Trees]]
* [[Binary_Search_Trees#Computing_Optimal_Binary_Search_Trees|Binary Search Trees]]


Line 24: Line 24:
  C<sub>ij</sub>= min{ ∑ p<sub>k</sub> + C<sub>i(r-1)</sub> + C<sub>(r+1)j</sub> }
  C<sub>ij</sub>= min{ ∑ p<sub>k</sub> + C<sub>i(r-1)</sub> + C<sub>(r+1)j</sub> }
       r=i k=i
       r=i k=i
</font>


The algorithm:
<font size=-1>
Let A be a bidimensional array <font color=teal># A[i,j] represents optimal BST value for items {i,...,j}</font>
for s = 0 to (n-1) <font color=teal># s represents (j-i), so i+s plays the role of j</font>
  for i = 1 to n
    if (i + s > n) continue
                i+s  i+s
    A[i, i+s] = min { ∑ p<sub>k</sub> + A[i,r-1] + A[r+i,i+s] } <font color=teal># interpret as 0 if the first index is bigger than the second index</font>
                r=i  k=i
return A[1,n]
</font>
</font>
==Running Time==
There are Θ(n<sup>2</sup>) subproblems. However, the subproblems are NOT Θ(1), some of them are Θ(n) (Θ(j-i) to compute A[i,j] so the overall running time is Θ(n<sup>3</sup>).
==Playground Implementation==
{{External|https://github.com/ovidiuf/playground/blob/master/learning/stanford-algorithms-specialization/15-dynamic-programming-optimal-binary-search-tree/src/main/java/playground/stanford/obst/Main.java}}

Latest revision as of 02:32, 30 November 2021

External

Internal

Overview

A balanced binary search tree exposes all its nodes via at most log n node traversals. However, if some of the search terms are more accessed than others, and we know a priori the relative access frequency, a balanced search tree might not be optimal. Instead, a tree that keeps the most frequently accessed nodes higher up in the tree offers better performance overall. An optimal search tree minimize the average search time with respect to a given set of probabilities over the keys. The cost of searching in the tree is given by the number of node assessments: if the key we look for is in the root, we only need to look at the root, so the number of node we need to assess is 1, if the key is immediately under the root, the cost is 2, and so on.

Optimal Substructure Lemma

If T is an optimal binary search tree for the keys {1, 2, ... n} with root r, and the keys in sorted order, then its subtrees T1 and T2 are optimal binary search trees for the keys {1, 2, ... r-1} and {r+1, ..., n} respectively.

Dynamic Programming Algorithm

The essence of a dynamic programming algorithm is to express the solution of larger problems as a function of solution of smaller problems. In the optimal binary search tree case, the smaller subproblems can obtained by either throwing away a prefix (the subtree T1) or a suffix (the subtree T2) of the original problem.

For an interval of keys 1 ≤ i ≤ j ≤ n, let Cij be the weighted search cost of an optimal binary search tree for items {i, i+1, ..., j-1, j}. The corresponding key probabilities are pi, pi+1, ..., pj.

The recurrence formula is, for every 1 ≤ i ≤ j ≤ n:

      j   j   
Cij= min{ ∑ pk + Ci(r-1) + C(r+1)j }
     r=i k=i

The algorithm:

Let A be a bidimensional array # A[i,j] represents optimal BST value for items {i,...,j}
for s = 0 to (n-1) # s represents (j-i), so i+s plays the role of j
  for i = 1 to n
    if (i + s > n) continue
                i+s  i+s
    A[i, i+s] = min { ∑ pk + A[i,r-1] + A[r+i,i+s] } # interpret as 0 if the first index is bigger than the second index
                r=i  k=i
return A[1,n]

Running Time

There are Θ(n2) subproblems. However, the subproblems are NOT Θ(1), some of them are Θ(n) (Θ(j-i) to compute A[i,j] so the overall running time is Θ(n3).

Playground Implementation

https://github.com/ovidiuf/playground/blob/master/learning/stanford-algorithms-specialization/15-dynamic-programming-optimal-binary-search-tree/src/main/java/playground/stanford/obst/Main.java