Posted by: atro February 19, 2009
Login in to Rate this Post:
0 
? 
?
Hey guys need help from you. I've seen people get help here. I am a web developer/graphic designer but I have to take this class its a requirement and i am not much of a programmer. If you give me a good pseudo code it will be fine. I understand the concept but i cannot write from the scratch. If you are going to use language then you can use C. I hope i get some help. And please dont flame this thread. Thanks.
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 city
could easily take about 25 comparisons per search. To improve this, multiway searching
uses a general tree, which is a tree data structure that can have more than two children.
In multiway searching, we store a few keys in each tree node, and the children 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 (c) the entries larger than the first two keys
but smaller than the rest, and so on. The figure below 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
6 and 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 middle branch, and for a key
larger than 10, we would take the right branch.
Write an algorithm to do a multiway search. For your answer you can assume that
each node has two arrays called Keys[3] and Links[4] and that you have a function
called Compare(keyList, searchKey) that returns a positive integer indicating the key that
matches or a negative integer indicating the link to take. (For example, Compare([2,6,10],
6) would return a value of 2 because the second key matches, and Compare([2,6,10], 7)
would return a value of −3 because 7 would be found on the third link associated with the
gap between the second and third key values.) When you have finished your algorithm,
do a wort-case and an average-case analysis, assuming that the tree is complete and each
internal node has four children. (You might want to draw a sample tree.) What would
be the impact on your two analyses if the tree was not complete or if some internal nodes
had fewer than four children?
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 city
could easily take about 25 comparisons per search. To improve this, multiway searching
uses a general tree, which is a tree data structure that can have more than two children.
In multiway searching, we store a few keys in each tree node, and the children 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 (c) the entries larger than the first two keys
but smaller than the rest, and so on. The figure below 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
6 and 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 middle branch, and for a key
larger than 10, we would take the right branch.
Write an algorithm to do a multiway search. For your answer you can assume that
each node has two arrays called Keys[3] and Links[4] and that you have a function
called Compare(keyList, searchKey) that returns a positive integer indicating the key that
matches or a negative integer indicating the link to take. (For example, Compare([2,6,10],
6) would return a value of 2 because the second key matches, and Compare([2,6,10], 7)
would return a value of −3 because 7 would be found on the third link associated with the
gap between the second and third key values.) When you have finished your algorithm,
do a wort-case and an average-case analysis, assuming that the tree is complete and each
internal node has four children. (You might want to draw a sample tree.) What would
be the impact on your two analyses if the tree was not complete or if some internal nodes
had fewer than four children?