Δένδρα αναζήτησης

Διατεταγμένο είναι ένα δένδρο στο οποίο η διάταξη των κόμβων έχει σημασία
Σε ένα δυαδικό δένδρο αναζήτησης η τιμή κάθε κόμβου είναι μεγαλύτερη ή ίση από τις τιμές των κόμβων του αριστερού υποδένδρου και μικρότερη ή ίση από τις τιμές των κόμβων του δεξιού υποδένδρου.
Σε ένα τέτοιο δένδρο η αναζήτηση για μια τιμή απαιτεί τόσες συγκρίσεις όσο είναι και το μέγιστο μήκος μονοπατιού.

Παράδειγμα αναζήτησης

/*
 * Search for the integer i in the ordered binary tree t
 * If found return its node; otherwise return NULL
 */
struct s_tree
search(struct s_tree *t, int i)
{
	if (t == NULL)
		return (NULL);
	else if (t->val == i)
		return (t);
	else if (i < t->val)
		return (search(t->left, i));
	else
		return (search(t->right, i));
}