Scribd
Upload
15 views

Optimal Binary Search Tree

Optimal binary search tree

Uploaded by

Atika Hussain
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
15 views

Optimal Binary Search Tree

Optimal binary search tree

Uploaded by

Atika Hussain
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
You are on page 1/ 5
8.3 Introduction tothe Design & Analysis of Algorithms straws [1994 East-Central Regionals of the indirectly via other connected ing Contest) ‘ACM International Collegiate Progra! Optimal Binary Search Trees A binary search tree is one of the most important data structures in computer science. One of its principal applications is to implement a dictionary, a set of tlements with the operations of searching, insertion, and deletion. If probabilities of searching for elements of a set are known (e.g., from accumulated data about past searches), it is natural to pose a question about an optimal binary search tree for which the average number of comparisons in a search is the smallest possible. (Forsimplicity, we limit our discussion to minimizing the average number of comparisons in a successful search. The method can be extended to include unsuccessful searches as well.) ‘As an example, consider four keys A, B, C, and D to be searched for with probabilities 0.1, 0.2, 0.4, and 0.3, respectively. Figure 8.8 depicts two out of 1 possible binary search trees containing these keys. The average number of com- parisons in a successful search in the first of these trees is 0.1-1 + 0.2.2 +043 + 03-4 = 2.9, while for the second one it is 0.1-2 + 0.2-1 + 0.4.2 + 0.33 =21 Neither of these two trees is, in fact, optimal. (Can you tell which binary trees optimal?) € __ For our tiny example, we could find the optimal tree by generating all binary search trees with these keys. Asa general algorithm, this exhaustive-search approach is unrealistic: the total number of binary search trees with keysis equal tothe nth Catalan number y Qn\ 1 e(n) = (“”)—_ = (n) (ch forn>0, c(0)=1, which grows to infinity as fast as 4"/n'> (see Probl i is s fa lem 7 in the exercises). Jet poe it disse be distinct keys ordered from the smallest to the largest a let pi,... Pn be the probabilities of searching for them. Let C[i, j] be the smallest ae ‘number of comparisons made in a successful search in a binary search! 7 made up of keys aj,...,q;, where i,j z ane j pe level of asin 71,4 + > ps} te ea i i ay é eta 14 SD py level of a in Ths +h pl 16H te = min (Cli, k — 1] + Clk + 1,71) + Dos aig) 7 rithms Introduction to the Design & Analysis of 19! Thus, we have the recurrence min {Clik 1+ Clk + 170+ 2 Ps forlsi

You might also like