finicin de rbol

* Formas de representacin
* Nomenclatura sobre rboles
* Declaracin de rbol binario
* Recorridos sobre rboles binarios
* Construccin de un rbol binario
* rbol binario de bsqueda
* Problemas

Definicin de rbol
Un rbol es una estructura de datos, que puede definirse de forma recursiva como:
- Una estructura vaca o
- Un elemento o clave de informacin (nodo) ms un nmero finito de estructuras tipo
rbol, disjuntos, llamados subrboles. Si dicho nmero de estructuras es inferior o
igual a 2, se tiene un rbol binario.
Es, por tanto, una estructura no secuencial.
Otra definicin nos da el rbol como un tipo de grafo (ver grafos): un rbol es un grafo
acclico, conexo y no dirigido. Es decir, es un grafo no dirigido en el que existe
exactamente un camino entre todo par de nodos. Esta definicin permite implementar
un rbol y sus operaciones empleando las representaciones que se utilizan para los
grafos. Sin embargo, en esta seccin no se tratar esta implementacin.

Formas de representacin
- Mediante un grafo:

Figura 1

- Mediante un diagrama encolumnado:

a

b
c

d
e
f

En la computacin se utiliza mucho una estructura de datos, que son los rboles
binarios. Estos rboles tienen 0, 1 2 descendientes como mximo. El rbol de la
figura anterior es un ejemplo vlido de rbol binario.

Nomenclatura sobre rboles

- Raz: es aquel elemento que no tiene antecesor; ejemplo: a.
- Rama: arista entre dos nodos.
- Antecesor: un nodo X es es antecesor de un nodo Y si por alguna de las ramas de X
se puede llegar a Y.
- Sucesor: un nodo X es sucesor de un nodo Y si por alguna de las ramas de Y se
puede llegar a X.
- Grado de un nodo: el nmero de descendientes directos que tiene. Ejemplo: c tiene
grado 2, d tiene grado 0, a tiene grado 2.
- Hoja: nodo que no tiene descendientes: grado 0. Ejemplo: d
- Nodo interno: aquel que tiene al menos un descendiente.
- Nivel: nmero de ramas que hay que recorrer para llegar de la raz a un nodo.
Ejemplo: el nivel del nodo a es 1 (es un convenio), el nivel del nodo e es 3.
- Altura: el nivel ms alto del rbol. En el ejemplo de la figura 1 la altura es 3.
- Anchura: es el mayor valor del nmero de nodos que hay en un nivel. En la figura, la
anchura es 3.
Aclaraciones: se ha denominado a a la raz, pero se puede observar segn la figura
que cualquier nodo podra ser considerado raz, basta con girar el rbol. Podra
determinarse por ejemplo que b fuera la raz, y a y d los sucesores inmediatos de la
raz b. Sin embargo, en las implementaciones sobre un computador que se realizan a
continuacin es necesaria una jerarqua, es decir, que haya una nica raz.

Declaracin de rbol binario

Se definir el rbol con una clave de tipo entero (puede ser cualquier otra tipo de
datos) y dos hijos: izquierdo (izq) y derecho (der). Para representar los enlaces con los
hijos se utilizan punteros. El rbol vaco se representar con un puntero nulo.

Un rbol binario puede declararse de la siguiente manera:

typedef struct tarbol
{
int clave;
struct tarbol *izq,*der;
} tarbol;
Otras declaraciones tambin aaden un enlace al nodo padre, pero no se estudiarn
aqu.

Recorridos sobre rboles binarios

Se consideran dos tipos de recorrido: recorrido en profundidad y recorrido en anchura
o a nivel. Puesto que los rboles no son secuenciales como las listas, hay que buscar
estrategias alternativas para visitar todos los nodos.
- Recorridos en profundidad:
* Recorrido en preorden: consiste en visitar el nodo actual (visitar puede ser
simplemente mostrar la clave del nodo por pantalla), y despus visitar el subrbol
izquierdo y una vez visitado, visitar el subrbol derecho. Es un proceso recursivo por
naturaleza.
Si se hace el recorrido en preorden del rbol de la figura 1 las visitas seran en el orden
siguiente: a,b,d,c,e,f.
void preorden(tarbol *a)
{
if (a != NULL) {
visitar(a);
preorden(a->izq);
preorden(a->der);
}
}

* Recorrido en inorden u orden central: se visita el subrbol izquierdo, el nodo actual,

y despus se visita el subrbol derecho. En el ejemplo de la figura 1 las visitas seran
en este orden: b,d,a,e,c,f.
void inorden(tarbol *a)
{
if (a != NULL) {
inorden(a->izq);
visitar(a);
inorden(a->der);
}
}

* Recorrido en postorden: se visitan primero el subrbol izquierdo, despus el

