Un árbol binario de búsqueda (ABB) es un árbol binario con la propiedad de que todos los elementos almacenados en el subárbol izquierdo de cualquier nodo x son menores que el elemento almacenado en x ,y todos los elementos almacenados en el subárbol derecho de x son mayores que el elemento almacenado en x. – Una interesante propiedad es que si se listan los nodos del ABB en inorden nos da la lista de nodos ordenada. Esta propiedad define un método de ordenación similar al Quicksort, con el nodo raíz jugando un papel similar al del elemento de partición del Quicksort aunque con los ABB hay un gasto extra de memoria mayor debido a los punteros.

La propiedad de ABB hace que sea muy simple diseñar un procedimiento para realizar la búsqueda.

Para cada nodo de un árbol binario de búsqueda debe cumplirse la propiedad:
Las claves de los nodos del subárbol izquierdo deben ser menores que la clave de la raíz.
Las claves de los nodos del subárbol derecho deben ser mayores que la clave de la raíz.

Esta definición no acepta elementos con claves duplicadas.
Se indican en el diagrama de la figura anterior, el descendiente del subárbol izquierdo con mayor clave y el descendiente del subárbol derecho con menor valor de clave; los cuales son el antecesor y sucesor de la raíz.

El siguiente árbol no es binario de búsqueda, ya que el nodo con clave 2, ubicado en el subárbol derecho de la raíz, tiene clave menor que ésta.

Los siguientes son árboles de búsqueda ya que cumplen la propiedad anterior.

La generación de estos árboles depende del orden en que se ingresen las claves en los nodos, a partir de un árbol vacío. El de la izquierda se generó insertando las claves en orden de llegada: 2, 1, 4, 3, 5 (o bien: 2, 4, 1, 5, 3). El de más a la derecha, se generó con la llegada en el orden: 5, 4, 3, 2, 1

Los dos árboles de más a la izquierda, en la Figura 6.5, se denominan balanceados, ya que las diferencias en altura de los subárboles izquierdo y derecho, para todos los nodos, difieren a lo más en uno. Los tres a la derecha están desbalanceados. El último tiene la estructura de una lista, y es un árbol degenerado.

Otras definiciones

Un árbol binario de búsqueda es una estructura de datos de tipo árbol binario en el que para todos sus nodos, el hijo izquierdo, si existe, contiene un valor menor que el nodo padre y el hijo derecho, si existe, contiene un valor mayor que el del nodo padre.

Obviamente, para establecer un orden entre los elementos del árbol, el tipo base debe ser escalar o debe tratarse de un tipo compuesto con una componente que actúe como clave de ordenación.

La siguiente figura es un ejemplo de árbol binario de búsqueda conteniendo enteros:

A continuación definiremos el Tipo Abstracto de Datos asociado a los árboles binarios de búsqueda. Para no alargar la descripción del mismo supondremos incluidas las operaciones del TAD ArbolB.

Búsqueda de un Elemento:
La operación de búsqueda en un árbol binario de búsqueda es bastante sencilla de entender. Supongamos que buscamos un elemento x en el árbol. Lo primero que haremos será comprobar si se encuentra en el nodo raíz. Si no es así, si el elemento buscado es menor que el contenido en el nodo raíz sabremos que, de estar en el árbol, se encuentra en el subárbol izquierdo. Si el elemento buscado es mayor que el contenido en el nodo raíz sabremos que, de estar en el árbol, se encuentra en el subárbol derecho. Para continuar la búsqueda en el subárbol adecuado aplicaremos recursivamente el mismo razonamiento. Por lo tanto, el esquema del algoritmo BuscarNodo será el siguiente: 1. Si el valor del nodo actual es igual al valor buscado, lo hemos encontrado. 2. Si el valor buscado es menor que el del nodo actual, deberemos inspeccionar el subárbol izquierdo. 3. Si el valor buscado es mayor que el del nodo actual, deberemos inspeccionar el subárbol derecho.

