Suppose we are designing a program to translate text from English to French. For each

occurrence of each English word in the text, we need to look up its French equivalent. We

could perform these lookup operations by building a binary search tree $($BST$)$

with n English words as keys and their French equivalents as satellite data. Moreover,

some words in the text might have no French translation. Because we will search the tree

for each individual word in the text, we want the total time spent searching to be as low as

possible. We could ensure $0($log$2$n$)$ search time per occurrence by using balanced BSTs

such as AVL, red$-$black trees etc. However, words appear with different frequencies in the

text, and a frequently used word may appear far from the root, while a rarely used word

appears near the root in balanced BSTs$.$ Such an organization would slow down the

translation, since the number of nodes visited when searching for a key in a BST depends

on the depth of the node containing the key. We want words that occur frequently in the

text to be placed nearer the root.

$($a$)$ Design an efficient algorithm to minimize the number of nodes traversed in all

searches in BST$,$ given that we know how often each word occurs in a BST$.$ What is

the time complexity of your algorithm?

$($b$)$ Given a set of $4$ English words $\{$Algorithm$,$ Coding, Happy, Job offer$),$ corresponding $(8)$

French equivalent as $\{$Algorithme$,$ Codage, Heureuse, Offre d'emploi$\},$ frequency of

successful searches are $(1,4,2,1)$ and frequency of unsuccessful searches are $(4,2,$

$4,1,1).$ Apply your algorithm to determine the optimal cost of searching and structure of BST$.$