subrbol derecho, y por ltimo el nodo actual. En el ejemplo de la figura 1 el recorrido
quedara as: d,b,e,f,c,a.
void postorden(arbol *a)
{
if (a != NULL) {
postorden(a->izq);
postorden(a->der);
visitar(a);
}
}
La ventaja del recorrido en postorden es que permite borrar el rbol de forma
consistente. Es decir, si visitar se traduce por borrar el nodo actual, al ejecutar este
recorrido se borrar el rbol o subrbol que se pasa como parmetro. La razn para
hacer esto es que no se debe borrar un nodo y despus sus subrboles, porque al
borrarlo se pueden perder los enlaces, y aunque no se perdieran se rompe con la regla
de manipular una estructura de datos inexistente. Una alternativa es utilizar una
variable auxiliar, pero es innecesario aplicando este recorrido.

- Recorrido en amplitud:
Consiste en ir visitando el rbol por niveles. Primero se visitan los nodos de nivel 1
(como mucho hay uno, la raz), despus los nodos de nivel 2, as hasta que ya no
queden ms.
Si se hace el recorrido en amplitud del rbol de la figura una visitara los nodos en este
orden: a,b,c,d,e,f
En este caso el recorrido no se realizar de forma recursiva sino iterativa, utilizando
una cola (ver Colas) como estructura de datos auxiliar. El procedimiento consiste en
encolar (si no estn vacos) los subrboles izquierdo y derecho del nodo extraido de la
cola, y seguir desencolando y encolando hasta que la cola est vaca.
En la codificacin que viene a continuacin no se implementan las operaciones sobre
colas.
void amplitud(tarbol *a)
{
tCola cola;
/* las claves de la cola sern de tipo rbol binario */
arbol *aux;

if (a != NULL) {
CrearCola(cola);
encolar(cola, a);
while (!colavacia(cola)) {
desencolar(cola, aux);
visitar(aux);
if (aux->izq != NULL) encolar(cola, aux->izq);
if (aux->der != NULL) encolar(cola, aux->der);
}
}

Por ltimo, considrese la sustitucin de la cola por una pila en el recorrido en

amplitud. Qu tipo de recorrido se obtiene?

Construccin de un rbol binario

Hasta el momento se ha visto la declaracin y recorrido de un rbol binario. Sin
embargo no se ha estudiado ningn mtodo para crearlos. A continuacin se estudia
un mtodo para crear un rbol binario que no tenga claves repetidas partiendo de su
recorrido en preorden e inorden, almacenados en sendos arrays.
Antes de explicarlo se recomienda al lector que lo intente hacer por su cuenta, es
sencillo cuando uno es capaz de construir el rbol viendo sus recorridos pero sin haber
visto el rbol terminado.
Partiendo de los recorridos preorden e inorden del rbol de la figura 1 puede
determinarse que la raz es el primer elemento del recorrido en preorden. Ese
elemento se busca en el array inorden. Los elementos en el array inorden entre izq y
la raz forman el subrbol izquierdo. Asimismo los elementos entre der y la raz forman
el subrbol derecho. Por tanto se tiene este rbol:

A continuacin comienza un proceso recursivo. Se procede a crear el subrbol

izquierdo, cuyo tamao est limitado por los ndices izq y der. La siguiente posicin en
el recorrido en preorden es la raz de este subrbol. Queda esto:

El subrbol b tiene un subrbol derecho, que no tiene ningn descendiente, tal y como
indican los ndices izq y der. Se ha obtenido el subrbol izquierdo completo de la raza,
puesto que b no tiene subrbol izquierdo:

Despus seguir construyndose el subrbol derecho a partir de la raz a.

La implementacin de la construccin de un rbol partiendo de los recorridos en
preorden y en inorden puede consultarse aqu (en C).

rbol binario de bsqueda

Un rbol binario de bsqueda es aquel que es:

- Una estructura vaca o

- Un elemento o clave de informacin (nodo) ms un nmero finito -a lo sumo dos- de
estructuras tipo rbol, disjuntos, llamados subrboles y adems cumplen lo siguiente:
* Todas las claves del subrbol izquierdo al nodo son menores que la clave del nodo.
* Todas las claves del subrbol derecho al nodo son mayores que la clave del nodo.
* Ambos subrboles son rboles binarios de bsqueda.
Un ejemplo de rbol binario de bsqueda:

Figura 5
Al definir el tipo de datos que representa la clave de un nodo dentro de un rbol
binario de bsqueda es necesario que en dicho tipo se pueda establecer una relacin
de orden. Por ejemplo, suponer que el tipo de datos de la clave es un puntero (da igual
a lo que apunte). Si se codifica el rbol en Pascal no se puede establecer una relacin
de orden para las claves, puesto que Pascal no admite determinar si un puntero es
mayor o menor que otro.
En el ejemplo de la figura 5 las claves son nmeros enteros. Dada la raz 4, las claves
del subrbol izquierdo son menores que 4, y las claves del subrbol derecho son
mayores que 4. Esto se cumple tambin para todos los subrboles. Si se hace el
recorrido de este rbol en orden central se obtiene una lista de los nmeros ordenada
de menor a mayor.
Cuestin: Qu hay que hacer para obtener una lista de los nmeros ordenada de
mayor a menor?
Una ventaja fundamental de los rboles de bsqueda es que son en general mucho
ms rpidos para localizar un elemento que una lista enlazada. Por tanto, son ms
rpidos para insertar y borrar elementos. Si el rbol est perfectamente
equilibrado -esto es, la diferencia entre el nmero de nodos del subrbol izquierdo y
el nmero de nodos del subrbol derecho es a lo sumo 1, para todos los nodosentonces el nmero de comparaciones necesarias para localizar una clave es
aproximadamente de logN en el peor caso. Adems, el algoritmo de insercin en un
rbol binario de bsqueda tiene la ventaja -sobre los arrays ordenados, donde se
empleara bsqueda dicotmica para localizar un elemento- de que no necesita hacer
una reubicacin de los elementos de la estructura para que esta siga ordenada
despus de la insercin. Dicho algoritmo funciona avanzando por el rbol escogiendo la

rama izquierda o derecha en funcin de la clave que se inserta y la clave del nodo
actual, hasta encontrar su ubicacin; por ejemplo, insertar la clave 7 en el rbol de la
figura 5 requiere avanzar por el rbol hasta llegar a la clave 8, e introducir la nueva
clave en el subrbol izquierdo a 8.
El algoritmo de borrado en rboles es algo ms complejo, pero ms eficiente que el de
borrado en un array ordenado.
Ahora bien, suponer que se tiene un rbol vaco, que admite claves de tipo entero.
Suponer que se van a ir introduciendo las claves de forma ascendente. Ejemplo:
1,2,3,4,5,6
Se crea un rbol cuya raz tiene la clave 1. Se inserta la clave 2 en el subrbol derecho
de 1. A continuacin se inserta la clave 3 en el subrbol derecho de 2.
Continuando las inserciones se ve que el rbol degenera en una lista secuencial,
reduciendo drsticamente su eficacia para localizar un elemento. De todas formas es
poco probable que se de un caso de este tipo en la prctica. Si las claves a introducir
llegan de forma ms o menos aleatoria entonces la implementacin de operaciones
sobre un rbol binario de bsqueda que vienen a continuacin son en general
suficientes.
Existen variaciones sobre estos rboles, como los AVL o Red-Black (no se tratan aqu),
que sin llegar a cumplir al 100% el criterio de rbol perfectamente equilibrado, evitan
problemas como el de obtener una lista degenerada.

Operaciones bsicas sobre rboles binarios de bsqueda

- Bsqueda
Si el rbol no es de bsqueda, es necesario emplear uno de los recorridos anteriores
sobre el rbol para localizarlo. El resultado es idntico al de una bsqueda secuencial.
Aprovechando las propiedades del rbol de bsqueda se puede acelerar la localizacin.
Simplemente hay que descender a lo largo del rbol a izquierda o derecha
dependiendo del elemento que se busca.
boolean buscar(tarbol *a, int elem)
{
if (a == NULL) return FALSE;
else if (a->clave < elem) return buscar(a->der, elem);
else if (a->clave > elem) return buscar(a->izq, elem);
else return TRUE;
}

- Insercin
La insercin tampoco es complicada. Es ms, resulta practicamente idntica a la
bsqueda. Cuando se llega a un rbol vaco se crea el nodo en el puntero que se pasa
como parmetro por referencia, de esta manera los nuevos enlaces mantienen la
coherencia. Si el elemento a insertar ya existe entonces no se hace nada.
void insertar(tarbol **a, int elem)

if (*a == NULL) {
*a = (arbol *) malloc(sizeof(arbol));
(*a)->clave = elem;
(*a)->izq = (*a)->der = NULL;
}
else if ((*a)->clave < elem) insertar(&(*a)->der, elem);
else if ((*a)->clave > elem) insertar(&(*a)->izq, elem);

- Borrado
La operacin de borrado si resulta ser algo ms complicada. Se recuerda que el rbol
debe seguir siendo de bsqueda tras el borrado. Pueden darse tres casos, una vez
encontrado el nodo a borrar:
1) El nodo no tiene descendientes. Simplemente se borra.
2) El nodo tiene al menos un descendiente por una sola rama. Se borra dicho nodo, y
su primer descendiente se asigna como hijo del padre del nodo borrado. Ejemplo: en el
rbol de la figura 5 se borra el nodo cuya clave es -1. El rbol resultante es:

