1 feb. 2013

Programación en C – Árbol Binario de Búsqueda (ABB) – Que es y cómo se usan

Hola a todos, en esta ocasión les presento los Arboles Binarios de Búsqueda, estaremos viendo que son, para que sirven y como se utilizan en el lenguaje de Programación C estructurado.

Antes de empezar a hablar sobre los Arboles Binarios de Búsqueda (ABB de aquí en adelante), debemos tener clara la Nomenclatura de Arboles, la cual esta detallada en el siguiente post, el cual se recomienda su lectura: Nomenclatura de Arboles. Tambien es recomendable la lectura de Recursividad Torres de Hanói para tener claros los conceptos de Recursividad.

Una vez entendida la nomenclatura, pasemos a los ABB.


- Que es un ABB?

Un ABB es como su nombre lo indica, un Árbol especial para realizar Búsquedas, el cual también es Binario, ya que la característica principal de estos árboles es que cada Padre puede tener solamente 2 Hijos, los cuales seguirán una regla, los Hijos con menor valor que el Padre deberán ser los Hijos Izquierdos, y los Hijos de mayor valor que el Padre deberán ser los Hijos Derechos. Aclaremos un poco esto con un ejemplo.

Vamos a crear un ABB agregando los siguientes valores en orden:

104, 71, 240, 17, 19, 108, 110, 245, 3, 18


El primer Nodo que vamos a agregar será el 104, el cual será la Raíz del Árbol, luego agregaremos el Nodo con valor 71 como su Hijo, comprobamos si el 71 es menor o mayor que su Padre, el 71 es menor que el 104, por lo tanto lo colocamos como su Hijo Izquierdo. Procedemos a agregar el Nodo con valor 240, como es mayor que el 104, lo colocamos como su Hijo Derecho. Por el momento el ABB nos queda de la siguiente forma



El Nodo siguiente que debemos agregar es el que tiene valor 17, este valor es menor que el 104, por lo tanto debe ser su Hijo Izquierdo, pero este Nodo Padre ya tiene un Hijo Izquierdo (el Nodo con valor 71), entonces comparamos el 17 con el 71, el 17 es menor que el 71 así que es su Hijo Izquierdo.

Luego agregamos el Nodo con valor 19, este es menor que 104, menor que el 71, y mayor que el 17, entonces este Nodo será el Hijo Derecho del Nodo con valor 17.

Siguiendo esta forma de completar un ABB, nuestro Árbol quedara finalmente de la siguiente forma




- Para qué sirve un ABB?

Un ABB, como su nombre lo indica, sirve para realizar búsquedas de una forma más efectiva que las listas enlazadas.

Imaginemos por un momento que tenemos el Árbol graficado anteriormente, y una Lista Enlazada con el orden en el que fuimos ingresando los elementos en el Árbol, y deseamos buscar el valor 18.

En el caso de la Lista Enlazada debemos recorrerla Nodo por Nodo hasta llegar al valor 18, lo que nos llevaría recorrer 10 Nodos antes de encontrar nuestro valor, en el caso del Árbol, para llegar de la Raíz al Nodo con valor 18, debemos ir al Hijo Izquierdo (71), luego al Hijo Izquierdo (17), y por ultimo al Hijo Derecho (18), lo que nos da un recorrido de 5 Nodos únicamente. Si bien parece despreciable la diferencia de recorrer 5 o 10 Nodos, entre más grande sean los Arboles y las Listas Enlazadas, será mayor la facilidad de encontrar el Nodo buscado en un Árbol que en una Lista.

Observación: Si los elementos del Árbol se insertan en forma ordenada (tanto ascendente como descendente), quedara formada una Lista Enlazada.


- Como se usa un ABB?

Para usar un ABB vamos a utilizar la siguiente estructura, la cual tendrá un valor entero y 2 punteros, uno para el Hijo Izquierdo y otro para el Hijo Derecho:


También vamos a declarar un puntero a la Raíz que no cambiara nunca, este será la referencia a nuestro Árbol, si lo perdemos no podremos tener acceso a nuestro Árbol y el programa tendrá perdidas de memoria. Declararemos a tpunteroa como un puntero a la estructura, y dentro del main declararemos a raíz del tipo de dato tpunteroa:


