CLICK ON THIS IMAGE

Optimal Binary Search Trees

A binary search tree is a tree with data (keys) at internal nodes with the following property :

For a given set of keys (and ordering) we can find many possible binary search trees.
To search for a given key in a tree, we can use the following useful search technique:
     datatype INTREE = EMPTY
| Node of (INTREE * int * INTREE)
fun IsInTree (k,Empty) = false
| IsInTree (k,Node(left,entry,right)) =
(k=entry) orelse
if (k<entry) then
IsInTree (k,left)
else (* k>entry *)
IsInTree (k,right)
How many comparisons does this give per key ?

For first tree : A-2 B-3 C-1 D-3 E-2 F-4 G-3 H-4
For second tree : A-4 B-3 C-2 D-3 E-1 F-3 G-2 H-3
For third tree : A-8 B-7 C-6 D-5 E-4 F-3 G-2 H-1

If all keys are equally possible, then the average number of comparisons is :

For the first tree : (2+3+1+3+2+4+3+4) / 8 = 22 / 8
For the second tree : (4+3+2+3+1+3+2+3) / 8 = 21 / 8
For the third tree : (8+7+6+5+4+3+2+1) / 8 = 36 / 8

In practice it is often the case that keys are not equally probable.
More
explanation

Even more
explanation

And even
more

Applet to calculate Optimal Binary Tree from notes: