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