TEMA 1: ÁRBOLES

INTRODUCCIÓN
Los árboles, en informática y ciencias de la computación, son estructuras de datos
homogéneas, no lineales, porque cada elemento, o nodo, puede estar vinculado a cero, uno
o más elementos.
Cada nodo del árbol contiene un área de datos y otra de enlaces; el área de datos puede
contener una o más variables o referencias a objetos; el área de enlaces contiene dos o más
referencias que apuntan a otros nodos similares al nodo origen. Se denomina árbol por la
similitud con un árbol invertido.
Los árboles facilitan la resolución de una variedad de problemas y son muy importantes en el
desarrollo de software. Algunas aplicaciones de los árboles son: búsquedas optimizadas de
datos, análisis sintáctico de lenguajes de programación, evaluación de expresiones
matemáticas, bases de inferencia, toma de decisiones, representación interna de páginas
web, representación taxonómica de animales y vegetales, etc., etc.

DEFINICIÓN
Un árbol se define como: una estructura de datos vacía o bien como una estructura con un
nodo de datos, ligado a cero o más subárboles disjuntos.
La siguiente figura representa un grafo:

La terminología empleada para describir los diferentes elementos de un árbol es:

 Nodo, elemento que contiene uno o más datos de tipo primitivo y/o una o más
referencias a objetos, además contiene dos o más referencias a otros nodos similares.

1
 Raíz, es el nodo de inicio del árbol, el que no tiene antecesor. En el ejemplo anterior,
el nodo raíz contiene el dato 65

 Árbol vacío, árbol que no tiene nodos o que tiene cero nodos.

 Nivel o profundidad de un nodo, número de arcos que se deben recorrer desde la raíz
hasta el nodo en cuestión. Por convención el nivel del nodo raíz es 0.

 Nodo padre o ascendiente, es el nodo del nivel anterior, vinculado al nodo actual. Por
ejemplo, el nodo con el dato 32 tiene como padre al nodo con el dato 46. El nodo raíz
es el único nodo que no tiene un nodo padre.
 Camino, es la secuencia de nodos consecutivos y vinculados entre sí, que empiezan
en un nodo cualquiera y terminan en un nodo descendiente. Por ejemplo, el camino
entre el nodo 79 y el 32 es: 79 46 32; por otra parte, no existe un camino entre los
nodos 25 y 32, por ejemplo.
 Longitud de camino entre dos nodos, es el número de enlaces que se debe recorrer
desde un nodo hasta otro. La longitud de camino de los nodos 79 y 14 es 2. La
2
 longitud de camino entre los nodos 58 y 79 no existe, porque no hay un camino entre
ambos nodos.
 Altura de un nodo, es la longitud de camino más largo, que empieza en ese nodo y
termina en una hoja. La altura del nodo 46 es 2. La altura del nodo 58 es 2.
 Altura del árbol, es la altura del nodo raíz. La altura del árbol del ejemplo es 4
 Anchura de un árbol, es el mayor de los números de nodos presente en los diferentes
niveles del árbol. La anchura del árbol es 5, que corresponde al nivel 2 y al nivel 3
 Ancestro de un nodo, cualquier nodo que se encuentre en el camino a partir del nodo
raíz hasta el nodo padre del nodo en cuestión. El nodo 32 tiene como ancestros a los
nodos 65, 79 y 46.
 Sucesor o hijo, nodo descendiente directo, ubicado en el siguiente nivel. Los hijos del
nodo 46 son los nodos 32 y 14
 Hermanos, nodos que tienen un mismo nodo padre. Los nodos 32 y 14 son hermanos
 Hoja o nodo terminal, es aquel nodo que no tiene descendientes. Los nodos 73, 43,
91, 81 y 14 son nodos hoja.
 Nodo interno, nodo que no es raíz ni hoja. Los nodos 58, 79, 25, 96, 12, 95, 46 y 32
son nodos internos.
 Grado de un nodo, número de descendientes directos del nodo. El grado del nodo 79
es 2, mientras que el grado 43 es 0.
 Grado de un árbol, es el mayor de los grados de los diferentes nodos de un árbol. El
grado del árbol de la imagen anterior es 3.
 Tamaño o peso de un árbol, número total de nodos del árbol. El árbol anterior tiene
tamaño 14
 Subárbol o rama, árbol contenido a partir de un nodo cualquiera, excepto el nodo raíz.

CLASIFICACIÓN DE LOS ÁRBOLES

Los árboles se clasifican de diferentes maneras, entre ellas se destacan los árboles binarios
o de grado 2 por su versatilidad y capacidad de representar a árboles que no son binarios.
Los árboles binarios se subdividen en:
 Árbol binario estricto, árbol cuyos nodos cuentan con dos nodos descendientes
obligatoriamente, a excepción de los nodos terminales.
 Árbol binario de búsqueda, es el árbol que tiene los datos de todos los nodos
ordenados, de acuerdo a un determinado criterio.
 Árbol AVL (Andelson Velskii y Landis), árbol binario en el que todos los nodos
cumplen que sus subárboles tienen una diferencia de altura máxima igual a uno.

