EInf24

Vista previa del material en texto

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.
Luis Carlos Torres Soler
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).
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.
Figura 3.1 Representación de Árboles
Estructuras de Datos
Facultad de Ingeniería
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.
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.
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]
}
Figura 3.2 Árbol binario.
Figura 3.3 Paso del árbol no binario (fig. 3.2) a uno binario.
Luis Carlos Torres Soler
46
Á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.
Á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.
Figura 3.4 Ejemplos de árboles.
Figura 3.5 Ejemplo de árboles completos.
Estructuras de Datos
Facultad de Ingeniería
47
Dos árboles son equivalentes si son similares y poseen la misma información.
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.
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) {
Figura 3.6 Ejemplo de árbol de búsqueda binario.
Luis Carlos Torres Soler
48
if (a== null) return;
LeerArbol(a->rama[0]);
LeerArbol(a->rama[1]);
}
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).
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
Figura 3.7. Estructura de un nodo.
Estructuras de Datos
Facultad de Ingeniería
49
stack <= p
p <-- ilink.p
SN SI stack = null TH sw=1
SN p <= stack
p <-- dlink.p
FSI
FSI
FMQ
FINPREORDEN()
Seudo-algoritmopara 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
Luis Carlos Torres Soler
50
link.dispo <- null
stack <- link.stack
SN s <-- stack
 stack <- link.stack
 link.s <-- dispo
 dispo <-- s
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
Estructuras de Datos
Facultad de Ingeniería
51
c. 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.
Figura 3.8. Conversión de bosque a árbol.
Luis Carlos Torres Soler
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
Estructuras de Datos
Facultad de Ingeniería
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.
Luis Carlos Torres Soler
54
F: META es info.subarbol_derecho de xv
 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.
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
Figura 3.9 Ejemplo de árbol de búsqueda binario.
Estructuras de Datos
Facultad de Ingeniería
55
FSI
SI info.nodo > META V: buscar_arbol_izquierdo(nodo)
F. buscar_arbol_derecho(nodo)
FSI
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.
Luis Carlos Torres Soler
56
Recorrido del árbol en pos-orden
altura=0
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 dela 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 in-
orden, pero nunca la misma lectura en pos-orden.
Figura 3.10 Árbol de expresión aritmética.
Estructuras de Datos
Facultad de Ingeniería
57
Definición. Un árbol AVL (llamado así por las iniciales de sus inventores: Adelson-Velskii-
Landis) 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.
Luis Carlos Torres Soler
58
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.
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.
Figura 3.11 Árbol AVL con desequilibrio a la izquierda.
Figura 3.12 Equilibrando un árbol AVL.
Estructuras de Datos
Facultad de Ingeniería
59
Rotación simple a la izquierda (RSI):
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.
Figura 3.13 Árbol AVL equilibrado.
Figura 3.14 Árbol AVL con desequilibrio a la izquierda.
Luis Carlos Torres Soler
60
c. Ahora, el nodo Q pasa a tomar la posición del nodo P, es decir, Q es el nodo raíz7.
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.
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.
Figura 3.15 Equilibrando un árbol AVL.
Figura 3.16 Árbol AVL equilibrado.
Estructuras de Datos
Facultad de Ingeniería
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.
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
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.17 Árbol AVL con desequilibrio a la derecha.
Figura 3.18 Equilibrando un árbol AVL, primera rotación.
Figura 3.19 Primera parte de equilibrio.
Luis Carlos Torres Soler
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.
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 nodosea 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.
Figura 3.20 Segunda rotación.
Figura 3.21 Árbol equilibrado.
Estructuras de Datos
Facultad de Ingeniería
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.
Luis Carlos Torres Soler
64
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.