3) El nodo tiene al menos un descendiente por cada rama. Al borrar dicho nodo es
necesario mantener la coherencia de los enlaces, adems de seguir manteniendo la
estructura como un rbol binario de bsqueda. La solucin consiste en sustituir la
informacin del nodo que se borra por el de una de las hojas, y borrar a continuacin
dicha hoja. Puede ser cualquier hoja? No, debe ser la que contenga una de estas dos
claves:
la mayor de las claves menores al nodo que se borra. Suponer que se quiere borrar
el nodo 4 del rbol de la figura 5. Se sustituir la clave 4 por la clave 2.
la menor de las claves mayores al nodo que se borra. Suponer que se quiere borrar
el nodo 4 del rbol de la figura 5. Se sustituir la clave 4 por la clave 5.
El algoritmo de borrado que se implementa a continuacin realiza la sustitucin por la
mayor de las claves menores, (aunque se puede escoger la otra opcin sin prdida de
generalidad). Para lograr esto es necesario descender primero a la izquierda del nodo
que se va a borrar, y despus avanzar siempre a la derecha hasta encontrar un nodo
hoja. A continuacin se muestra grficamente el proceso de borrar el nodo de clave 4:

Codificacin: el procedimiento sustituir es el que desciende por el rbol cuando se da el