3
De los árboles indicados, el árbol binario de búsqueda u ordenado, es el más empleado, por
su simplicidad de implementación.

FORMAS DE REPRESENTACIÓN
Los árboles pueden representarse de diferentes formas:
 Mediante un grafo, por ejemplo:

 Mediante paréntesis anidados

m( e( a, i( g, k) ), q( , v( s, ))
 Mediante diagramas de Venn

 Mediante diagramas de columnas

4
En los lenguajes de programación, los árboles se pueden implementar mediante:
 arreglos (estructuras estáticas)
 referencias o punteros, (estructuras dinámicas).

ÁRBOLES BINARIOS
Son los árboles de grado 2, es decir cada nodo tiene dos descendientes como máximo, a los
que se denominan subárbol izquierdo y subárbol derecho.

ÁRBOLES BINARIOS DE BÚSQUEDA

Un árbol binario de búsqueda es aquel que tiene sus elementos o datos ordenados de
acuerdo a algún criterio ordinal. El árbol binario de búsqueda clásico es aquel en que el
subárbol izquierdo tiene nodos con valores menores al valor del nodo de referencia, mientras
que el subárbol derecho tiene nodos con valores mayores a éste.

5
Un árbol binario de búsqueda presenta la ventaja de requerir mucho menos comparaciones
que una búsqueda en una lista enlazada, principalmente cuando el árbol se encuentra
equilibrado o balanceado. Además, la inserción y eliminación de nodos es más directa que
en las listas enlazadas y mucho más rápida que en listas estáticas o basadas en arreglos. Un
análisis de complejidad correspondiente a las operaciones de búsqueda, inserción y
eliminación, da por resultado O(log(n)).

IMPLEMENTACIÓN DE UN ARBOL
Implementación con arreglos
Un árbol puede implementarse mediante arreglos o mediante punteros y/o referencias.
La representación de un árbol binario con arreglos, contempla un arreglo unidimensional
cuyos elementos o celdas pueden contener datos primitivos o referencias a objetos. La
estructura jerárquica del árbol está definida por los índices del arreglo, correspondiendo el
índice 0 para el nodo raíz; para cualquier nodo de índice i, su nodo descendiente izquierdo
tiene el índice 2*i+1 y su nodo descendiente derecho tiene el índice 2*i+2; mientras que el
nodo padre tiene el índice igual a la parte entera de (i-1)/2. Por ejemplo:

Si se implementa un árbol que tiene nodos hasta el nivel: n, el tamaño del arreglo necesario
será: 2n+1-1; por ejemplo, un árbol que tenga nodos hasta el nivel 4 requerirá un arreglo de
tamaño: 31 celdas; para un árbol de nivel 9, el tamaño del arreglo será: 2047 celdas.
Además, cuando los datos son de un tipo primitivo, es fundamental emplear un valor
centinela, que indique la inexistencia de un dato válido en esa celda.
La principal desventaja de la implementación de árboles mediante un arreglo unidimensional,
es que se debe conocer el máximo nivel que tendrá el árbol, para realizar un
dimensionamiento adecuado del tamaño de memoria, lo que significa una reserva de
memoria, aunque el árbol esté vacío.

6
Implementación con referencias
La implementación de un árbol mediante punteros o referencias requiere la especificación de
una clase correspondiente a un elemento o nodo, a la que se denominará: Nodo, la que
conviene definirla como una clase interna, que contendrá, al menos, los siguientes atributos:
 Dato, que contendrá un elemento de la clase Object.
 Dos referencias a nodos de la clase Nodo, denominados der e izq.
Los métodos de esta clase interna se limitan a sus constructores y a sus métodos getters y
setters de ser necesarios.
El árbol propiamente dicho contendrá básicamente un atributo que será una referencia al
nodo raíz del árbol.

RECORRIDOS DE ÁRBOLES
El recorrido de los árboles es una operación fundamental y consiste en visitar cada nodo una
vez de forma sistemática. El recorrido de un árbol puede realizarse en profundidad y en
anchura.

RECORRIDO EN PROFUNDIDAD
Consiste en el recorrido a través de las ramas, expandiendo cada nodo a su descendiente,
hasta alcanzar la primera hoja, luego se recorre por otra rama hasta llegar a otra hoja y así
sucesivamente.
Existen tres formas de recorrer un árbol en profundidad:
 Recorrido pre orden
 Recorrido en orden
 Recorrido post orden
Desde el punto de vista matemático, el recorrido pre orden produce la notación polaca prefija,
el recorrido algebraico tradicional y el recorrido post orden produce la notación polaca postfija
RPN.
Por ejemplo, dado el siguiente árbol, a continuación, se muestra la secuencia de los datos
realizando los diferentes recorridos:

7
Recorrido en pre orden
El recorrido en pre orden consiste en: procesar el nodo raíz, luego recorrer en pre orden el
subárbol izquierdo y por último recorrer en pre orden subárbol derecho. Aplicando este
procedimiento al árbol anterior, se tiene la siguiente secuencia de datos: A B D E C F G
Recorrido en orden
El recorrido pre orden consiste en, inicialmente recorrer en orden el subárbol izquierdo, luego
acceder y procesar el nodo raíz y por último recorrer en orden el subárbol derecho. Aplicando
este procedimiento al árbol anterior, se tiene la siguiente secuencia de datos: D B E A F C G
Recorrido en post orden
El recorrido post orden consiste en, inicialmente recorrer en post orden el subárbol izquierdo,
luego recorrer en post orden subárbol derecho y por último acceder y procesar el nodo raíz.
Aplicando este procedimiento al árbol anterior, se obtienen la secuencia: D E B F G C A

RECORRIDO EN AMPLITUD O ANCHURA

El recorrido en amplitud o anchura consiste en visitar los diferentes nodos del árbol por
niveles; primero se visita el nodo del nivel 1 (solo el nodo raíz), luego todos los nodos de
nivel 2, de izquierda a derecha, luego los nodos del nivel 3 de izquierda a derecha, y así
sucesivamente hasta el último nivel.
Aplicando el recorrido en amplitud o anchura al grafo anterior, se tiene la siguiente secuencia
de datos:
A, B, C, D, E, F, G
El recorrido en amplitud se implementa de forma iterativa, partiendo del nodo raíz y utilizando
una cola de referencias a los nodos del árbol, como estructura de datos auxiliar, en la que se
almacenan la referencia del subárbol izquierdo y luego la referencia del subárbol derecho de
cada nodo accedido y de donde se extraen las referencias a los nodos que a continuación
serán procesados.

ELIMINACIÓN DE UN NODO
La eliminación de un nodo, en un árbol binario de búsqueda, es una operación que tiene
cierta complejidad; para sobrellevar de manera más simple, esta operación se divide en los
siguientes tres casos:
 Eliminación de un nodo hoja
 Eliminación de un nodo con un descendiente
 Eliminación de un nodo con dos descendientes
La eliminación de un nodo hoja es trivial, únicamente se debe acceder al nodo padre y se
cambia la referencia que accede al nodo hoja a null. Por ejemplo, en la siguiente figura se

8
pretende eliminar el nodo 12, luego, a través de la referencia aux que apunta al nodo padre
(nodo 9), se asigna null a la referencia derecha que apunta al nodo 12.

La eliminación de un nodo con un solo descendiente implica cambiar la referencia del nodo
padre que accede al nodo a eliminar, al nodo hijo de éste. Por ejemplo, en la siguiente figura
se eliminará el nodo 9, para lo que se asignará la referencia derecha del nodo 7 (padre de 9)
al nodo hijo (12) del nodo a eliminar (9).

La eliminación de un nodo con dos descendientes implica buscar en el subárbol derecho del
nodo a eliminar, el nodo que se ubica más a la izquierda (nodo que contiene el menor dato
de la rama derecha del nodo a eliminar) y copiar el valor de éste en el nodo a eliminar, luego
se elimina el nodo más a la izquierda mediante uno de los casos descritos anteriormente. Por
ejemplo, para eliminar el nodo 7 del diagrama anterior, se busca el nodo más a la izquierda
del subárbol derecho del nodo 7, en este caso es el nodo 9; luego se copia el valor del nodo
9 al nodo 7 y por último se elimina el nodo 9, mediante el caso 1 por tener un solo hijo.

9
O si se desea eliminar el nodo 15, se accede al nodo más a la izquierda del subárbol derecho
de 15, en este caso el nodo 17, se copia su valor por 15 y se elimina el nodo 17.

ÁRBOL BALANCEADO AVL

Un árbol balanceado es un árbol binario de búsqueda que se caracteriza porque, para todos
los nodos, la altura del subárbol derecho no difiere en más de una unidad respecto al
subárbol izquierdo, es decir:
Un árbol balanceado es sumamente eficiente para la búsqueda binaria.
Para lograr la condición de equilibrio o balanceo, la inserción y eliminación de nodos se ha de
realizar de forma muy particular. En caso de que alguna de estas operaciones rompa la
condición de equilibrio, se debe realizar una serie de rotaciones de los nodos.
Las operaciones básicas de un árbol balanceado son:
 esVacio(); determina si el árbol está vacío
 insertar(dato); inserta el dato en el árbol ordenado
 eliminar(dato); elimina el dato en el árbol ordenado
 rotaciónIzq(); rotación a la izquierda
 rotaciónDer(); rotación a la derecha

10
ARBOL ENHEBRADO O ENHILADO

La ventaja de este tipo de representación no es sólo el mejor aprovechamiento de la

memoria disponible, sino por la posibilidad de un acceso rápido al sucesor (o al

11
predecesor) de un nodo, Para poder manejar correctamente toda la información de la que
se dispone en la representación hilvanada (con hilos) del árbol binario, es necesario
poder distinguir entre lo que son punteros normales, que representan las relaciones
reales entre los nodos, y lo que son hilos. Esto se puede hacer añadiendo dos campos
booleanos a la representación de los nodos del árbol. Estos nuevos campos indicarán si
los enlaces izquierdo y derecho son hilos o no.

12