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

Find Member Function

Program gif gives the code for the Find member function of the BST class. The Find function takes as its lone argument a const reference to an Object instance. The purpose of the routine is to search the tree for an object which matches the argument. If a match is found, Find returns a reference to the matching object. Otherwise, Find returns NullObject::Instance().

   program19396
Program: BST Class Find and FindMin Member Function Definitions

The recursive Find member function starts its search at the root and descends one level in the tree for each recursive call. At each level at most one object comparison is made (line 5). The worst case running time for a search is

displaymath64814

where tex2html_wrap_inline64816 is the time to compare two objects and n is the number of internal nodes in the tree. The same asymptotic running time applies for both successful and unsuccessful searches.

The average running time for a successful search is tex2html_wrap_inline64820, where tex2html_wrap_inline64822 is the average depth of an internal node in a binary search tree. If tex2html_wrap_inline64824, the average time of a successful search is tex2html_wrap_inline59891.

The average running time for an unsuccessful search is tex2html_wrap_inline64828, where tex2html_wrap_inline64830 is the average depth of an external node in a binary search tree. If tex2html_wrap_inline64824, the average time of an unsuccessful search is tex2html_wrap_inline59891.


next up previous contents index

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