Esto podría realizarse también con un puntero del estilo:


Pero de esta forma deberíamos usar punteros dobles en alguna de las funciones y esto podría dar lugar a confusión, por lo que me parece mas elegante la forma que les propongo.


Para utilizar un ABB desarrollaremos una serie de funciones que nos permitirán utilizarlo, estas serán:

insertarArbol: Recibe como parámetro un puntero a un Nodo del Árbol y un entero, e inserta el Nodo en el lugar correspondiente del ABB según el valor del entero.

imprimirArbol: Recibe como parámetro un puntero a un Nodo del Árbol, e imprime el mismo En Orden, es decir de forma ordenada y ascendente todos los Nodos del Árbol.

borrarArbol: Recibe como parámetro un puntero a un Nodo del Árbol, y procede a borrar todo el Árbol.

buscar: Recibe como parámetro un puntero a un Nodo del Árbol y un entero, busca este entero en el Árbol y devuelve un puntero al Nodo si existe, si no existe devuelve un puntero nulo.

esHoja: Recibe como parámetro un puntero a un Nodo del Árbol. Devuelve un 1 si este Nodo es una Hoja, un 0 si no lo es

alturaArbolNodo: Recibe como parámetro un puntero a un Nodo del Árbol y un entero, y devuelve un entero con la altura que existe entre la Raiz y el Nodo con el valor recibido por parámetro.

alturaArbol: Recibe como parámetro un puntero a un Nodo del Árbol y un entero por referencia, el cual será modificado por la altura total del Árbol (recordar pasarle la raíz como Nodo para que nos devuelva la altura correcta del Árbol).

arbolCompleto: Recibe como parámetro un puntero a un Nodo del Árbol y un entero pasado por referencia, el cual será modificado por el valor 0 si no es un Árbol Completo, y por el valor 1 si es un Árbol Completo.

Mostremos un extenso ejemplo en código con estas funciones, y como se utilizan


Esto es todo por hoy, cualquier duda/pregunta en los comentarios :)

Saludos!

-----
Argies_Dario


Compilado con: Microsoft Visual Studio 2008
Sistema Operativo: Windows 7

Fuentes:
Ninguna

2 comentarios:

  1. Muy bueno el post, es la primer vez que encuentro este blog... Una consulta si quisiera hacer una funcion que vaya sacando nodo por nodo y de esa manera ir devolviendolo y ese nodo borrarlo, como seria? porque intente hacer una funcion que recorra el arbol y me devuelva la info pero no me funciona.... Desde ya gracias

    ResponderEliminar
    Respuestas
    1. Hola!, me alegro que te haya servido. Respecto a tu pregunta no se me ocurre nada elegante para solucionar ese problema, ya que al trabajar recursivamente complica mucho la funcionalidad que buscas.

      Lo que haria yo para poder solucionarlo, y esta es una solucion muy mala y pesimamente perfomante, pero podria usar todas las funciones del post. Seria hacer lo siguiente:

      Primero obtener el menor valor de nodo (el maximo nodo a la izquierda) y el mayor valor de nodo (el maximo nodo a la derecha), una vez establecido ese rango, hacer un while entre ese rango con un contador, que vaya buscando cada valor con la funcion buscar, esta funcion devuelve un puntero a ese nodo, si se encuentra el valor buscado, podrias consultar ese nodo y saber su valor, y en el caso de que este nodo sea hoja podrias borrarlo... CUIDADO: No debes borrar nodos que no sean hojas, porque sino se romperia el arbol!. Si el valor no se encuentra o si es encontrado y no es hoja se continua con el proximo valor a buscar.

      Como te comente, esta forma de solucionarlo tiene pesima perfomance porque habria que iterar muchisimas veces para ir sacando los nodos hojas y borrandolos, pero podria solucionarse rapidamente con todas las funciones que se encuentran en el post

      Saludos!

      Eliminar

Dejanos tu comentario sobre esta nota