Algorithms in a Nutshell

(^130) | Chapter 5: Searching
A binary search tree,T, is a finite set of nodes that are identified by an ordered
property, or key. The set of nodes may be empty, or it might contain a root node
nr. Each nodenrefers to two binary search trees,Tl, andTr, and obeys the prop-
erty that ifkis the key for noden, then all keys inTlare≤kand all the keys inTr
are≥k. This property is called thebinary-search-tree property(Cormen et al.,
2001). Figure 5-8 shows a small example of a binary tree. Each node has an
integer key that identifies the node. You can see that finding a key in the tree in
Figure 5-8 requires examining at most three nodes, starting with the root node.
The tree is perfectly balanced. That is, each node that has any children has exactly
two children. A perfectly balanced binary tree has 2n–1 nodes for somen≥1 and a
height of n–1.
Trees may not always be balanced. In the worst case, a tree may be degenerate and
have the basic properties of a list. Consider the same nodes for Figure 5-8 arranged
in the way shown in Figure 5-9. Here the nodes were added in ascending order
and—although the structure fits the strict definition of a binary tree, with the left
subtree of each node being an empty tree—the structure is effectively a list.
Forces
If we simply need to locate a search item, the first choice should be a hash-based
solution. Some factors that might alter our decision to use a binary search tree are:

• The data set size is unknown, and the implementation must be able to han-
  dle any possible size that will fit in memory.


• The data set is highly dynamic, and there will be many insertions and dele-
  tions during the data structure’s lifetime.


• The application requires traversing the data in ascending or descending
  order.
  Once we decide to use a search tree, we must make the following decisions about
  the tree’s details:


• If we need to be able to traverse the data set in order starting at any specific
  node, the appropriate pointers to parent nodes must be included in the node
  structure.


• If the data is dynamic, we must balance the tree.

Figure 5-8. A simple binary search tree

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use