Arboles Binario

Introducción

A los arboles ordenados de grado dos se les conoce como arboles binarios ya que cada nodo del árbol no tendrá más de dos descendientes directos. Las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.

La representación gráfica de un árbol binario es la siguiente:

Representación en Memoria

Hay dos formas tradicionales de representar un árbol binario en memoria:

• Por medio de datos tipo punteros también conocidos como variables dinámicas o listas.

• Por medio de arreglos.

Sin embargo la más utilizada es la primera, puesto que es la más natural para tratar este tipo de estructuras.

Los nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos. En un campo se almacenará la información del nodo. Los dos restantes se utilizarán para apuntar al subarbol izquierdo y derecho del subarbol en cuestión.

Cada nodo se representa gráficamente de la siguiente manera:

El algoritmo de creación de un árbol binario es el siguiente:

Procedimiento crear(q:nodo)

inicio

mensaje("Rama izquierda?")

lee(respuesta)

si respuesta = "si" entonces

new(p)

q(li) <– nil

crear(p)

en caso contrario

q(li) <– nil

mensaje("Rama derecha?")

lee(respuesta)

si respuesta="si" entonces

new(p)

q(ld)<–p

crear(p)

en caso contrario

q(ld) <–nil

fin

INICIO

new(p)

raiz<–p

crear(p)

FIN

Clasificación de Árboles Binarios

Existen cuatro tipos de árbol binario:.

• A. B. Distinto.

• A. B. Similares.

• A. B. Equivalentes.

• A. B. Completos.

A continuación se hará una breve descripción de los diferentes tipos de árbol binario así como un ejemplo de cada uno de ellos.

A. B. DISTINTO

Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes. Ejemplo:

A. B. SIMILARES

Dos arboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente. Ejemplo:

A. B. EQUIVALENTES

Son aquellos arboles que son similares y que además los nodos contienen la misma información. Ejemplo:

A. B. COMPLETOS

Son aquellos arboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subarbol izquierdo y el subarbol derecho

Recorrido de un Árbol Binario

Hay tres manera de recorrer un árbol : en inorden, preorden y postorden. Cada una de ellas tiene una secuencia distinta para analizar el árbol como se puede ver a continuación:

• INORDEN

• Recorrer el subarbol izquierdo en inorden.

• Examinar la raíz.

• Recorrer el subarbol derecho en inorden.

• PREORDEN

• Examinar la raíz.

• Recorrer el subarbol izquierdo en preorden.

• recorrer el subarbol derecho en preorden.

• POSTORDEN

• Recorrer el subarbol izquierdo en postorden.

• Recorrer el subarbol derecho en postorden.

• Examinar la raíz.

A continuación se muestra un ejemplo de los diferentes recorridos en un árbol binario.

Inorden: GDBHEIACJKF

Preorden: ABDGEHICFJK

Postorden: GDHIEBKJFCA

5.5 Arboles Enhebrados

Existe un tipo especial de árbol binario llamado enhebrado, el cual contiene hebras que pueden estar a la derecha o a la izquierda. El siguiente ejemplo es un árbol binario enhebrado a la derecha.

• ARBOL ENHEBRADO A LA DERECHA. Este tipo de árbol tiene un apuntador a la derecha que apunta a un nodo antecesor.

• ARBOL ENHEBRADO A LA IZQUIERDA. Estos arboles tienen un apuntador a la izquierda que apunta al nodo antecesor en orden

Control de Acceso a los Elementos de un Arreglo

En C++, el acceso a los elementos de un arreglo tiene que ser controlado por el programador, ya que el lenguaje no restringe la posibilidad de accesar a posiciones de memoria que están más abajo de la última posición reservada para el arreglo. Lo mismo sucede cuando se manejan cadenas, donde el programador tiene la responsabilidad de controlar el acceso a los caracteres de la cadena, tomando como límite el terminador nulo. En el listado 5.6 se presenta un ejemplo de acceso a los 5 bytes colocados abajo del terminador nulo de una cadena dada por el usuario.

#include // Para gets() y puts()

#include // Para clrscr() y gotoxy()

#include // Para strlen()

void main()

