Árbol binario de búsqueda (ABB).

   Un árbol binario es una estructura de datos sumamente útil en muchos aspectos, en particular, cuando deben tomarse decisiones en dos sentidos en cada punto de un proceso determinado.

   Con base en lo anterior, suponga que por alguna razón se desea encontrar todos los duplicados de una secuencia de números. Para ello, considere lo siguiente:

1. El primer número de la secuencia se coloca en un nodo que se ha establecido como la raíz de un árbol binario, cuyos subárboles izquierdo y derecho estarán inicialmente vacíos.
2. Cada número sucesivo en la secuencia se compara con el número que se encuentra en la raíz del árbol binario. En este momento, se tienen tres casos a considerar:
1. Si coincide, se tiene un duplicado.
2. Si es menor, se examina el subárbol izquierdo.
3. Si es mayor, se examina el subárbol derecho.
3. Si alguno de los subárboles esta vacío, el número no es un duplicado y se coloca en un nodo nuevo en dicha posición del árbol binario.
4. Si el subárbol correspondiente no está vacío, se compara el número con la raíz del subárbol en cuestión, y se repite todo el proceso nuevamente con dicho subárbol.

   Un árbol binario de búsqueda (ABB) es un árbol binario que no tiene valores duplicados en los nodos, y además, tiene las siguientes características:

1. Los valores en cualquier subárbol izquierdo son menores que el valor en su nodo padre.
2. Los valores en cualquier subárbol derecho son mayores que el valor en su nodo padre.

   Tome en cuenta que un ABB es un árbol binario, pero un árbol binario no es necesariamente un ABB. En este sentido, todo lo que se ha dicho y definido para árboles binarios, es aplicable también a los árboles binarios de búsqueda.

Operaciones primitivas.

   Respecto a las operaciones primitivas, se definen cuatro operaciones primitivas para un ABB:

• inserta: inserta un nuevo nodo al árbol binario de búsqueda. La inserción se realiza de manera ordenada respecto del elemento a insertar, por lo que debe existir una relación de orden definida para el conjunto de datos al que pertenece dicho elemento.

   En resumen, la operación inserta de manera ordenada a elemento en el ABB cuando el objeto abb recibe el mensaje correspondiente, es decir: abb.inserta(elemento).

• recorre en preorden: recorre el ABB no vacío en orden previo, de tal forma que cuando el objeto abb recibe el mensaje: abb.recorrePreorden( ) se imprime en la salida estándar el recorrido en orden previo de abb.

• recorrido en orden: recorre el árbol binario de búsqueda no vacío en orden, de tal forma que cuando el objeto abb recibe el mensaje: abb.recorreEnorden( ) se imprime en la salida estándar el recorrido en orden de abb.

   Note cómo un recorrido en orden, como su nombre lo indica, imprime en la salida estándar los elementos almacenados en el árbol ordenados de manera ascendente.

• recorrido en postorden: recorre el ABB no vacío en orden posterior, de tal forma que cuando el objeto abb recibe el mensaje: abb.recorrePostorden( ) se imprime en la salida estándar el recorrido en orden posterior de abb.

   Para el caso de un árbol binario de búsqueda, también serían deseables otras operaciones, como aquellas que se definieron para los árboles binarios: primitivas, operaciones adicionales que podrían ser útiles y recorridos inversos por ejemplo (vea las entradas Árboles binarios (operaciones primitivas) y Árboles binarios (recorridos)).

   En este sentido, es importante resaltar que siempre que una operación no viole la relación de orden intrínseca a los ABB, es factible de ser implementada y que la decisión final respecto a su implementación estará en directa función de si ésta tiene o no sentido en la aplicación que se esté desarrollando.