Analysis of algorithms 3. When the collection of data is large, a large number o

Question

Analysis of algorithms 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

Explanation / Answer

boolean search(Node n,int x)
   // Node n is null
   if (n == null) return false;
   int res = compare(n.keys,x);
   // id res is negative, search recursively in the corresponding Link
   if (res < 0)
       search(n.Links[-1*res],x);
   // if res is not negative, we have find x succesfully in the Link
   return true;
end

Best Case :-
   if Node containing the value we are searching is at level 0, then we need to search the keys of that level.
   therefore O(compare) => O(length(Node.keys))

Worst Case :-
   if Node containing the value we are searching is at deepest level, O(log n);
   n is number of Node in the Tree

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.