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

Searching a Binary Tree

The search method described above applies directly to binary search trees. As above, the search begins at the root node of the tree. If the object of the search, x, matches the root r, the search terminates successfully. If it does not, then if x is less than r, the left subtree is searched; otherwise x must be greater than r, in which case the right subtree is searched.

Figure gif shows two binary search trees. The tree tex2html_wrap_inline62302 is an example of a particularly bad search tree because it is not really very tree-like at all. In fact, it is topologically isomorphic with a linear, linked list. In the worst case, a tree which contains n items has height O(n). Therefore, in the worst case an unsuccessful search must visit O(n) internal nodes.

   figure18039
Figure: Examples of search trees.

On the other hand, tree tex2html_wrap_inline62304 in Figure gif is an example of a particularly good binary search tree. This tree is an instance of a perfect binary tree .

Definition (Perfect Binary Tree)  A perfect binary tree of height tex2html_wrap_inline62578 is a binary tree tex2html_wrap_inline62666 with the following properties:
  1. If h=0, then tex2html_wrap_inline63362 and tex2html_wrap_inline63364.
  2. Otherwise, h>0, in which case both tex2html_wrap_inline62662 and tex2html_wrap_inline62664 are both perfect binary trees of height h-1.

It is fairly easy to show that a perfect binary tree of height h has exactly tex2html_wrap_inline62690 internal nodes. Conversely, the height of a perfect binary tree with n internal nodes is tex2html_wrap_inline63380. If we have a search tree that has the shape of a perfect binary tree, then every unsuccessful search visits exactly h+1 internal nodes, where tex2html_wrap_inline63384. Thus, the worst case for unsuccessful search in a perfect tree is tex2html_wrap_inline58840.


next up previous contents index

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