search tree

A search tree is a tree where every subtree of a node has keys less than any other subtree of the node to its right. The keys in a node are conceptually between subtrees and are greater than any keys in subtrees to its left and less than any keys in subtrees to its right.

A search might visit nodes in the tree to locate some information. At the outset of the search one has a given key and seeks to find the node in the tree having that key. As the nodes are visited a comparison of the node’s key to the given key is made and a decision to go to either the left subtree or the right subtree is made. Knowing that all keys to the left (right) are smaller (larger) makes the search easy to carry out.

Title search tree
Canonical name SearchTree
Date of creation 2013-03-22 17:22:02
Last modified on 2013-03-22 17:22:02
Owner Mathprof (13753)
Last modified by Mathprof (13753)
Numerical id 5
Author Mathprof (13753)
Entry type Definition
Classification msc 68P10
Classification msc 68P05