Algorithms in a Nutshell

Binary Tree Search | 131

Searching

In most applications we need to balance the tree to avoid askewed tree, where

there are a few branches that are much longer or shorter than the other

branches—or in the worst case a degenerate tree, as in Figure 5-9. Two popular

types of balanced trees can be used for binary search. One is the AVL tree,

proposed by Adel’son-Vel’skii and Landis in 1962. An AVL tree obeys the

followingbalancingproperty: no node has subtrees that differ in height by more

than 1.

A more recent type of balanced binary tree is called ared-black tree. Red-black

trees are approximately balanced. Using a red-black tree guarantees that no

branch has a height more than two times that of any other. A red-black tree satis-

fies the following conditions (Cormen et al., 2001):

• Every node is labeled either red or black.


• The root is black.


• Every leaf node contains a null value and is black.


• All red nodes have two black children.


• Every simple path from a node to one of its descendant leaf nodes contains
  the same number of black nodes.
  In the diagrams that follow, we have not shown the null value leaf nodes in the
  interest of space. When you look at the diagrams, you should imagine that each
  leaf node in the diagram actually has two black children, and that these have null
  values.
  Figure 5-10 shows a valid red-black tree containing seven different integers
  inserted in the following order: 13, 26, 43, 17, 25, 15, and 16.

Figure 5-9. A degenerate 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