4.7.2 Interactive Exercise ``Optimal Binary Search Tree''

What you can do:

• Start the exercise by pressing the "Random keys"-button or by clearing the tree and adding keys one by one starting from an empty tree. (Enter each key and its frequency in the two editable fields left to the buttons, then press "Add/replace")

• You can add nodes, delete nodes and change the frequency of a node. (The frequency is proportional to the probability of the node.) To choose the node, either click on its index-number, key-number, or frequency in the table or enter its key-value in the editable key field.

• When you click onto an entry in the optimal cost-matrix $\mathbf{C}$, the frequency-matrix $\mathbf{F}$, or the optimal root index-matrix $\mathbf{R}$, the corresponding subtree only is shown in the optimal binary search tree, and only the arcs corresponding to this optimal binary search tree are shown in the optimal root index-matrix.

Your browser doesn't recognize the HTML's applet-tag. Please choose another browser or update to a newer version!

What you should do:

1. Enter nodes with the following keys and frequencies:
   

   key	11	25	30	44	49	60	70	77	90
   frequ.	4	18	2	3	5	6	7	9	1

2. Begin with the Frequency matrix $\mathbf{F}$: Find out, how the entries in this matrix are calculated. Start at the diagonal and work up to the upper right corner. In every step keep a part of your attention focused on the original frequency-values. Finally give a formula, how ${F}(i,j)$ is calculated and verify this formula.

3. Continue with the Optimal cost matrix $\mathbf{C}$:
   1. Verify that you get the entry $(i,j)$ in this matrix by adding the value ${F}(i,j)$ and the Optimal cost-entries belonging to the optimal subtrees (which are visible in the Optimal Binary Search Tree-window, when you click on the entry $(m,n)$ in one of the matrices). (You can highlight the cost of the optimal subtrees by clicking onto the entries in the Optimal root-matrix, where an arc ends.

   2. Justify, that the procedure described in exercise 2., if applied to ${F}(1,n)$ is equivalent to adding the frequency of the root + $n$ times the frequencies of the nodes in the n-th level, i.e. delivers the optimal cost of the given tree.

4. Now inspect the Optimal Root Index matrix $\mathbf{R}$: a bit closer.
   1. What does the entry in ${R}(1,6)$ mean? What does the entry in ${R}(3,6)$ mean?

   2. Explain, how the values in ${R}$ were constucted. At which point of the algorithm these values are stored?

   3. Explain, how you would construct the tree (i.e. the arcs in ${R}$), when the matrix $R$ is given.
      • Hint: Keep in mind, that the root of a binary tree splits it into a left and a right subtree.

      • Note that these arcs give a nice picture of the binary search tree, when you incline your head 45 degrees to the right.

5. Write down the complete algorithm in Java or in Maple.

6. And just for fun - working with the tree you entered in exercise 1:
   1. Change the frequency of key 60 from "6" to "7".

   2. Change the frequency of key 25 from ''8'' to ''18''