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