Class Code: AMC621 Instructor: Huilan Chang
**Reference: Optimal Binary Search Trees (Section 3.5 in Foundations Of Algorithms by Neapolitan)
🔹 A binary tree is a rooted tree where each node has at most two children.
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 under this probability distribution.
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.
Let $T_n$ be the number of binary trees of $n$ nodes. Then
🔹 Recursive property