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

Get Algorithms in a Nutshell now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.