Search tree

<h2 id="types-of-trees">Types of trees</h2>

<h3>Binary search tree</h3>
<p class="note">Main article: <a href="/facts/Binary_search_tree/gWubNt7b">Binary search tree</a></p>
<p>A Binary Search Tree is a node-based data structure where each node contains a key and two subtrees, the left and right. For all nodes, the left subtree's key must be less than the node's key, and the right subtree's key must be greater than the node's key. These subtrees must all qualify as binary search trees.
</p><p>The worst-case <a href="/facts/Time_complexity/77T62gmf">time complexity</a> for searching a binary search tree is the <a href="/facts/Tree_(data_structure)/RcXz9noF">height of the tree</a>, which can be as small as O(log n) for a tree with n elements.
</p>
<h3>B-tree</h3>
<p class="note">Main article: <a href="/facts/B-tree/IHE2l8GR">B-tree</a></p>
<p>B-trees are generalizations of binary search trees in that they can have a variable number of subtrees at each node. While child-nodes have a pre-defined range, they will not necessarily be filled with data, meaning B-trees can potentially waste some space. The advantage is that B-trees do not need to be re-balanced as frequently as other <a href="/facts/Self-balancing_binary_search_tree/W7WAsES0">self-balancing trees</a>.
</p><p>Due to the variable range of their node length, B-trees are optimized for systems that read large blocks of data, they are also commonly used in databases.
</p><p>The time complexity for searching a B-tree is O(log n).
</p>
<h3>(a,b)-tree</h3>
<p class="note">Main article: <a href="/facts/(a,b)-tree/lLon4yTJ">(a,b)-tree</a></p>
<p>An (a,b)-tree is a search tree where all of its leaves are the same depth. Each node has at least a children and at most b children, while the root has at least 2 children and at most b children.
</p><p>a and b can be decided with the following formula:<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
</p><p>
  
    
      
        2
        ≤
        a
        ≤
        
          
            
              (
              b
              +
              1
              )
            
            2
          
        
      
    
    {\displaystyle 2\leq a\leq {\frac {(b+1)}{2}}}

</p><p>The time complexity for searching an (a,b)-tree is O(log n).
</p>
<h3>Ternary search tree</h3>
<p class="note">Main article: <a href="/facts/Ternary_search_tree/kzzw6q3f">Ternary search tree</a></p>
<p>A ternary search tree is a type of <a href="/facts/Tree_(data_structure)/RcXz9noF">tree</a> that can have 3 nodes: a low child, an equal child, and a high child. Each node stores a single character and the tree itself is ordered the same way a binary search tree is, with the exception of a possible third node.
</p><p>Searching a ternary search tree involves passing in a <a href="/facts/String_(computer_science)/4ChJu5WS">string</a> to test whether any path contains it.
</p><p>The time complexity for searching a balanced ternary search tree is O(log n).
</p>
<h2 id="searching-algorithms">Searching algorithms</h2>
<h3>Searching for a specific key</h3>
<p>Assuming the tree is ordered, we can take a key and attempt to locate it within the tree. The following algorithms are generalized for binary search trees, but the same idea can be applied to trees of other formats.
</p>
<h4>Recursive</h4>
search-recursive(key, node)
    if node is <i>NULL</i>
        return <i>EMPTY_TREE</i>
    if key < node.key
        return search-recursive(key, node.left)
    else if key > node.key
        return search-recursive(key, node.right)
    else
        return node

<h4>Iterative</h4>
searchIterative(key, node)
    currentNode := node
    while currentNode is not <i>NULL</i>
        if currentNode.key = key
            return currentNode
        else if currentNode.key > key
            currentNode := currentNode.left
        else
            currentNode := currentNode.right

<h3>Searching for min and max</h3>
<p>In a sorted tree, the minimum is located at the node farthest left, while the maximum is located at the node farthest right.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p>
<h4>Minimum</h4>
findMinimum(node)
    if node is <i>NULL</i>
        return <i>EMPTY_TREE</i>
    min := node
    while min.left is not <i>NULL</i>
        min := min.left
    return min.key

<h4>Maximum</h4>
findMaximum(node)
    if node is <i>NULL</i>
        return <i>EMPTY_TREE</i>
    max := node
    while max.right is not <i>NULL</i>
        max := max.right
    return max.key

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Trie/cXNr0ScT">Trie</a></li>
<li><a href="/facts/Binary_tree/TDV7GMpu">Binary tree</a></li>
<li><a href="/facts/Depth-first_search/luxJKVph">Depth-first search</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Black, Paul and Pieterse, Vreda (2005). "search tree". Dictionary of Algorithms and Data Structures <a href="https://xlinux.nist.gov/dads/HTML/searchtree.html" target="_blank">https://xlinux.nist.gov/dads/HTML/searchtree.html</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Toal, Ray. "(a,b) Trees" <a href="http://cs.lmu.edu/~ray/notes/abtrees/" target="_blank">http://cs.lmu.edu/~ray/notes/abtrees/</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Gildea, Dan (2004). "Binary Search Tree" <a href="http://www.cs.rochester.edu/~gildea/csc282/slides/C12-bst.pdf" target="_blank">http://www.cs.rochester.edu/~gildea/csc282/slides/C12-bst.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Search tree open-in-new

Search tree