Inserción de un Elemento:
La operación de inserción de un nuevo nodo en un árbol binario de búsqueda consta de tres fases básicas: 1. Creación del nuevo nodo 2. Búsqueda de su posición correspondiente en el árbol. Se trata de encontrar la posición que le corresponde para que el árbol resultante siga siendo de búsqueda. 3. Inserción en la posición encontrado. Se modifican de modo adecuado los enlaces de la estructura. La creación de un nuevo nodo supone simplemente reservar espacio para el registro asociado y rellenar sus tres campos. Dado que no nos hemos impuesto la restricción de que el árbol resultante sea equilibrado, consideraremos que la posición adecuada para insertar el nuevo nodo es la hoja en la cual se mantiene el orden del árbol. Insertar el nodo en una hoja supone una operación mucho menos complicada que tener que insertarlo como un nodo interior y modificar la posición de uno o varios subárboles completos.

Veamos con un ejemplo la evolución de un árbol conforme vamos insertando nodos siguiendo el criterio anterior respecto a la posición adecuada.

Eliminación de un Elemento:
La eliminación de un nodo de un árbol binario de búsqueda es más complicada que la inserción, puesto que puede suponer la recolocación de varios de sus nodos. En líneas generales un posible esquema para abordar esta operación es el siguiente: 1. Buscar el nodo que se desea borrar manteniendo un puntero a su padre. 2. Si se encuentra el nodo hay que contemplar tres casos posibles: a. Si el nodo a borrar no tiene hijos, simplemente se libera el espacio que ocupa b. Si el nodo a borrar tiene un solo hijo, se añade como hijo de su padre, sustituyendo la posición ocupada por el nodo borrado. c. Si el nodo a borrar tiene los dos hijos se siguen los siguientes pasos: i. Se busca el máximo de la rama izquierda o el mínimo de la rama derecha. ii. Se sustituye el nodo a borrar por el nodo encontrado.

Veamos gráficamente varios ejemplos de eliminación de un nodo:

Implementación de Árbol Binario de Búsqueda en SEED

Descripción
El árbol Binario de Búsqueda es un árbol binario especial, cuya particularidad es que mantiene sus datos de manera ordena, estableciendo entre los datos el valor de comparación entre ellos. Su estructura también se fundamenta en una estructura denominada “NodoBin”, que almacena la información y del cual destaca un Nodo principal llamado “raíz” en donde este será mayor que su hijo izquierdo y menor que su hijo derecho y se almacenara los datos de menor valor en su hijo izquierdo y los de mayor valor en su hijo derecho.

Cabe mencionar que al poseer los datos ordenados el proceso de búsqueda a comparación con el Árbol Binario General es mucho más eficiente. Esta estructura posee gran similitud, con la estructura Árbol binario General, solo difieren en el hecho en que esta estructura los datos se insertar de forma ordenada. Por esta razón el equipo de desarrollo decidió usar herencia del Árbol Binario, de esta manera el árbol de Búsqueda adquiere los atributos, propiedades y las operaciones que se hallan declarado protegidas o publicas, la estructura se implemento en la clase ArbolBinarioBusqueda.

Los método básicos insertar se implementaron de nuevo teniendo en cuenta la propiedad de mantener los datos ordenados, en esta estructura al insertar el nuevo elemento no es necesario informar el padre ni el lado a insertar, debido a que ese proceso no hace parte que del comportamiento de la estructura. En el siguiente diagrama de clases se puede observar los métodos y atributos de la clase.

Requerimientos funcionales implementados:

RF1 Crear un nuevo Árbol Binario de Búsqueda.
RF2 Conocer y editar la raíz del Árbol Binario de Búsqueda.
RF3 Insertar nuevos datos en un Árbol Binario de Búsqueda.
RF4 Eliminar datos de un Árbol Binario de Búsqueda.
RF5 Consultar la existencia de objetos dentro del Árbol Binario de Búsqueda.
RF6 Editar objetos existentes dentro del Árbol Binario de Búsqueda. RF9 Consultar si un Nodo es o no una hoja del Árbol Binario de Búsqueda.
RF10 Recorrer un Árbol Binario de Búsqueda en Preorden, en Inorden y en PostOrden.
RF11 Recorrer un Árbol Binario de Búsqueda por niveles.
RF12 Conocer el peso de un Árbol Binario de Búsqueda.
RF13 Consultar la altura de un Árbol Binario de Búsqueda.
RF14 Podar un Árbol Binario de Búsqueda. (Eliminar sus Nodos Hoja).
RF15 Conocer por consola los datos presentes en el Árbol.

Implementación de un Simulador para Árbol Binario de Búsqueda
El Simulador posee las operaciones indicadas por su menú de opciones: