O'Reilly logo

Algorithms in a Nutshell by Gary Pollice, Stanley Selkow, George T. Heineman

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 the binary search tree, where each interior node in the tree has at most two child nodes. Another type of search tree, called a B-Tree, is an n-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 element e from a collection C to be stored in the search tree needs to have one or more properties that can be used as a key k; these keys determine the universe U. The elements must also have properties that distinguish them from other elements in the set. The search tree will store the elements from C.

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required