A search tree is a data structure used in computer programming to contain and organize a list of data. Each search tree is comprised of an ordered set of nodes. These nodes can be connected to zero or more other nodes. The individual nodes contain some data as well as links to any other nodes. The data that is contained in the nodes of the tree is very often ordered in some way to allow efficient algorithms to search for, insert and remove nodes with ease.
The nodes of a search tree are described with four important terms. The top of a tree, where the first node is located, is called the root. If a node contains links to sub-nodes, that node is known as a parent. Nodes that are beneath the parent are called children, and any node that has no child nodes is called a leaf. So, a root node is identified because it does not have a parent, and leaf nodes will have no children.
A program is able to move through a tree searching for data by starting at a particular node, performing a conditional check and then moving to the next logical node if the required data is not present. Depending on the data structure used, this search can take a variable amount of time. If the search tree is organized during the process of adding and removing nodes, the search can be very fast. When a tree is assembled randomly, is unsorted or allows multiple parents, the search can take a very long time.
One factor that affects the use of search trees is the issue of balance. A balanced tree is one in which both the right and left children of the root node contain either the same depth of child nodes or are within a one-node count of each other. The depth of a tree is the number of nodes from the lowest leaf of a tree to the root. An unbalanced tree could have all of the nodes on only one side or have all of the nodes arranged in a linear fashion with no branches. When the depth of a tree increases, the speed of search algorithms can decrease dramatically.
There are certain types of search trees that are described as self-balancing. These trees use operations such as tree rotation to help maintain balance while preserving the order of the data in the leaves. Although performing tree rotations might slow down a program when adding and removing nodes, this is countered by the speed at which data can be retrieved.
Although there are many types of search trees, the most common tree data structure is a binary search tree. This data type consists of nodes that each have zero to two child nodes. There is only one root node, and all of the leaves in the tree are ordered from left to right in ascending values according to the data they hold. Many algorithms exist for binary search trees that can make ordering data very easy.
There is no single standard implementation for search tree nodes. The nodes can be represented by a wide variety of data structures. Arrays of arrays can be used, as could multiply linked lists. Often, a search tree uses a custom data structure that is designed to aid in the completion of the necessary operations called for by the program. Some standard programming libraries even include their own internal implementations of search trees.
