Editing Search tree (section)

{{Short description|Data structure in tree form sorted for fast lookup}}
{{Distinguish|tree search}}

In [[computer science]], a '''search tree''' is a [[Tree (data structure)|tree data structure]] used for locating specific keys from within a set. In order for a tree to function as a search tree, the key for each node must be greater than any keys in subtrees on the left, and less than any keys in subtrees on the right.<ref>Black, Paul and Pieterse, Vreda (2005). [https://xlinux.nist.gov/dads/HTML/searchtree.html "search tree"]. [http://xlinux.nist.gov/dads// Dictionary of Algorithms and Data Structures]</ref>

The advantage of search trees is their efficient search time given the tree is reasonably balanced, which is to say the [[Tree data structure#Terminologies used in Trees|leaves]] at either end are of 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.

Search trees are often used to implement an [[associative array]]. The search tree algorithm uses the key from the [[attribute–value pair|key–value pair]] to find a location, and then the application stores the entire key–value pair at that particular location.