Supongamos que K1 < K2< ... < Kn. Dado un objeto x, nuestro problema es buscar las claves y determinar si x es igual a una de las claves o si x esta entre las claves Ki y Ki+1 para algún i. Primero señalemos que la búsqueda tiene 2n + 1 posibles resultados, es decir, x es menor que K1, x es igual a K1, x es mayor que K1 pero menor que K2, x es igual a K2, etc.
Un procedimiento de búsqueda consiste en una serie de comparaciones entre x y las claves donde cada comparación de x con una clave nos indica si x es igual, menor que, o mayor que tal clave.
Definición:
Definimos un árbol de búsqueda para las claves K1,
K2, ..., Kn como un árbol
binario con n nodos rama y n + 1 hojas. Los nodos rama son etiquetados
con K1, K2, ..., Kn
y las hojas son etiquetados K0, K1, K2,
..., Kn; de manera que para el nodo rama con la etiqueta
Ki, su subárbol izquierdo contiene sólo
los vértices con las etiqueta Kj, j <
i y su subárbol derecho contiene sólo vértices con
etiquetas Kj, j 
i.
Ejemplo:
Sea el siguiente árbol:
De inmediato se ve que un árbol de búsqueda corresponde un procedimiento
de búsqueda; al comenzar con la raíz del árbol de búsqueda,
compramos un objeto dado x con la etiqueta de la raíz K1.
Si x es igual a Ki, la búsqueda ha terminado.
Si x es menor que Ki, comparamos x con
el hijo izquierdo, si x es mayor que Ki con
el hijo derecho de la raíz. Dicha comparación se continúa
para los nodos rama sucesivamente hasta que x concuerda con una clave
o se alcance una hoja. Es evidente que si una hoja etiquetada con Kj
es alcanzada, esto significa que x es mayor que la clave Kj
pero menor que la clave Kj+1. Si se alcanza Kn
significa que x es mayor que Kn.
Ejemplo:
Sean AB, CF, EG, PP las claves K1, K2, K3,
K4 en un árbol de búsqueda. Dado el objeto BB,
los pasos de búsqueda son :
1.- Comparar BB con K3 la cual es EG
2.- Como BB es menor que EG, comparemos BB con K1, la cual
es AB
3.- Como BB es mayor que AB, comparemos BB con K2 ,la cual
es CF
4.- Como BB con es menor que CF, se alcanza la hoja K1
Así concluimos que el objeto BB es mayor que AB y menor que CF.