Algorithms in a Nutshell

Binary Tree Search | 135

Searching

Consequences

Red-black trees—as well as other balanced binary trees—require more code to

implement than simple binary search trees. The tradeoff is usually worth it in

terms of runtime performance gains. Red-black trees have two storage require-

ments as far as the data structures used for nodes:

• Each node requires space to store the node’s color. This is a minimum of one
  bit, but in practice, most implementations use at least a byte.


• Every node must have a parent link, which is not a requirement for a binary
  search tree.
  Red-black trees also require a node with a null value at the root. One can imple-
  ment this using a single null-valued node and make all leaf pointers point to it.

Analysis

The average-case performance of search in a red-black tree is the same as a

BINARYSEARCH, that is O(logn). However, now insertions and deletions can be

performed in O(logn) time as well.

Variations

There are other balanced tree structures. The most common one is the AVL tree,

mentioned previously. Red-black trees and other balanced binary trees are fine

choices for in-memory searching. When the data set becomes too large to be kept

in memory, another type of tree is typically used: then-way tree, where each node

hasn>2 children. A common version of such trees is called theB-tree, which

performs very well in minimizing the number of disk accesses to find a particular

item in large data sets. B-trees are commonly used when implementing relational

databases.

References

Adel’son-Vel’skii, G. M., and E. M. Landis, “An algorithm for the organization of

information,”Soviet Mathematics Doklady, 3:1259–1263, 1962.

Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein,

Introduction to Algorithms, Second Edition. McGraw-Hill, 2001.

Hester, J.H. and D.S. Hirschberg, “Self-Organizing Linear Search,” ACM

Computing Surveys, 17 (3): 295–312, 1985.

Knuth, Donald,The Art of Computer Programming, Volume 3: Sorting and

Searching, Third Edition. Addison-Wesley, 1997.

Schmidt, Douglas C., “GPERF: A Perfect Hash Function Generator,” Proceedings

of the Second C++ Conference”: 87–102, 1990. Available athttp://citeseerx.ist.

psu/viewdoc/summary?doi=10.1.1.44.8511, accessed May 10, 2008.

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