FIND

The key algorithm in a search tree is the "find" operation. It is the operation which determines whether a particular key is stored in the structure--it returns a pointer to the data associated with that key.

The other operations of interest are "insert" and "delete", but generally search trees are used in situations where the number of "find"s greatly outweighs the number of the other operations.

Here's the basic outline of the find:

  if its an interior node:
     
     compare the key (being sought) with the key in the node
         (if there's no key left, go to last child)
        --less than?  go to the child "before" this key
	--equal to?   go to the next child
	--greater than? move to next key in node & repeat

  if its a leaf:
      compare the key (being sought) with the key in the leaf
         (if there's no key left, return unsuccessful)
        --less than?  return unsuccessful
	--equal to?   return success (and a pointer)
	--greater than?  move to next key in leaf & repeat

NEXT BACK