Download Árboles - Departamento de Ingeniería de Sistemas e Industrial

3. ÁRBOLES
Una estructura muy utilizada en el manejo de información es la estructura de árbol. Caracteriza a los
sistemas jerárquicos y se emplea principalmente en el procesamiento de datos para la toma de
decisiones: la clasificación y el agrupamiento (clustering). Los árboles son estructuras no lineales y
dinámicas empleadas en muchas aplicaciones computacionales, en especial en la construcción de
compiladores, en minería de datos, lingüística computacional,... Un árbol es una estructura en la que
cada nodo puede apuntar (encadenar) a uno o varios nodos.
Definición. Un árbol es un conjunto finito de nodos R, tal que:
a. Hay un nodo principal llamado raíz.
b. Los otros nodos se particionan en S subconjuntos R1, R2, ..., Rs que a la vez son también árboles.
Esta definición es algo recursiva y puede simplificarse como: un árbol es una estructura compuesta por
un nodo raíz y varios árboles encadenados al nodo raíz.
Para su proceso computacional varias son las características que poseen los árboles:
1.
Todo árbol que no es vacío, tiene un nodo raíz único. Es el nodo usado para referirnos al
árbol1.
2.
Un nodo P es descendiente directo de un nodo H, si el nodo H tiene un pointer
(encadenamiento) a P. H es padre de P.
3.
Un nodo Z es antecesor directo de un nodo W, si el nodo Z tiene un pointer a W. Z es padre
de W2 o W es hijo de Z.
4.
Los nodos que son hijos del mismo padre, se dicen hermanos.
5.
Todo nodo que no posee ramificaciones (hijos), se llama terminal o nodo hoja.
6.
Orden es el número potencial de descendientes que puede tener un nodo.
7.
Nivel es el número de arcos que deben ser recorridos para llegar a un determinado nodo
desde la raíz. Por definición la raíz tiene nivel 0.
8.
Altura del árbol es el máximo número de nivel que existe en el árbol.
1
Es importante conservar siempre el nodo raíz ya que es el nodo a partir del cual se desarrolla el árbol, si se
pierde este nodo, se perderá el acceso al árbol.
2
Frecuentemente, para hacer más fácil el recorrido por el árbol, se añade un puntero a cada nodo que encadene
el nodo padre.
44
9.
Grado es el número de subárboles que salen de un nodo.
La escritura (representación) de un árbol puede ser de diferentes maneras, según la utilización o
aplicación que se le va a dar; puede ser en forma de estructura descendiente, como una multilista,
utilizando barras, o cuadros (ver figura 3.1).
Figura 3.1 Representación de Árboles
Un ejemplo de estructura de árbol es el sistema de directorios y ficheros en el disco, en este caso se
considera que los ficheros son hojas y los directorios ramas. Otro ejemplo podría ser la tabla de
contenido de un libro. Igualmente, los organigramas de mando de las organizaciones y los árboles
genealógicos.
Los árboles se pueden clasificar de diferente manera y por diferentes conceptos; algunas clases más
usadas en computación son:
Árboles n-arios
Los grados de los nodos en un árbol son mayores o iguales a dos. Si el grado de todos los nodos es
dos, se dice que el árbol es binario. Si el grado de todos los nodos es tres se dice que el árbol es
ternario, y así sucesivamente3. Si todos los nodos tienen diferente grado, simplemente se dice que no es
árbol binario.
3
Los árboles con los que se trabajan en estructuras de datos tienen la característica de que todos los nodos del
árbol tienen el mismo número de campos. Igualmente, cada nodo sólo puede ser apuntado por otro nodo, es decir,
cada nodo sólo tendrá un padre.
Luis Carlos Torres Soler
Estructuras de Datos
45
Las estructuras de datos manejan árboles binarios (grado máximo 2), sin embargo, cualquier árbol
puede ser convertido a binario. Para ello, el hijo izquierdo va a la izquierda, el hermano más próximo a
la derecha, los demás hermanos a la derecha del hermano anterior, y así sucesivamente.
Figura 3.2 Árbol binario.
Un árbol A es binario, si cada nodo del árbol posee a lo más dos subárboles disyuntos A1 y A2
llamados subárbol izquierdo y subárbol derecho.
Figura 3.3 Paso del árbol no binario (fig. 3.2) a uno binario.
La definición típica en C de un nodo es:
struct nodo {
int info;
struct nodo *ilink;
struct nodo *dlink;
}
o generalizando más:
#define grado 2
struct nodo {
int info;
struct nodo *link[grado]
}
Facultad de Ingeniería
46
Figura 3.4 Ejemplos de árboles.
Árboles homogéneos
Un árbol homogéneo es aquel en el que todos sus nodos tienen la misma conformación, es decir, cada
nodo que conforma el árbol tiene igual número de campos.
Figura 3.5 Ejemplo de árboles completos.
Árboles completos
Un árbol completo se caracteriza porque todos sus nodos terminales tienen la misma altura.
Un árbol binario se dice que es completo, si todos los nodos del árbol, excepto los del último nivel
tienen dos hijos: subárbol izquierdo y subárbol derecho (ver figura 3.3).
Árboles ordenados
Un árbol ordenado se caracteriza porque la posición relativa de los subárboles es fija, es decir, no se
pueden intercambiar. Esto sucede porque el subárbol depende de una clave de la información. Cuando
el árbol se lee en inorden, las claves aparecen en orden ascendente.
Sea la lista de claves: 60, 30, 85, 20, 50, 90, 75, 40, 80, 70, 95, 45, 83, 73. El árbol respectivo está
dado en la figura 3.6:
Dos subárboles son distintos cuando sus estructuras son diferentes. Los árboles de la figura 3.4 son
distintos.
Dos árboles son similares cuando sus estructuras son idénticas pero la información de los nodos es
diferente.
Luis Carlos Torres Soler
Estructuras de Datos
Dos árboles son equivalentes si son similares y poseen la misma información.
47
Las operaciones en árboles son similares a las empleadas en listas o pilas:
a. Añadir o insertar elementos.
b. Buscar o localizar elementos.
c. Borrar elementos.
d. Leer (recorrer) el árbol completamente.
Figura 3.6 Ejemplo de árbol de búsqueda binario.
Los algoritmos de inserción y borrado dependen en gran medida del tipo de árbol que se está
implementando.
El modo evidente de moverse a través del árbol es siguiendo los punteros. Esas lecturas dependen en
gran medida del tipo y propósito del árbol, pero hay ciertos recorridos usados más frecuentemente.
Los árboles binarios se pueden leer de tres formas: inorden, preorden y posorden. Lo que diferencia
los distintos métodos de recorrer el árbol no es el sistema de hacerlo, sino el momento elegido para
procesar la información del nodo con relación a los recorridos en cada una de las ramas.
La lectura en inorden se realiza leyendo primero el hijo izquierdo, luego la raíz, y por último el hijo
derecho.
La lectura en preorden se realiza leyendo primero la raíz, luego el hijo izquierdo, y por último el hijo
derecho.
La lectura en posorden se realiza leyendo primero el hijo izquierdo, luego el hijo derecho y por último
la raíz.
Las tres lecturas se suelen implementar mediante recursividad. Se parte del nodo raíz, LeerArbol(raíz);
la función LeerArbol, aplicando recursividad, se vuelve muy sencilla para invocarla de nuevo para
cada una de las ramas.
void LeerArbol(arbol a) {
Facultad de Ingeniería
if (a== null) return;
LeerArbol(a->rama[0]);
LeerArbol(a->rama[1]);
48
}
Lectura en Pre-orden
void PreOrden(arbol a) {
if (a== null) return;
Procesar(info);
LeerArbol(a->rama[0]);
LeerArbol(a->rama[1]);
}
Lectura In-orden
void InOrden(arbol a) {
if (a== null) return;
LeerArbol(a->rama[0]);
Procesar(info);
LeerArbol(a->rama[1]);
}
Lectura Pos-orden
void PosOrden(arbol a) {
if (a== null) return;
LeerArbol(a->rama[0]);
LeerArbol(a->rama[1]);
Procesar(info);
}
Los campos de un árbol binario para su lectura se notan: ilink (link izquierdo), info (información) y
dlink (link derecho).
Figura 3.7. Estructura de un nodo.
Seudo-algoritmo para la lectura de un árbol binario en Pre-orden:
PREORDEN(arbol)
sw=0
p <-- arbol
MQ sw = 0
SI p<> null TH dato <-- info.p
Luis Carlos Torres Soler
Estructuras de Datos
stack <= p
p <-- ilink.p
SN SI stack = null TH sw=1
SN p <= stack
p <-- dlink.p
FSI
49
FSI
FMQ
FINPREORDEN()
Seudo-algoritmo para la lectura de un árbol binario en In-orden:
INORDEN(arbol)
sw=0
p <-- arbol
MQ sw = 0
SI p<> null TH stack <== p
p <-- ilink.p
SN SI stack = null TH sw=1
SN p <= stack
dato <-- info.p
p <-- dlink.p
FSI
FSI
FMQ
FININORDEN()
=========================
stack <= p significa
SI dispo = null TH UNDERFLOW
SI stack = null TH stack <-- dispo
dispo <-- link.dispo
link.stack = null
SN s <-- dispo
dispo <-- link.dispo
link.s <-- stack
stack <-- s
FSI
FSI
Es decir, se está controlando y haciendo los movimientos necesarios para manejar el espacio
disponible y las consideraciones de stack. Similarmente debe considerarse p <= stack.
SI stack = null TH OVERFLOW
SI dispo = null TH dispo <- stack
Facultad de Ingeniería
link.dispo <- null
stack <- link.stack
SN s <-- stack
stack <- link.stack
link.s <-- dispo
dispo <-- s
50
FSI
FSI
Seudo-algoritmo para la lectura de un árbol binario en Pos-orden:
POSORDEN(arbol)
sw=0
p <-- arbol
MQ sw = 0
SI p<> null TH stack <= p
p <-- ilink.p
st=0
SN SI stack = null TH sw=1
SN p <= stack
SI st= 1 TH dato <-- info.p
FSI
p <-- dlink.p
st=1
FSI
FSI
FMQ
FINPOSORDEN()
Un conjunto de árboles, se llama bosque. El bosque también puede convertirse a árbol binario con los
siguientes pasos:
a.
Como raíz del árbol binario se toma la raíz del primer árbol.
b.
Como subárbol izquierdo se toma el subárbol izquierdo de cada árbol
Luis Carlos Torres Soler
Estructuras de Datos
c.
51
Figura 3.8. Conversión de bosque a árbol.
Como subárbol derecho se toma el árbol hermano de nivel.
Interesa en computación los árboles ordenados porque presentan mayor interés desde el punto de vista
de tipo abstracto de dato (TAD), y los que tienen mayores 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: in-orden, pre-orden o pos-orden. 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:
a. Árboles binarios de búsqueda (ABB): son árboles de grado 2 que mantienen una secuencia ordenada
si se recorren en inorden.
Facultad de Ingeniería
52
b. Árboles AVL: son árboles binarios de búsqueda equilibrados, es decir, los niveles de cada rama para
cualquier nodo no difiere en más de 1.
Árboles binarios de búsqueda (ABB)
Se trata de árboles de grado 2 en los que se cumple que para cada nodo, el valor de información del
subárbol izquierdo es menor que la información del nodo y a su vez ésta información menor que la que
hay en el subárbol derecho.
Proceso para generar ABB
Se cuenta con un conjunto de nodos con información clave donde cada una puede ser comparada de
ser menor o mayor con respecto a otra. Se crea un árbol con las siguientes normas:
a. El primer nodo es un nodo raíz.
b. Si la información del nuevo nodo es menor que la del nodo raíz, va a la izquierda.
c. Si la información del nuevo nodo es mayor que la del nodo raíz, va a la derecha.
Algoritmo para generar un árbol binario de búsqueda:
Alg_IABB()
nodo <= Lista
MQ Lista <> vacío
SI árbol = null TH: árbol <= nodo
SN: xv <= árbol
SI info.xv > info.nodo
TH: SI ilink.xv = null TH: ilink.xv <= nodo
SN: xv <= ilink.xv
FSI
FSI
SI info.xv < info.nodo
TH: SI dlink.xv = null TH: dlink.xv <= nodo
F: xv <= dlink.xv
FSI
FSI
SI info.xv = info.nodo V: "esta clave ya existe", SALIR
FSI
FSI
FMQ
Fin_Alg_IABB()
Operaciones en ABB
Luis Carlos Torres Soler
Estructuras de Datos
53
Las operaciones son las ya comunes de las demás estructuras de datos, además de otras propias de los
árboles:
a. Buscar un elemento (información).
b. Insertar un elemento.
c. Borrar un elemento.
d. Movimiento a través del árbol:
1. Izquierda.
2. Derecha.
3. Raíz.
e. Conocer información:
1. Comprobar si un árbol está vacío.
2. Calcular el número de nodos.
3. Calcular la altura de un nodo.
4. Calcular la altura del árbol.
Buscar un elemento
Partiendo siempre del nodo raíz, se busca un elemento de forma recursiva4.
SI árbol=null V: "el nodo no está en el árbol", SALIR
SI info.raíz = META V: informar, EXITO
SI info.raíz > META V: buscar_en_árbol_izquierdo.
F: buscar_en_árbol_derecho
Insertar un elemento
Para insertar un elemento hay que emplear la función de búsqueda. Si el elemento está en el árbol no
se inserta. Si no lo está se inserta en el orden establecido.
Se requiere de variable auxiliar para referenciar el padre de un nodo actual.
xv=null
nodo=raíz
MQ nodo <> vacío o se halle elemento (META)
SI info.nodo > META V: xv=nodo
nodo <- árbol_izquierdo(nodo)
F: SI info.nodo < META V: xv=nodo
nodo <- árbol_derecho(nodo)
FSI
FSI
SI info.nodo <> null V: "este es META", SALIR
FMQ
SI xv=null V: "árbol vacío", crear árbol con info.raíz=META
F: SI META<info.padre V: META es info.subárbol_izquierdo de xv
4
El valor de retorno de la búsqueda en un ABB será la dirección del nodo buscado, o null, si no se halla.
Facultad de Ingeniería
F: META es info.subarbol_derecho de xv
54
FSI
FSI
Borrar un elemento
Para borrar un elemento también hay que emplear el algoritmo de búsqueda. Si el elemento buscado no
está en el árbol, no hay que borrar. Si está, hay dos casos posibles:
a. Es nodo hoja: se borra directamente.
b. Es nodo rama: se intercambia información para continuar con el árbol.
Figura 3.9 Ejemplo de árbol de búsqueda binario.
Se utiliza un puntero auxiliar para conservar la referencia al padre del nodo raíz actual.
xv=null
nodo=raíz
SI nodo = null V: "árbol sin información", SALIR FSI
SI info.nodo = META V: se esta ante los casos de :
a. El nodo es una hoja.
SI xv = null V: árbol <- null
F: SI nodo es rama derecha de xv V: árbol_derecho(nodo) <- null
F: SI nodo es rama izquierda de xv V: árbol_izquierdo(nodo) <- null
FSI
FSI
FSI
b. El nodo es una rama.
Se busca el nodo más a la izquierda del árbol derecho de nodo o el más a la
derecha del árbol izquierdo.
xv <- padre(nodo)
intercambiar información de nodo y el "nodo" hallado.
Borrar nodo
Luis Carlos Torres Soler
Estructuras de Datos
FSI
SI info.nodo > META V: buscar_arbol_izquierdo(nodo)
F. buscar_arbol_derecho(nodo)
FSI
55
Movimientos a través del árbol
El árbol siempre se referencia mediante un puntero al nodo raíz. Para movernos a través del árbol debe
emplearse variables (punteros) auxiliares, de modo que desde cualquier nodo los movimientos posibles
serán: ir al árbol izquierdo o ir al árbol derecho.
Información
Por tratarse de una estructura dinámica, un árbol, es necesario conocer alguna información del árbol
para posteriormente trabajar de una forma más eficiente.
Calcular el número de nodos
Es sencillo, se cuentan los nodos recurriendo a cualquiera de los modos de recorrer un árbol: in-orden,
pre-orden o pos-orden.
Comprobar si el nodo es hoja
Se comprueba si tanto el árbol izquierdo como el árbol derecho de un nodo son vacíos.
Calcular la altura de un nodo
Se cuenta con una variable que cuenta los pasos que se avanza hacia un nodo al emplear el algoritmo
de búsqueda.
xx <- árbol
altura = 0
SI info.xx = META V: "altura de.." nodo es altura SALIR
F: altura = altura + 1
SI info.xx < META V: xx <- arbol_derecho(xx)
F: xx <- arbol_izquierdo(xx)
FSI
FSI
Calcular la altura de un árbol
La altura de un árbol es la mayor altura en la que pueda estar un nodo. Se recorre todo el árbol.
Facultad de Ingeniería
Recorrido del árbol en pos-orden
altura=0
56
Figura 3.10 Árbol de expresión aritmética.
Cada vez que se inicia una nueva rama de nivel, incrementar altura
Al procesar las dos ramas, comprobar altura con nueva altura, cambiar valor se es
necesario.
Árboles degenerados
Los ABB algunas veces presentan inconvenientes. Al construirlo a partir de una lista ordenada resulta
un árbol que solamente tiene árboles derechos, a esto se le llama ABB degenerado.
Representación de expresiones algebraicas
Una aplicación particular de los árboles binarios es la representación de expresiones algebraicas. Su
construcción es a partir de la notación posfija5.
Sea la expresión: x=z/r*y+(z-(s+u)*s), el árbol correspondiente está en la figura 3.10.
Árboles AVL
El comportamiento de los ABB no es siempre tan bueno como nos gustaría. Para minimizar el
problema de los ABB desequilibrados, sea cual sea el grado de desequilibrio que tengan, hay que
recurrir a algoritmos para equilibrar los árboles. En general, estos algoritmos, crean una lista mediante
la lectura en inorden del árbol, y luego vuelven a reconstruirlo equilibrado. Conociendo el número de
elementos es algo fácil. El problema de estos algoritmos es que requieren explorar y reconstruir todo el
árbol cada vez que se inserta o se elimina un elemento, de modo que lo que se gana al acortar las
búsquedas, teniendo que hacer menos comparaciones, se pierde equilibrando el árbol. Para resolver
este inconveniente puede recurrirse a los árboles AVL.
5
Dos o más árboles binarios diferentes de expresiones algebraicas pueden llegar a tener la misma lectura en inorden, pero nunca la misma lectura en pos-orden.
Luis Carlos Torres Soler
Estructuras de Datos
57
Definición. Un árbol AVL (llamado así por las iniciales de sus inventores: Adelson-VelskiiLandis) es un árbol binario de búsqueda en el que para cada nodo, las alturas de sus subárboles
izquierdo y derecho no difieren en más de 1.
No se trata de árboles perfectamente equilibrados, pero si son lo suficientemente equilibrados como
para que su comportamiento sea lo bastante bueno para usarlos donde los ABB no garantizan tiempos
de búsqueda óptimos.
El algoritmo para mantener un árbol AVL equilibrado se basa en reequilibrados locales, de modo que
no es necesario explorar todo el árbol después de cada inserción o borrado.
Operaciones en AVL
Los árboles AVL son también ABB, de modo que mantienen todas las operaciones que poseen éstos.
Las nuevas operaciones son las de equilibrar el árbol, pero eso se hace como parte de las operaciones
de inserción y borrado.
Factor de equilibrio. Cada nodo, además de la información que se pretende almacenar, los dos
punteros a los árboles derecho e izquierdo, además debe incluir un campo nuevo: el factor de
equilibrio.
El factor de equilibrio es la diferencia entre las alturas del árbol derecho y el izquierdo:
FE= altura subárbol derecho - altura subárbol izquierdo; por definición, para un árbol AVL, este
valor debe ser -1, 0 o 1.
El reequilibrio se realiza mediante rotaciones.
Rotación simple a la derecha (RSD):
Esta rotación se usa cuando el subárbol izquierdo de un nodo sea 2 unidades más alto que el derecho,
es decir, cuando su FE sea de -2. Además, la raíz del subárbol izquierdo tenga un FE de -1, es decir,
que esté cargado a la izquierda.
Se procede del siguiente modo:
- Se nota P al nodo que muestra el desequilibrio, el que tiene FE=-2. Se nota Q al nodo raíz del
subárbol izquierdo de P. Además, se nota X al subárbol izquierdo de Q, Y al subárbol derecho de Q y
W al subárbol derecho de P.
En la figura 3.11 se puede observar que tanto Y como W tienen la misma altura (n), y X es una unidad
mayor (n+1). Esto hace que FE=-1 de Q, la altura del subárbol que tiene Q como raíz es (n+2) y por
tanto de P es FE=-2.
Facultad de Ingeniería
58
Figura 3.11 Árbol AVL con desequilibrio a la izquierda.
a. Se pasa el subárbol derecho del nodo Q como subárbol izquierdo de P. Esto mantiene el árbol como
ABB, ya que todos los valores a la derecha de Q siguen estando a la izquierda de P.
b. El árbol P pasa a ser subárbol derecho del nodo Q.
Figura 3.12 Equilibrando un árbol AVL.
c. Ahora, el nodo Q pasa a tomar la posición del nodo P, es decir, Q es el nodo raíz6.
En el árbol resultante se puede ver que tanto P como Q quedan equilibrados en cuanto altura. En el
caso de P, porque sus dos subárboles tienen la misma altura (n); en el caso de Q, porque el subárbol
izquierdo X tiene una altura (n+1) y sus subárbol derecho también, ya que a P se añade la altura de
cualquiera de sus subárboles.
6
P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura.
Luis Carlos Torres Soler
Estructuras de Datos
Rotación simple a la izquierda (RSI):
59
Figura 3.13 Árbol AVL equilibrado.
Figura 3.14 Árbol AVL con desequilibrio a la izquierda.
Se trata de un caso simétrico al anterior. Esta rotación se usa cuando el subárbol derecho de un nodo
sea 2 unidades más alto que el izquierdo, es decir, cuando su FE sea de 2. Además, la raíz del subárbol
derecho tenga un FE de 1, es decir, que esté cargado a la derecha.
Se procede del siguiente modo:
- Se nota P al nodo que muestra el desequilibrio, el que tiene FE=2. Se nota Q al nodo raíz del subárbol
derecho de P. Además, se nota X al subárbol izquierdo de P, Y al subárbol izquierdo de Q y W al
subárbol derecho de Q.
En la figura 3.14 se puede observar que tanto X como Y tienen la misma altura (n), y W es una unidad
mayor (n+1). Esto hace que FE=1 para Q, la altura del subárbol que tiene Q como raíz es (n+2) y por
tanto FE=2 para P.
a. Se pasa el subárbol izquierdo del nodo Q como subárbol derechoo de P. Esto mantiene el árbol
como ABB, ya que todos los valores a la izquierda de Q siguen estando a la derecha de P.
b. El árbol P pasa a ser subárbol izquierdo del nodo Q.
Facultad de Ingeniería
c. Ahora, el nodo Q pasa a tomar la posición del nodo P, es decir, Q es el nodo raíz7.
60
Figura 3.15 Equilibrando un árbol AVL.
En el árbol resultante (figura 3.16) puede verse que tanto P como Q quedan equilibrados en cuanto
altura. En el caso de P, porque sus dos subárboles tienen la misma altura (n); en el caso de Q, porque el
subárbol izquierdo X tiene una altura (n+1) y sus subárbol derecho también, ya que a P se añade la
altura de cualquiera de sus subárboles.
Figura 3.16 Árbol AVL equilibrado.
Rotación doble de nodos
Rotación doble a la derecha (RDD):
Esta rotación se usa cuando el subárbol izquierdo de un nodo sea 2 unidades más alto que el derecho,
es decir, cuando su FE= 2. Además, la raíz del subárbol izquierdo tenga un FE=1, es decir, que esté
cargado a la derecha.
La figura 3.17 muestra uno de los posibles árboles que se pueden presentar, hay otras posibilidades. El
nodo R puede tener FE=-1, 0 o 1.En cada uno de esos casos los árboles izquierdo y derecho de R (Y y
W) pueden tener alturas de n y n+1, n y n o n+1 y n, respectivamente.
7
P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura.
Luis Carlos Torres Soler
Estructuras de Datos
61
El modo de realizar la rotación es independiente de la estructura del árbol R, cualquiera de las tres
produce resultados equivalentes. Se hará aquí el análisis para el caso en que FE=-1.
Figura 3.17 Árbol AVL con desequilibrio a la derecha.
Se realizan dos rotaciones. Se nota P al nodo que muestra el desequilibrio, FE=-2. Se nota Q al nodo
raíz del subárbol izquierdo de P, y R al nodo raíz del subárbol derecho de Q. Se realiza primero una
Figura 3.18 Equilibrando un árbol AVL, primera rotación.
roación simple de Q a la izquierda. Luego, se hará una rotación simple de P a la derecha. Es decir, (a)
Se pasa el subárbol izquierdo del nodo R como subárbol derecho de Q. Esto mantiene el árbol como
ABB, ya que todos los valores a la izquierda de R siguen estando a la derecha de Q; (b) El nodo R pasa
a tomar la posición del nodo Q, es decir, la raíz del subárbol izquierdo de P será el nodo R en lugar de
Q.
c. El árbol Q pasa a ser el subárbol izquierdo del nodo R.
d. Se pasa el subárbol derecho del nodo R como subárbol izquierdo de P. Esto mantiene el árbol como
Figura 3.19 Primera parte de equilibrio.
Facultad de Ingeniería
62
ABB, ya que todos los valores a la derecha de R siguen estando a la izquierda de P.
e. Ahora el nodo R pasa a tomar la posición del nodo P, es decir, el nuevo árbol será el nodo R, en
lugar del nodo P.
f. El árbol P pasa a ser el subárbol derecho del nodo R.
Figura 3.20 Segunda rotación.
Rotación doble a la izquierda (RDI)
Es una rotación similar a la anterior y se usa cuando el subárbol derecho de un nodo sea 2 unidades
más alto que el izquierdo, es decir, cuando posee un FE=2. Además, la raíz del subárbol derecho tiene
FE=-1, luego está cargado a la izquierda. También se realizan dos rotaciones.
Reequilibrados en árboles AVL
Cada vez que se inserta o elimina un nodo en un árbol AVL pueden suceder dos cosas: (a) el árbol se
mantiene como AVL; o (b) Pierde la propiedad AVL. En el segundo caso siempre se está en algúno de
los casos esplicados anteriormente, y se recupera el estado AVL aplicando la rotación adecuada.
Ya se dijo que se requiere añadir un nuevo campo a cada nodo del árbol para averiguar si el árbol
sigue siendo AVL, el factor de equilibrio. Cuando uno de esos valores sea 2 o -2 se aplica la rotación
correspondiente.
Debido a que se requiere capacidad para recorrer el árbol a la raíz, es necesario añadir un nuevo
puntero a cada nodo que apunte al nodo padre8. Esto complicará algo las operaciones de inserción,
borrado y rotación, pero facilita y agiliza mucho el cálculo del FE, y se verá que las complicaciones se
compensan en gran parte por las facilidades obtenidas al disponer de este puntero.
Cuando se actualizan los valores de FE no requiere calcularse las alturas de las dos ramas de cada
nodo, sabiendo el valor anterior de FE, y sabiendo en que rama se ha añadido o eliminado el nodo, es
8
En rigor, no es necesario el puntero, puede almacenarse el camino recorrido para localizar un nodo concreto
usando una pila, y después usarla para recuperar el camino en orden inverso. Aunque esto obliga a introducir
otra estructura dinámica, lo que complica en exceso los algoritmos.
Luis Carlos Torres Soler
Figura 3.21 Árbol equilibrado.
Estructuras de Datos
63
fácil calcular el nuevo valor FE. Si el nodo ha sido añadido en la rama derecha o eliminado en la
izquierda, y ha habido un cambio de altura en la rama, se incrementa el valor FE; si el nodo se añade
en la rama izquierda o se elimina de la derecha, y ha habido un cambio de altura en la rama, se
decrementa el valor FE.
Los cambios de altura en una rama se producen sólo cuando el FE del nodo raíz de esa rama cambia de
0 a 1 o de 0 a -1. En caso contrario, cuando el FE cambia de 1 a 0 o de -1 a 0, no se produce cambio en
la altura9.
Ejercicios
Sea la expresión: x=(y-z/w*s)/(w+z-s/y)*x+(y-u/s). ¿Cuál es su árbol, la lectura en preorden y la
notación posfija?
Considere el siguiente seudo-algoritmo (no completo) que crea un árbol a partir de una notación
posfija
............
F1 <- R1
MQ F <= R
aux <- INFO(F)
nodo <- DISPO
INFO.nodo <- aux
SI aux "opdo" TH Dlink.nodo <- null
Ilink.nodo <- null
ColaArb.R1 <- nodo
F <- F +1
R1 <- R1 + 1
SN R1 <- R1 - 1
Dlink.nodo <- ColaArb.R1
R1 <- R1 - 1
Ilink.nodo <- ColaArb.R1
F <- F + 1
ColaArb.R1 <- nodo
R1 <- R1 + 1
raíz <- nodo
FSI
FMQ
............
a. Explique qué se hace en cada uno de los pasos.
9
Si no hay cambio de altura, los valores FE del resto de los nodos en el árbol hasta la raíz no pueden cambiar
(FE=altura de rama derecha-altura de rama izquierda). La altura de la rama que no pertenece al camino no
puede cambiar.
Facultad de Ingeniería
b. Completarlo, modificarlo si contiene errores.
c. Pruébelo para la expresión: x=(a-b-d*a-a+b*d/a)-(a+b-c)/a.
Luis Carlos Torres Soler
64