Search tree - AbsoluteAstronomy.com

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, a search tree is a binary tree

Binary tree

In computer science, a binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to...

data structure

Data structure

In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...

in whose nodes data values are stored from some ordered set

Ordered set

In order theory in mathematics, a set with a binary relation R on its elements that is reflexive , antisymmetric and transitive is described as a partially ordered set or poset...

, in such a way that in-order traversal of the tree visits the nodes in ascending order of the stored values. This means that for any internal node containing a value , the values stored in its left subtree satisfy , and the values stored in its right subtree satisfy . Each subtree of a search tree is by itself again a search tree.

Search trees can implement the data type

Data type

In computer programming, a data type is a classification identifying one of various types of data, such as floating-point, integer, or Boolean, that determines the possible values for that type; the operations that can be done on values of that type; the meaning of the data; and the way values of...

of (finite) multiset

Multiset

In mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once...

s. The advantage of using search trees is that the test for membership can be performed efficiently provided that the tree is reasonably balanced, that is, the leaves of the tree are at comparable depths. Various search-tree data structures exist, several of which also allow efficient insertion and deletion of elements, which operations then have to maintain tree balance. If the multiset being represented is immutable, this is not an issue.

Search trees can also implement associative array

Associative array

In computer science, an associative array is an abstract data type composed of a collection of pairs, such that each possible key appears at most once in the collection....

s by storing key–value pairs, where the ordering is based on the key part of these pairs.

In some kinds of search trees the data values are all stored in the leaves of the tree. In that case some additional information needs to be stored in the internal tree nodes to make efficient operations possible.

Examples

Some examples of search-tree data structures are:

AVL tree
AVL tree
In computer science, an AVL tree is a self-balancing binary search tree, and it was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. Lookup, insertion, and deletion all take O time in both the average and worst...

s, Red-black tree
Red-black tree
A red–black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer and named "symmetric binary B-tree," but acquired its modern name in a paper in 1978 by...

s, splay tree
Splay tree
A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O amortized time. For many sequences of nonrandom operations, splay trees perform...

s and Tango Trees
Tango Trees
A Tango tree is an online binary search tree that is O-competitive proposed by Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Patrascu in 2004.-Overview:...

which are instances of self-balancing binary search tree
Self-balancing binary search tree
In computer science, a self-balancing binary search tree is any node based binary search tree that automatically keeps its height small in the face of arbitrary item insertions and deletions....

s;
Ternary search tree
Ternary search tree
In computer science, a ternary search tree is a special trie data structure where the child nodes of a standard trie are ordered as a binary search tree. Searching for a string in a ternary search tree consists of a series of binary searches, one for each character in the string...

s, in which each internal node has exactly three children;
B trees, commonly used in databases;
B+ tree
B+ tree
In computer science, a B+ tree or B plus tree is a type of tree which represents sorted data in a way that allows for efficient insertion, retrieval and removal of records, each of which is identified by a key. It is a dynamic, multilevel index, with maximum and minimum bounds on the number of...

s, like B trees but with all data values stored in the leaves;
van Emde Boas tree
Van Emde Boas tree
A van Emde Boas tree , also known as a vEB tree, is a tree data structure which implements an associative array with m-bit integer keys. It performs all operations in O time...

s, very efficient if the data values are fixed-size integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

s.

Examples

See also