Áboles binarios de búsqueda

La estructura de datos que veremos es la de árboles, esta estructura nos permite organizar información de forma que tenemos una relación de padres e hijos, ordenando por ejemplo por un valor.En el primer caso veremos el árbol binario de búsqueda, donde cada nodo tiene dos ramas y un campo de valor, a la izquierda conectaremos otros nodos de menor valor y a la derecha otros nodos de mayor valor.

Veamos una definición de árbol binario:

typedef struct arbol {
arbol * izq;
arbol * der;
int valor;
};

Definiremos como NULL un árbol vacío, para cada nodo del árbol tendremos una rama izquierda y una derecha, que son punteros a otros nodos, y un campo para el valor. En este ejemplo usaremos un int para el valor para simplificar, pero podríamos tener un puntero a otra estructura más compleja (y tendríamos que tener forma de poder comparar estos elementos más complejos de forma que podamos ordenar el árbol).

Siguiente la línea de definir un TAD, vamos a crear operaciones básicas sobre esta definición para realizar las tareas esenciales sobre un árbol, como crear, insertar, recorrer y borrar. Por la naturaleza de los árboles tenemos una definición recurrente, y el TAD también trabajará de esta forma, con funciones recursivas sobre la estructura de datos.

Aquí tenemos un TAD para nuestro árbol binario:

arbol * ArbolCrear();
// Crear un árbol vacío.

bool ArbolEsVacio(arbol * t);
// Devuelve true si el árbol ess vacío.

void ArbolInsertar (arbol *& t, int n);
// Inserta el elemento n en el árbol.

int ArbolRaiz(arbol * t);
// Devuelve la raíz del árbol.

arbol * ArbolIzq(arbol * t);
// Devuelve la rama izquierda del árbol.

arbol * ArbolDer(arbol * t);
// Devuelve la rama derecha del árbol.

Y su implementación:

arbol * ArbolCrearVacio() {
return NULL;
}

bool ArbolEsVacio(arbol * t) {
return t == NULL;
}

void ArbolInsertar (arbol *& t, int n) {
if (ArbolEsVacio(t)) {
arbol * nodo = new arbol;
nodo->valor = n;
nodo->izq = ArbolCrearVacio();
nodo->der= ArbolCrearVacio();
t = nodo;
} else {
if (arbol->nodo > n) {
ArbolInsertar (t->izq, n);
} else {
ArbolInsertar (t->der, n);
}
}
}

int ArbolRaiz(arbol * t) {
return t->valor;
}

arbol * ArbolIzq(arbol * t) {
return t->izq;
}

arbol * ArbolDer(arbol * t) {
return t->der;
}

Tengan en cuenta algunos detalles, como por ejemplo al insertar pasamos por referencia el puntero al árbol de forma que podemos modificarlo. Otro detalle es que por ejemplo las operaciones que nos dan las ramas izq y der deben ser utilizadas con precaución, ya que no chequean que el árbol sea vacío. Por lo tanto si llamamos a una de estas operaciones con un árbol vacío tendremos un error grave en el programa. Tenemos que colocar una precondición en el TAD, aclarando que esa operación sólo puede ser utilizada en el caso de que hayamos chequeado que el árbol que le pasamos no es vacio.

arbol * ArbolIzq(arbol * t);
// Devuelve la rama izquierda del árbol.
// Precondición: !ArbolEsVacio(t)

arbol * ArbolDer(arbol * t);
// Devuelve la rama derecha del árbol.
// Precondición: !ArbolEsVacio(t)

Ahora que tenemos el árbol binario podemos organizar información, por ejemplo si tenemos una gran cantidad de numeros y queremos saber si determinado número pertenece al conjunto podemos hacerlo recorriendo el árbol en forma recursiva, chequeando con el nodo actual y recorriendo las ramas. Por ejemplo podríamos hacer algo asi:

bool ArbolPertenece (arbol * t, int n) {
if (ArbolEsVacio(t)){
return false;
} else {
if (t->valor == n) {
return true;
} else if (t->valor > n) {
return ArbolPertenece(t->izq, n);
} else {
return ArbolPertenece(t->der, n);
}
}
}

Si el nodo en que estamos es vacío, entonces no encontramos el valor buscado, si no es vacío comparamos el valor del nodo actual, si es igual lo encontramos y devolvemos true, si no es igual puede ser mayor o menor por lo que llamamos en forma recursiva a la función con una de las dos ramas para seguir buscando.

Podemos ver que la eficiencia de esta estructura de datos es mucho mayor en las búsquedas, ya que podemos encontrar un elemento sin tener que recorrer todo el conjunto, como nos sucedía en el caso de las listas. Lo que hacemos al buscar en el árbol binario de búsqueda es ir dividiendo el conjunto en dos partes, por lo que cada vez reducimos a la mitad la cantidad de elementos, lo que nos da un orden de búsqueda igual a lograitmo de n, donde n es la cantidad de elementos del conjunto (vermos esto en más detalle más adelante, al finalizar las estructuras y realizar un análisis de órdenes de las mismas).

Por su parte la lista nos obliga a recorrer todo el conjunto de elementos, por lo que podemos tener que recorrer toda la lista para encontrar. Entonces tenemos que para buscar tenemos orden n para la lista, y orden ln(n) para el árbol binario.

Pero no todo es color de rosas en los árboles binarios, ya que tenemos dos complicaciones. La primera es que para insertar un elemento tenemos que recorrer, comparando con los nodos hasta llegar al lugar adecuado del valor dentro del árbol, lo que nos llevar a realizar ln(n) operaciones antes de poder insertar, mientras que con la lista insertamos al comienzo de la misma y no tenemos que recorrer nada, lo que nos da un orden 1 (es decir, una sola operación para insertar sin importar la cantidad de elementos que haya en el conjunto).

El otro problema que tenemos es que no realizamos balanceos del árbol al insertar, a medida que vamos insertando vamos dejando los nodos tal quedan de las comparaciones, pero esto puede provocar que nuestro árbol se transforme en una lista (o en algo parecido a una lista) si se dan ciertas condiciones. Por ejemplo, supongamos que queremos insertar los siguientes números: 10, 8, 6, 4, 2. Entonces siempre estaremos insertando en la rama izquierda, por lo que tendremos en realidad una lista de elementos, no tendremos una distribución pareja de elementos lo cual es necesario para que nuestra búsqueda tenga orden ln(n) (recuerden que este orden se da por ir dividiendo el conjunto en 2 cada vez, reduciendo el tamaño).

Para solucionar este problema veremos en la siguiente entrada, la estructura de datos conocida como AVL, esta estructura sigue la línea del árbol binario que acabamos de ver pero haciendo hincapie en mantener el árbol balanceado en todo momento, es decir que nunca tendremos el problema de que nuestro árbol degenere en una lista y perdamos la posibilidad de buscar en forma rápida dentro del conjunto. Esto lo lograremos rotando las ramas luego de insertar si las mismas quedan desbalanceadas.