Plz , Analysis of algorithms Q

3. When the collection of data is large, a large number of comparisons may still be needed to do a binary search. For example, a telephone directory of a large ity could easily take about 25 comparisons per search. To improve this, multi- way searching uses a general tree, which is a tree data structure that can have more than two children. In muliway searching, we store a few keys in each than two children. In multiway searching, we store few keys in each subtrees containing (a) the entries tree node, and the children represent the and the chidren represent the subtrees containing (a) the entries smaller than all the keys, (b) the entries larger than the first key but smaller than the rest, (e) the entries larger than the first two keys but smaller than the rest, and so on. The following figure shows an example of a general tree that can be used for multiway searching. In the root of this tree we have the keys of d 10, so if we are looking for a key less than 6, we would take the left branch. If we are looking for a key between 6 and 10, we would take the mid- 6 an dle branch, and for a key larger than 10, we would take the right branch. 6110 214 12114116 13) (5 79 11 13 (15 17