{

char nombre[31];

clrscr();

gotoxy(10,1);

puts("¿ Cuál es tu nombre ? ");

gotoxy(35,1);

gets(nombre);

clrscr();

gotoxy (10,1);

puts("ELEMENTO CARACTER DIRECCION");

for( int x=0 ; (x < x,nombre[x],nombre[x],&nombre[x]); u?, c="%4d" printf(?nombre[%2d] gotoxy(10,x+2); x++) x

Listado 5.6.- Colocación de los elementos de una cadena en memoria RAM.

Árboles en Montón

Esta sección consiste en transformar un bosque en un árbol binario. Entenderemos como bosque a un conjunto normalmente ordenado de dos o más árboles generales.

La serie de pasos que debemos seguir para lograr la conversión de un bosque en un árbol binario es la siguiente:

• Enlazar horizontalmente las raíces de los distintos árboles generales.

• Enlazar los hijos de cada nodo en forma horizontal (los hermanos).

• Enlazar verticalmente el nodo padre con el hijo que se encuentra más a la izquierda. Además debe eliminarse el vínculo de ese padre con el resto de sus hijos.

• Debe rotarse el diagrama resultante aproximadamente 45 grados hacia la izquierda y así se obtendrá el árbol binario correspondiente.

5.8 Arboles binarios de búsqueda

Un árbol de búsqueda binaria es una estructura apropiada para muchas de las aplicaciones que se han discutido anteriormente con listas. La ventaja especial de utilizar un arbol es que se facilita la búsqueda.

Un árbol binario de búsqueda es aquel en el que el hijo de la izquierda (si existe) de cualquier nodo contiene un valor más pequeño que el nodo padre, y el hijo de la derecha (si existe) contiene un valor más grande que el nodo padre.

Un ejemplo de arbol binario de búsqueda es el siguiente:

Capítulo 7

Árboles binarios de búsqueda (ABB)

7.1 Definición  

Se trata de árboles de orden 2 en los que se cumple que para cada nodo, el valor de la clave de la raíz del subárbol izquierdo es menor que el valor de la clave del nodo y que el valor de la clave raíz del subárbol derecho es mayor que el valor de la clave del nodo.

7.2 Operaciones en ABB

El repertorio de operaciones que se pueden realizar sobre un ABB es parecido al que realizábamos sobre otras estructuras de datos, más alguna otra propia de árboles:

• Buscar un elemento.

• Insertar un elemento.

• Borrar un elemento.

• Movimientos a través del árbol:

• Izquierda.

• Derecha.

• Raiz.

• Información:

• Comprobar si un árbol está vacío.

• Calcular el número de nodos.

• Comprobar si el nodo es hoja.

• Calcular la altura de un nodo.

• Calcular la altura de un árbol.

7.3 Buscar un elemento 

Partiendo siempre del nodo raíz, el modo de buscar un elemento se define de forma recursiva.

• Si el árbol está vacío, terminamos la búsqueda: el elemento no está en el árbol.

• Si el valor del nodo raíz es igual que el del elemento que buscamos, terminamos la búsqueda con éxito.

• Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo.

• Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho.

El valor de retorno de una función de búsqueda en un ABB puede ser un puntero al nodo encontrado, o NULL, si no se ha encontrado.

7.4 Insertar un elemento

Para insertar un elemento nos basamos en el algoritmo de búsqueda. Si el elemento está en el árbol no lo insertaremos. Si no lo está, lo insertaremos a continuación del último nodo visitado.

Necesitamos un puntero auxiliar para conservar una referencia al padre del nodo raíz actual. El valor inicial para ese puntero es NULL.

• Padre = NULL

• nodo = Raiz

• Bucle: mientras actual no sea un árbol vacío o hasta que se encuentre el elemento.

• Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo: Padre=nodo, nodo=nodo->izquierdo.

• Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho: Padre=nodo, nodo=nodo->derecho.

• Si nodo no es NULL, el elemento está en el árbol, por lo tanto salimos.

• Si Padre es NULL, el árbol estaba vacío, por lo tanto, el nuevo árbol sólo contendrá el nuevo elemento, que será la raíz del árbol.

• Si el elemento es menor que el Padre, entonces insertamos el nuevo elemento como un nuevo árbol izquierdo de Padre.

• Si el elemento es mayor que el Padre, entonces insertamos el nuevo elemento como un nuevo árbol derecho de Padre.

Este modo de actuar asegura que el árbol sigue siendo ABB.

7.5 Borrar un elemento

Para borrar un elemento también nos basamos en el algoritmo de búsqueda. Si el elemento no está en el árbol no lo podremos borrar. Si está, hay dos casos posibles:

• Se trata de un nodo hoja: en ese caso lo borraremos directamente.

• Se trata de un nodo rama: en ese caso no podemos eliminarlo, puesto que perderíamos todos los elementos del árbol de que el nodo actual es padre. En su lugar buscamos el nodo más a la izquierda del subárbol derecho, o el más a la derecha del subárbol izquierdo e intercambiamos sus valores. A continuación eliminamos el nodo hoja.

Necesitamos un puntero auxiliar para conservar una referencia al padre del nodo raíz actual. El valor inicial para ese puntero es NULL.

• Padre = NULL

• Si el árbol está vacío: el elemento no está en el árbol, por lo tanto salimos sin eliminar ningún elemento.

• (1) Si el valor del nodo raíz es igual que el del elemento que buscamos, estamos ante uno de los siguientes casos:

• El nodo raíz es un nodo hoja:

• Si 'Padre' es NULL, el nodo raíz es el único del árbol, por lo tanto el puntero al árbol debe ser NULL.

• Si raíz es la rama derecha de 'Padre', hacemos que esa rama apunte a NULL.

• Si raíz es la rama izquierda de 'Padre', hacemos que esa rama apunte a NULL.

• Eliminamos el nodo, y salimos.

• El nodo no es un nodo hoja:

• Buscamos el 'nodo' más a la izquierda del árbol derecho de raíz o el más a la derecha del árbol izquierdo. Hay que tener en cuenta que puede que sólo exista uno de esos árboles. Al mismo tiempo, actualizamos 'Padre' para que apunte al padre de 'nodo'.

• Intercambiamos los elementos de los nodos raíz y 'nodo'.

• Borramos el nodo 'nodo'. Esto significa volver a (1), ya que puede suceder que 'nodo' no sea un nodo hoja. (Ver ejemplo 3)

• Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo.

• Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho.

Ejemplo 1: Borrar un nodo hoja

En el árbol de ejemplo, borrar el nodo 3.

• Localizamos el nodo a borrar, al tiempo que mantenemos un puntero a 'Padre'.

• Hacemos que el puntero de 'Padre' que apuntaba a 'nodo', ahora apunte a NULL.

• Borramos el 'nodo'.

Ejemplo 2:

Borrar un nodo rama con intercambio de un nodo hoja.

En el árbol de ejemplo, borrar el nodo 4.

• Localizamos el nodo a borrar ('raíz').

• Buscamos el nodo más a la derecha del árbol izquierdo de 'raíz', en este caso el 3, al tiempo que mantenemos un puntero a 'Padre' a 'nodo'.

• Intercambiamos los elementos 3 y 4.

• Hacemos que el puntero de 'Padre' que apuntaba a 'nodo', ahora apunte a NULL.

• Borramos el 'nodo'.

Ejemplo 3:

Borrar un nodo rama con intercambio de un nodo rama.

Para este ejemplo usaremos otro árbol. En éste borraremos el elemento 6.

• Localizamos el nodo a borrar ('raíz').

• Buscamos el nodo más a la izquierda del árbol derecho de 'raíz', en este caso el 12, ya que el árbol derecho no tiene nodos a su izquierda, si optamos por la rama izquierda, estaremos en un caso análogo. Al mismo tiempo que mantenemos un puntero a 'Padre' a 'nodo'.

• Intercambiamos los elementos 6 y 12.

• Ahora tenemos que repetir el bucle para el nodo 6 de nuevo, ya que no podemos eliminarlo.

• Localizamos de nuevo el nodo a borrar ('raíz').

• Buscamos el nodo más a la izquierda del árbol derecho de 'raíz', en este caso el 16, al mismo tiempo que mantenemos un puntero a 'Padre' a 'nodo'.

• Intercambiamos los elementos 6 y 16.

• Hacemos que el puntero de 'Padre' que apuntaba a 'nodo', ahora apunte a NULL.

• Borramos el 'nodo'.

Este modo de actuar asegura que el árbol sigue siendo ABB.

Operaciones básicas con árboles

Salvo que trabajemos con árboles especiales, como los que veremos más adelante, las inserciones serán siempre en punteros de nodos hoja o en punteros libres de nodos rama. Con estas estructuras no es tan fácil generalizar, ya que existen muchas variedades de árboles.

De nuevo tenemos casi el mismo repertorio de operaciones de las que disponíamos con las listas:

• Añadir o insertar elementos.

• Buscar o localizar elementos.

• Borrar elementos.

• Moverse a través del árbol.

• Recorrer el árbol completo.

Los algoritmos de inserción y borrado dependen en gran medida del tipo de árbol que estemos implementando, de modo que por ahora los pasaremos por alto y nos centraremos más en el modo de recorrer árboles.

6.4 Recorridos por árboles:

El modo evidente de moverse a través de las ramas de un árbol es siguiendo los punteros, del mismo modo en que nos movíamos a través de las listas.

Esos recorridos dependen en gran medida del tipo y propósito del árbol, pero hay ciertos recorridos que usaremos frecuentemente. Se trata de aquellos recorridos que incluyen todo el árbol.

Hay tres formas de recorrer un árbol completo, y las tres se suelen implementar mediante recursividad. En los tres casos se sigue siempre a partir de cada nodo todas las ramas una por una.

Supongamos que tenemos un árbol de orden tres, y queremos recorrerlo por completo.

Partiremos del nodo raíz:

RecorrerArbol(raiz);

La función RecorrerArbol, aplicando recursividad, será tan sencilla como invocar de nuevo a la función RecorrerArbol para cada una de las ramas:

void RecorrerArbol(Arbol a) {

if(a == NULL) return;

RecorrerArbol(a->rama[0]);

RecorrerArbol(a->rama[1]);

RecorrerArbol(a->rama[2]);

}

Lo que diferencia los distintos métodos de recorrer el árbol no es el sistema de hacerlo, sino el momento que elegimos para procesar el valor de cada nodo con relación a los recorridos de cada una de las ramas.

Los tres tipos son:

Pre-orden:

En este tipo de recorrido, el valor del nodo se procesa antes de recorrer las ramas:

void PreOrden(Arbol a) {

if(a == NULL) return;

Procesar(dato);

RecorrerArbol(a->rama[0]);

RecorrerArbol(a->rama[1]);

RecorrerArbol(a->rama[2]);

}

Si seguimos el árbol del ejemplo en pre-orden, y el proceso de los datos es sencillamente mostrarlos por pantalla, obtendremos algo así:

A B E K F C G L M D H I J N O

In-orden:

En este tipo de recorrido, el valor del nodo se procesa después de recorrer la primera rama y antes de recorrer la última. Esto tiene más sentido en el caso de árboles binarios, y también cuando existen ORDEN-1 datos, en cuyo caso procesaremos cada dato entre el recorrido de cada dos ramas (este es el caso de los árboles-b):

void InOrden(Arbol a) {

if(a == NULL) return;

RecorrerArbol(a->rama[0]);

Procesar(dato);

RecorrerArbol(a->rama[1]);

RecorrerArbol(a->rama[2]);

}

Si seguimos el árbol del ejemplo en in-orden, y el proceso de los datos es sencillamente mostrarlos por pantalla, obtendremos algo así:

K E B F A L G M C H D I N J O

Post-orden:

En este tipo de recorrido, el valor del nodo se procesa después de recorrer todas las ramas:

void PostOrden(Arbol a) {

if(a == NULL) return;

RecorrerArbol(a->rama[0]);

RecorrerArbol(a->rama[1]);

RecorrerArbol(a->rama[2]);

Procesar(dato);

}

Si seguimos el árbol del ejemplo en post-orden, y el proceso de los datos es sencillamente mostrarlos por pantalla, obtendremos algo así:

K E F B L M G C H I N O J D A

6.5 Eliminar nodos en un árbol:

El proceso general es muy sencillo en este caso, pero con una importante limitación, sólo podemos borrar nodos hoja:

El proceso sería el siguiente:

• Buscar el nodo padre del que queremos eliminar.

• Buscar el puntero del nodo padre que apunta al nodo que queremos borrar.

• Liberar el nodo.

• padre->nodo[i] = NULL;.

Cuando el nodo a borrar no sea un nodo hoja, diremos que hacemos una "poda", y en ese caso eliminaremos el árbol cuya raíz es el nodo a borrar. Se trata de un procedimiento recursivo, aplicamos el recorrido PostOrden, y el proceso será borrar el nodo.

El procedimiento es similar al de borrado de un nodo:

• Buscar el nodo padre del que queremos eliminar.

• Buscar el puntero del nodo padre que apunta al nodo que queremos borrar.

• Podar el árbol cuyo padre es nodo.

• padre->nodo[i] = NULL;.

En el árbol del ejemplo, para podar la rama 'B', recorreremos el subárbol 'B' en postorden, eliminando cada nodo cuando se procese, de este modo no perdemos los punteros a las ramas apuntadas por cada nodo, ya que esas ramas se borrarán antes de eliminar el nodo.

De modo que el orden en que se borrarán los nodos será:

K E F y B

6.6 árboles ordenados:

A partir del siguiente capítulo sólo hablaremos de árboles ordenados, ya que son los que tienen más interés desde el punto de vista de TAD, y los que tienen más aplicaciones genéricas.

Un árbol ordenado, en general, es aquel a partir del cual se puede obtener una secuencia ordenada siguiendo uno de los recorridos posibles del árbol: inorden, preorden o postorden.

En estos árboles es importante que la secuencia se mantenga ordenada aunque se añadan o se eliminen nodos.

Existen varios tipos de árboles ordenados, que veremos a continuación:

• árboles binarios de búsqueda (ABB): son árboles de orden 2 que mantienen una secuencia ordenada si se recorren en inorden.

• árboles AVL: son árboles binarios de búsqueda equilibrados, es decir, los niveles de cada rama para cualquier nodo no difieren en más de 1.

• árboles perfectamente equilibrados: son árboles binarios de búsqueda en los que el número de nodos de cada rama para cualquier nodo no difieren en más de 1. Son por lo tanto árboles AVL también.

• árboles 2-3: son árboles de orden 3, que contienen dos claves en cada nodo y que están también equilibrados. También generan secuencias ordenadas al recorrerlos en inorden.

• árboles-B: caso general de árboles 2-3, que para un orden M, contienen M-1 claves.

Autor:

Danny Guerrero