Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Linear Search

Program gif gives the naıve version of the Find method of the MWayTree class. The Find method takes a ComparableObject and locates the item in the search tree which matches the given object.

   program20860
Program: MWayTree class Find method (linear search).

Consider the execution of the Find method for a node T of a an M-way search tree. Suppose the object of the search is x. Clearly, the search fails when tex2html_wrap_inline62773 (lines 10-11). In this case, null is returned.

Suppose tex2html_wrap_inline64585. The linear search on lines 13-20 considers the keys tex2html_wrap_inline63513, tex2html_wrap_inline64589, tex2html_wrap_inline64591, ..., tex2html_wrap_inline63509, in that order. If a match is found, the matching object is returned immediately (lines 16-17).

Otherwise, when the main loop terminates there are three possibilities: i=0 and tex2html_wrap_inline64597; tex2html_wrap_inline64599 and tex2html_wrap_inline63589; or i=n-1 and tex2html_wrap_inline64605. In all three cases, the appropriate subtree in which to continue search is tex2html_wrap_inline62605 (line 21).

Clearly the running time of Program gif is determined by the main loop. In the worst case, the loop is executed M-1 times. Therefore, at each node in the search path at most M-1 object comparisons are done.

Consider an unsuccessful search in an M-way search tree. The running time of the Find method is

displaymath64575

in the worst case, where h is the height of the tree and tex2html_wrap_inline63301 is the time required to compare two objects. Clearly, the time for a successful search has the same asymptotic bound. If the tree is balanced and tex2html_wrap_inline63929, then the running time of Program gif is tex2html_wrap_inline64621, where K is the number of keys in the tree.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.