Algorithms in a Nutshell

Binary Tree Search | 129

Searching

givenjust its key value,key(e). If the original collectionCcontained two identical

elements, then only one of them would be properly stored by the hash tableA.*

Binary Tree Search

Binary searching on an array in memory is efficient, as we have already seen.

However, the effectiveness of searching on arrays is reduced greatly when the

underlying data in the search set changes frequently. With a dynamic search set,

one must adopt a different data structure in order to maintain acceptable search

performance.

Search trees are the most common data structure used to store dynamic search

sets. Search trees perform well in memory and when stored on secondary storage.

The most common type of search tree is thebinary search tree, where each inte-

rior node in the tree has at most two child nodes. Another type of search tree,

called aB-Tree, is ann-ary tree designed to be easily stored on disk.

Input/Output

The input and output to algorithms using search trees is the same as for BINARY

SEARCH. Each elementefrom a collectionCto be stored in the search tree needs

to have one or more properties that can be used as a keyk; these keys determine

the universeU. The elements must also have properties that distinguish them

from other elements in the set. The search tree will store the elements fromC.

Context

Memory leaks are serious problems for programmers. When a program will run

for an extended period, such as many of the server applications used in today’s

systems, memory leaks will eventually cause the program to exceed the amount of

memory allocated to its process and then crash, often with disastrous

consequences.

One might write a program to monitor memory allocations and deallocations and

report on a program’s memory profile in order to detect the presence of memory

leaks. Such a memory profiler can be written quite simply by writing new

malloc()andfree() functions that record the appropriate information before allo-

cating and freeing memory. We want to record every memory allocation and

when that memory is freed, we must remove it from the set of active allocations.

In the context described, we have noa prioriknowledge of how many elements

we need to store. A hash-based search would work, but we may select a hash table

size that is much too small for effective resource usage. An alternate search

strategy is to use a search tree. When we plan on maintaining our search data set

in memory, we typically use abinarysearchtree. Binary search trees perform well

with dynamic data where insertions and deletions are frequent.

* GPERF for C and C++ can be downloaded fromhttp://www.gnu.org/software/gperf/, and JPERF

for Java can be downloaded fromhttp://www.anarres.org/projects/jperf/.

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