Optimal binary search tree

Application: We could perform translating text from English to French with n English words as keys and their French equivalents as satellite data  by building binary search tree.

Goal: How to organize a binary search tree so as to minimize the number of nodes visited in all searches.

The feature of optimal binary search tree:
1. the overall height is not necessarily smallest
2. greatest search probability of any key isn't put at the root

solve dynamic programming:

step1: The structure of an optimal binary search tree
 
1. if an optimal binary search tree T has a subtree T', then T' must be optimal as well
2. select kr (i <= r <= j) as the root, the left subtree contains the keys ki, ..., kr-1 (and dummy keys di-1, ..., dr-1) and
3.

step 2: A recursive solution