Search Tree

In computer science, a search tree is a binary tree data structure in whose nodes data values are stored from some ordered set, 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 v, the values x stored in its left subtree satisfy xv, and the values y stored in its right subtree satisfy vy. Each subtree of a search tree is by itself again a search tree.

Search trees can implement the data type of (finite) multisets. 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 arrays 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.

Read more about Search Tree:  Examples

Other articles related to "search tree, search, tree, trees, search trees":

Backtracking - Description of The Method - Usage Considerations
... false for every ancestor t of c in the search tree ... algorithm will still find all solutions, but it will be equivalent to a brute-force search ... It may assume that the partial candidate c and all its ancestors in the tree have passed the reject test ...
Self-balancing Binary Search Tree
... In computer science, a self-balancing (or height-balanced) binary search tree is any node-based binary search tree that automatically keeps its height (n ...
Search Tree - Examples
... Some examples of search-tree data structures are AVL trees, Red-black trees, splay trees and Tango Trees which are instances of self-balancing binary search trees Ternary search trees ...
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 ... For many sequences of nonrandom operations, splay trees perform better than other search trees, even when the specific pattern of the sequence is unknown ... The splay tree was invented by Daniel Dominic Sleator and Robert Endre Tarjan in 1985 ...
List Of Graph Theory Topics - Trees
... Tree Abstract syntax tree B-tree Binary tree Binary search tree Self-balancing binary search tree AVL tree Red-black tree Splay tree T-tree Binary space ...

Famous quotes containing the words tree and/or search:

    It never had been inside the room,
    And only one of the two
    Was afraid in an oft-repeated dream
    Of what the tree might do.
    Robert Frost (1874–1963)

    Still, I search in these woods and find nothing worse
    than myself, caught between the grapes and the thorns.
    Anne Sexton (1928–1974)