Course: 113-1 Introduction to Algorithms. Lecturer: Huilan Chang. 2024.11.28 Reference: Optimal Binary Search Trees (Section 3.5 in Foundations Of Algorithms by Neapolitan)

Preliminaries

• A binary tree is a rooted tree where each node has at most two children.
  • The depth of a node is the number of edges from it to root.
  • The depth of a tree is the maximum depth of all its nodes.

Example.

• A binary search tree (二元蒐尋樹) is a binary tree of items satisfying

  (1) Each node contains one key.

  (2) For each node $v$, the keys in the left subtree of $v$ $\leq$ the key in $v$ $\leq$ the keys in the right subtree of $v$.

  Example. keys: A<B<C<D<E<F<G

  $T_1$ $T_2$ a balanced binary tree

• Search in binary search tree:

  Example. Find the node with key E in $T_1$.

• It all keys have the same probability of being the search key, then the average number of comparisons to locate a key is ① $= \frac{19}{7}$ in $T_1$.

  ② $= \frac{17}{7}$ in $T_2$. (better)

  $T_2$ (a balanced binary tree) is optimal in this assumption.

Probability of being the search key is not uniform

• Let $K_1, K_2, \cdots, K_n$ be the $n$ keys in order. Let $p_i$ be the probability that $K_i$ is the search key. In a search tree $T$, if $C_i$ is the number of comparisons needed to find $K_i$, then the average search time for $T$ is $\sum_{i=1}^n C_ip_i$. Goal: Determine a tree for which the average search time is minimized.

Example. $n=3, p_1=0.7, p_2=0.2, p_3=0.1$, keys A<B<C. All binary search trees:

• Note: ① The number of binary search trees of $n$ nodes is the Catalan number $C_n=\frac{1}{n+1}{2n\choose n}\sim \frac{4^n}{n^{1/2}\sqrt{\pi}}$ (exponentially many). Question: There are at least $2^{n-1}$ binary search trees of $n$ nodes. Why?

② Brute-force method is not efficient.

Dynamic Programming

• Recursive property

<aside>

Definition. Let $A[i][j]$ be the average search time for an optimal binary search trees with keys $K_i$ through $K_j$.

</aside>

<aside>

🌴 🌴 🌴  Optimal Substructure 🌴 🌴 🌴  If $T$ be an optimal tree with keys $K_1$ through $K_n$ with root $K_k$, then its left subtree is an optimal tree with keys $K_1$ through $K_{k-1}$, and its right subtree is an optimal tree with keys $K_{k+1}$ through $K_n$.

</aside>

• Example.

• If the optimal tree has key $K_k$ at the root, then $A[1][n]=$

  Notice that: 但我們不知道 $k$是多少，因此要掃過所有可能：

• 🌴🌴🌴 Generally, for $1\leq i\leq j\leq n$, $A[i][j]=$

For $i=1,2,\cdots, n$, $A[i][i] = p_i$ $A[i][i-1]=A[i+1][i]=0$.

Compute an optimal solution in a bottom-up fashion.