caso del nodo con descencientes por ambas ramas.
void borrar(tarbol **a, int elem)
{
void sustituir(tarbol **a, tarbol **aux);
tarbol *aux;
if (*a == NULL) /* no existe la clave */
return;
if ((*a)->clave < elem) borrar(&(*a)->der, elem);
else if ((*a)->clave > elem) borrar(&(*a)->izq, elem);
else if ((*a)->clave == elem) {
aux = *a;
if ((*a)->izq == NULL) *a = (*a)->der;
else if ((*a)->der == NULL) *a = (*a)->izq;
else sustituir(&(*a)->izq, &aux); /* se sustituye por
la mayor de las menores */
free(aux);
}

Ficheros relacionados
Implementacin de algunas de las operaciones sobre rboles binarios.

Ejercicio resuelto

Escribir una funcin que devuelva el numero de nodos de un rbol binario. Una
solucin recursiva puede ser la siguiente:
funcion nodos(arbol : tipoArbol) : devuelve entero;
inicio
si arbol = vacio entonces devolver 0;
en otro caso devolver (1 + nodos(subarbol_izq) + nodos(subarbol_der));
fin
Adaptarlo para que detecte si un rbol es perfectamente equilibrado o no.

Problemas propuestos
rboles binarios: OIE 98. (Enunciado)

Aplicacin prctica de un rbol

Se tiene un fichero de texto ASCII. Para este propsito puede servir cualquier libro
electrnico de la librera Gutenberg o Cervantes, que suelen tener varios cientos de
miles de palabras. El objetivo es clasificar todas las palabras, es decir, determinar que
palabras aparecen, y cuantas veces aparece cada una. Palabras como 'nio'-'nia',
'vengo'-'vienes' etc, se consideran diferentes por simplificar el problema.
Escribir un programa, que recibiendo como entrada un texto, realice la clasificacin
descrita anteriormente.
Ejemplo:
Texto: "a b'a c. hola, adios, hola"
La salida que produce es la siguiente:
a2
adios 1
b1
c1
hola 2
Ntese que el empleo de una lista enlazada ordenada no es una buena solucin. Si se
obtienen hasta 20.000 palabras diferentes, por decir un nmero, localizar una palabra
cualquiera puede ser, y en general lo ser, muy costoso en tiempo. Se puede hacer
una implementacin por pura curiosidad para evaluar el tiempo de ejecucin, pero no
merece la pena.
La solucin pasa por emplear un rbol binario de bsqueda para insertar las claves. El
valor de log(20.000) es aproximadamente de 14. Eso quiere decir que localizar una
palabra entre 20.000 llevara en el peor caso unos 14 accesos. El contraste con el
empleo de una lista es simplemente abismal. Por supuesto, como se ha comentado
anteriormente el rbol no va a estar perfectamente equilibrado, pero nadie escribe
novelas manteniendo el orden lexicogrfico (como un diccionario) entre las palabras,

asi que no se obtendr nunca un rbol muy degenerado. Lo que est claro es que
cualquier evolucin del rbol siempre ser mejor que el empleo de una lista.
Por ltimo, una vez realizada la lectura de los datos, slo queda hacer un recorrido en
orden central del rbol y se obtendr la solucin pedida en cuestin de segundos.
Una posible definicin de la estructura rbol es la siguiente:
typedef struct tarbol
{
char clave[MAXPALABRA];
int contador; /* numero de apariciones. Iniciar a 0 */
struct tarbol *izq,
*der;
} tarbol;