Download Árboles - Departamento de Informática

Universidad de Valladolid
Departamento de informática
Campus de Segovia
Estructura de datos
Tema 5: Árboles
Prof. Montserrat Serrano Montero
1
ÍNDICE
Primera parte:
• Conceptos básicos
• TAD Árbol binario
• TAD Árbol de búsqueda
2
CONCEPTOS BÁSICOS
•
Árbol: Estructura no lineal que organiza sus
elementos formando jerarquías.
•
•
Nodo: Elemento del árbol.
Árbol: Se define formalmente como una
estructura finita formada por un nodo al cual
están conectados ninguno, uno o más árboles
disjuntos (no comparten elementos).
Definición recursiva: lo definido se encuentra
dentro de la definición.
3
CONCEPTOS BÁSICOS
•
•
•
•
Bosque: Conjunto de dos o más árboles.
Subárbol: Subconjunto de elementos de un
árbol con estructura de árbol.
Raíz: Nodo superior de un árbol. Al nodo raíz
se le asocia el nivel 1. Nivel cero para el árbol
vacío.
Si existe una arista (rama) dirigida del nodo n
al nodo m, entonces n es el padre o
ascendiente directo de m y m es un hijo o
descendiente directo de n. Los hijos del
mismo padre son hermanos.
•
Un nodo que no tiene hijos se llama hoja del
árbol. Nodo terminal.
•
Nodo interior o rama: Tiene descendientes.
4
CONCEPTOS BÁSICOS
•
•
•
Camino: Secuencia de nodos conectados
dentro de un árbol.
Nodo ascendiente y descendiente: n es
antecesor de m si existe un camino de n a m
y en este caso, m es descendiente de n.
Longitud del camino: Número de nodos
menos uno (r-1). (5-1) en el ej.
5
CONCEPTOS BÁSICOS
•
Nivel de un nodo: La longitud del camino
desde el nodo raíz al nodo considerado, más
uno.
•
Altura o profundidad de un árbol: El nivel
más alto del árbol (o nivel máximo de los
nodos de un árbol).
Grado (aridad): Número de hijos de un
nodo. El grado de un árbol se define como el
máximo del grado de sus nodos.
Árbol ternario: Árbol de grado 3.
Un árbol unario sería un árbol de grado 1. A
este árbol se le llama lista (árbol degenerado)
El máximo número de nodos de un árbol de
altura “h” y grado “g” sería:
6
1 + g + g2 + g3 +...+ gh-1 = ∑ gi ; 0 ≤ i ≤ (h -1)
•
•
CONCEPTOS BÁSICOS
•
Representación de árboles:
a) Grafo
b) Jerarquía de márgenes
c) Conjuntos incluidos
d) Listas incluidas
7
TAD ÁRBOL BINARIO
•
Árbol binario: Árbol de grado 2. De cada
nodo parten como máximo dos subárboles
disjuntos (izquierdo y derecho). También
puede estar vacío.
ESPECIFICACIÓN INFORMAL:
TAD ArbolB (VALORES: rango del problema;
OPERACIONES: Inicia, EsVacio, Insertar,
Suprimir, Izquierdo, Derecho, Raiz);
Inicia ( )
→ ArbolB
Efecto: Crea un árbol binario vacío y lo deja en
disposición de ser utilizado.
EsVacio (ArbolB)
→ Boolean
8
Efecto: Devuelve true si el árbol binario es
vacío y false en caso contrario.
TAD ÁRBOL BINARIO
Insertar (ArbolB, Elemento) → ArbolB
Efecto: Introduce en el ArbolB un nuevo nodo
cuyo valor está dado por el Elemento pasado.
Excepción: Árbol lleno en implementa. estática.
Suprimir (ArbolB, Elemento) → ArbolB
Efecto: Borra del árbol binario el nodo cuyo
valor coincide con el que se pasa en Elemento,
si éste existe.
Excepción: Error si el árbol binario está vacío.
Izquierdo (ArbolB)
→ ArbolB
Efecto: Devuelve el hijo izquierdo del árbol
binario pasado como entrada.
Excepción: Error si el árbol binario está vacío.
Derecho (ArbolB)
→ ArbolB
Efecto: Devuelve el hijo derecho del árbol
binario pasado como entrada.
Excepción: Error si el árbol binario está vacío.
Raiz (ArbolB)
→ Elemento
Efecto: Devuelve el Elemento contenido en el
nodo raíz del árbol binario pasado como
9
entrada.
Excepción: Error si el árbol binario está vacío.
DECLARACIÓN DE TIPOS
•
Con arrays:
const
MaxNodos = ...;
type
indice = 0..MaxNodos; {máx nº de nodos}
tInfo = ...; {depende del problema}
tNodo = record
info: tInfo;
iz: indice;
de: indice;
end;
tArbol = record
raiz: indice; (1)
libre: indice; (6)
nodos: array [1..MaxNodos] of tNodo;
end;
10
DECLARACIÓN DE TIPOS
•
Con punteros: (seguir con esta implementación)
tInfo = ...; {depende del problema}
tArbol = ^Nodo;
Nodo = record
info: tInfo;
iz, de: tArbol
end;
11
ALGORITMOS BÁSICOS
procedure Inicia (var ArbolB: tArbol);
begin
ArbolB:= nil
end;
function EsVacio (ArbolB: tArbol): boolean;
begin
EsVacio:= (ArbolB = nil)
end;
function Izquierdo (ArbolB: tArbol): tArbol;
begin
if not EsVacio (ArbolB) then Izquierdo:= ArbolB^.iz
else writeln (‘El árbol está vacío’)
end;
function Derecho (ArbolB: tArbol): tArbol;
begin
if not EsVacio (ArbolB) then Derecho:= ArbolB^.de
else writeln (‘El árbol está vacío’)
end;
procedure Raiz (ArbolB: tArbol; var Elemento: tInfo);
begin
if not EsVacio (ArbolB) then Elemento:= ArbolB^.info
else writeln (‘El árbol está vacío’)
12
end;
ALGORITMOS DE RECORRIDO
•
Utilizados para visualizar o consultar datos
almacenados en un árbol.
•
Métodos:
a) En profundidad: Recorre el árbol por
subárboles.
1. Enorden
2. Preorden
3. Postorden
b) En amplitud: Recorre el árbol por niveles.
•
Los métodos en profundidad pueden
implementarse de forma recursiva e iterativa.
La forma iterativa requiere utilizar una pila.
•
El recorrido en amplitud se implementa de
forma iterativa con ayuda de una cola como
estructura de datos auxiliar.
•
Aplicación de estos algoritmos: acceso a
13
datos de almacenamiento en memoria
secundaria.
ALGORITMOS DE RECORRIDO
•
Recorrido recursivo enorden (IND):
1. Recorrer el subárbol izquierdo (I)
2. Visitar el nodo raíz (N)
3. Recorrer el subárbol derecho (D).
Resultado: 4-2-5-1-6-3-7
1
2
4
3
5
6
7
procedure enorden (Arbol: tArbol);
begin
if Arbol <> nil then
begin
enorden (Arbol^.iz);
write (Arbol^.info, ‘- ‘);
enorden (Arbol^.de)
end
end;
14
ALGORITMOS DE RECORRIDO
•
Recorrido recursivo preorden (NID):
1. Visitar el nodo raíz (N)
2. Recorrer el subárbol izquierdo (I).
3. Recorrer el subárbol derecho (D).
1
Resultado: 1-2-4-5-3-6-7
3
2
5
4
6
7
procedure preorden (Arbol: tArbol);
begin
if Arbol <> nil then
begin
write (Arbol^.info, ‘- ‘);
preorden (Arbol^.iz);
preorden (Arbol^.de)
end
end;
15
ALGORITMOS DE RECORRIDO
•
Recorrido recursivo postorden (IDN):
1. Recorrer el subárbol izquierdo (I).
2. Recorrer el subárbol derecho (D).
3. Visitar el nodo raíz (N).
1
Resultado: 4-5-2-6-7-3-1
2
3
5
4
6
7
procedure postorden (Arbol: tArbol);
begin
if Arbol <> nil then
begin
postorden (Arbol^.iz);
postorden (Arbol^.de);
write (Arbol^.info, ‘ - ‘)
end
end;
16
ALGORITMOS DE RECORRIDO
•
Hay otras posibles combinaciones,
considerando recorrido primero el
subárbol derecho:
1. Enorden: DNI
7-3-6-1-5-2-4
2. Preorden: NDI
1-3-7-6-2-5-4
3. Postorden: DIN 7-6-3-5-4-2-1
Ejemplo. Deducir los tres recorridos en
profundidad del árbol binario siguiente:
•
A
C
B
D
H
E
I
F
G
J
Enorden: H-D-I-B-J-E-A-F-C-G
Preorden: A-B-D-H-I-E-J-C-F-G
Postorden: H-I-D-J-E-B-F-G-C-A
17
ALGORITMOS DE RECORRIDO
•
Recorrido iterativo en amplitud:
1. Tomar el puntero a la raíz y ponerlo en la cola.
2. Quitar el primer elemento de la cola, mostrar
el contenido del nodo y almacenar en la cola los
punteros correspondientes a sus hijos izquierdo y
derecho.
3. Repetir el paso 2.
procedure amplitud (Arbol: tArbol);
var A: tArbol; cola: tCola;
begin
Inicia (cola);
A:= Arbol;
if A<>nil then Encolar (cola, A);
while not EsVacia (cola) do
begin
Desencolar (cola, A);
write (A^.info, ‘ – ‘);
if A^.iz <> nil then Encolar (cola, A^.iz);
if A^.de <> nil then Encolar (cola, A^.de)
end
end;
18
ALGORITMOS DE RECORRIDO
•
Recorrido iterativo enorden (IND):
Se utiliza una pila donde almacenar punteros a
los distintos nodos del árbol.
3. Recupera
1.
2.
Se recupera
van colocando
dede
la la
pila
pila
eny la
escribe
y pila
se escribe
punteros,
1. Como
el 6.a1Como
lano
raíztiene
tiene
no
yhijo
loshijo
sucesivos
derecho,
derecho,
recupera
hijos
se pasa
izquierdos
dea la
recuperar
piladey cada
escribe
de la
nodo.
4.
pila
Elyhijo
a escribir
derecho
el de
8. El
4 es
8 tiene
6. Pone
un en
hijoladerecho,
pila el
que
puntero
se coloca
a 6. en la pila. Después se coloca en la
pila el hijo izquierdo de 12 que será el que se
19
recupere a continuación.
ALGORITMOS DE RECORRIDO
•
Recorrido iterativo enorden (IND):
procedure enorden (Arbol: tArbol);
var A: tArbol; P: tPila;
begin
Inicia (P);
A := Arbol;
repeat
while A <> nil do
begin
Apilar (P, A);
A := A^.iz
end;
if not EsVacia (P) then
begin
Cima (P, A);
Desapilar (P);
write (A^.info, ‘ – ‘);
A := A^.de
end;
until EsVacia (P) and EsVacio (A)
end;
20
ÁRBOLES DE EXPRESIÓN
•
Los árboles binarios se utilizan para
almacenar expresiones aritméticas en
memoria, esencialmente en compiladores de
lenguajes de programación.
•
Los paréntesis no se almacenan en el árbol
pero están implicados en la forma del árbol.
(A + B) * C
A+B*C
21
ÁRBOLES DE EXPRESIÓN
•
Ejemplo 1: Deducir las expresiones que
representan los siguientes árboles binarios.
•Solución:
Ejemplo 2: Dibujar la representación en árbol
binario
de /cada
a) X * (Y
- Z) una de las siguientes
expresiones:
b) A + [ (B * - (C + D)]
a)
/ [ +(AY)]
+ B)
c) X
[A**Y( X
* C* C ]
b) (X * Y / A) + (B * C)
22
ÁRBOLES BINARIOS
DE BÚSQUEDA
•
Árbol binario de búsqueda: Árbol binario
ordenado. El valor en el nodo raíz es mayor
que todos los del subárbol izquierdo y menor
que todos los del subárbol derecho.
•
•
Si recorremos el árbol enorden, está ordenado.
Las operaciones básicas sobre este tipo de
árboles binarios son:
a) Búsqueda
b) Inserción
c) Borrado
23
d) Recorridos
ESPECIFICACIÓN
•
TAD Árbol binario de búsqueda:
Busqueda (ABB, Clave) → ABB
Efecto: Devuelve el valor de una referencia al
nodo que tiene la clave buscada y nil si la
clave no está en el árbol.
Insertar (ABB, Clave)
→ ABB
Efecto: Introduce en el árbol como nodo hoja, la
clave pasada como valor de entrada.
Suprimir (ABB, Clave) → ABB
Efecto: Borra del árbol binario el elemento
pasado como entrada, si éste existe.
Excepción: Error si el árbol binario está vacío.
24
IMPLEMENTACIÓN
•
Operación Búsqueda:
function Busqueda (ABB: tArbol; Clave: tInfo):
tArbol;
begin
if ABB = nil then Busqueda := nil
else
if ABB^.info = Clave then
Busqueda := ABB
else
if ABB^.info > Clave then
Busqueda := Busqueda (ABB^.iz, Clave)
else
Busqueda := Busqueda (ABB^.de, Clave)
end;
25
IMPLEMENTACIÓN
•
Operación Insertar:
•
Pasos a seguir:
1. Asignar memoria para un nuevo nodo.
2. Buscar en el árbol para encontrar la posición
de inserción del nuevo nodo, que se colocará
como nodo hoja.
3. Enlazar el nuevo nodo al árbol.
Ej: Tenemos que almacenar los números
8 3 1 20 1 10 5 4
•
Para insertar 8, la única elección es insertar 8
en el nodo raíz:
Como 3 < 8, 3 va en el subárbol izquierdo.
26
IMPLEMENTACIÓN
•
Operación Insertar:
El 1 irá a la izquierda
y debajo de 3:
20 debe ir a la derecha de 8
Los restantes elementos se sitúan de la misma
forma:
27
IMPLEMENTACIÓN
•
Operación Insertar:
procedure Insertar (var ABB: tArbol; Clave: tInfo);
var N: tArbol;
begin
if ABB = nil then
begin
new (N);
N^.info := Clave;
Crea el nodo cuando se
N^.iz := nil;
llega a una posición
hoja
N^.de := nil;
ABB := N;
end
else if ABB^.info > Clave then {Clave menor}
Insertar (ABB^.iz, Clave) {Izquierda}
else
if ABB^.info < Clave then
Insertar (ABB^.de, Clave) {Derecha}
end;
28
IMPLEMENTACIÓN
•
Operación Suprimir: Compleja, ya que el
nodo a suprimir puede ser cualquiera y la
operación de supresión debe mantener la
estructura del ABB.
•
Se pueden presentar 3 casos con tratamientos
diferentes:
1. El nodo a borrar es un nodo hoja.
- Se borra el nodo.
2. El nodo a borrar sólo tiene un descendiente.
- Se puentea el nodo.
3. El nodo a borrar es normal, es decir, tiene
los dos nodos hijos: (2 alternativas)
a) Reemplazar la clave a eliminar por la
mayor de las claves menores.
b) Reemplazar la clave a eliminar por la
menor de las claves mayores.
•
Implementamos con un ejemplo el caso 3,
29
alternativa a).
IMPLEMENTACIÓN
•
Se quiere borrar la clave 20. Pasos a seguir:
1. Situarse en el nodo raíz del subárbol izquierdo
del nodo a borrar.
2. Se desciende por la derecha hasta encontrar un
nodo N sin descendiente derecho.
3. Se traslada la clave del nodo N al nodo a
borrar.
30
4. Se borra el nodo N.
IMPLEMENTACIÓN
•
•
Árbol resultante, una vez borrada la clave
20.
Es un árbol de búsqueda:
1, 5, 10, 12, 15, 17, 18, 22, 24, 30, 35
31
IMPLEMENTACIÓN
•
Operación Suprimir:
procedure Suprimir (var ABB: tArbol; Clave: tInfo);
var N: tArbol;
procedure Borra2hijos (var ABB: tArbol);
begin
if ABB < > nil then
if ABB^.info > Clave then {Clave menor}
Suprimir (ABB^.iz, Clave)
else if ABB^.info < Clave then {Clave mayor}
Suprimir (ABB^.de, Clave)
else {Clave encontrada}
begin
N := ABB;{Puntero aux al nodo a borrar}
if ABB^.iz = nil then {Comprueba 2
ABB := ABB^.de
descendientes}
else if ABB^.de = nil then
ABB := ABB^.iz
else Borra2hijos (ABB^.iz); {Se toma el
dispose (N)
nodo izq a la clave
end
que se quiere borrar}
32
end;
IMPLEMENTACIÓN
•
Operación Suprimir:
procedure Borra2hijos (var ABB: tArbol);
begin
if ABB^.de < > nil then {Se desciende por la
Borra2hijos (ABB^.de) derecha hasta nodo
else
hoja derecha}
begin
{Se cambia la información de la clave a
borrar por la mayor de las claves menores}
N^.info := ABB^.info;
{Puntero auxiliar al nuevo nodo a borrar}
N := ABB;
{Se enlaza al árbol el posible nodo izquierdo
del nuevo a borrar}
ABB := ABB^.iz
end
33
end;
INTERÉS DE LOS ABB
•
El esfuerzo para localizar un elemento es
menor que en una lista.
• El nº de comparaciones, como máximo
en un ABB, es el nº de niveles del árbol,
que es más pequeño cuanto más
completo sea el árbol.
• Dada una estructura con n elementos:
1. En una lista habrá que hacer una media
de n/2 comparaciones.
2. En un ABB habrá que hacer 2k-1
comparaciones siendo k la altura del
árbol.
n = 2k-1; 2k-1=2*log2(n+1)-1
34
Universidad de Valladolid
Departamento de informática
Campus de Segovia
Estructura de datos
Tema 5: Árboles equilibrados
Prof. Montserrat Serrano Montero
35
Nadie que no haya cometido nunca un error
ha intentado nunca algo nuevo.
Einstein
ÍNDICE
Segunda parte:
• Conceptos básicos
• Buscando el equilibrio.
• Diseño e implementación
de árboles AVL
36
INTERÉS DE LOS ÁRBOLES DE
BÚSQUEDA
•
Optimizar el proceso de búsqueda.
En el caso de un árbol binario ordenado
habrá que hacer un máximo de k
comparaciones para encontrar el elemento
buscado, siendo k la altura del árbol.
En el caso más favorable, el árbol binario está
completo. Así, el número máximo de
elementos que puede tener un árbol binario de
altura h es:
nmax = 1 + 2 + 4 + 8 + ...+ 2 k-1 = 2k –1
37
k = log2(nmax + 1)
CONCEPTOS BÁSICOS
•
Si los elementos se añaden en el árbol según
el algoritmo de inserción visto para los ABB,
la estructura resultante del árbol dependerá
del orden en que sean añadidos.
•
Si todos los elementos se insertan en orden
creciente o decreciente, el árbol va a tener
todas sus ramas izquierda o derecha,
respectivamente, vacías.
•
La búsqueda en estos árboles será totalmente
38
secuencial. Comparaciones: O (n)
CONCEPTOS BÁSICOS
•
La idea asociada a la eficiencia en la
búsqueda de un elemento es la de árbol
equilibrado.
•
Intuitivamente quiere decir que “una rama
del árbol no sea mucho más larga que otra”,
“que el número de niveles no sea demasiado
grande para el número de nodos existentes”,
“que no haya desproporción de elementos de
una rama con respecto a otra”.
39
CONCEPTOS BÁSICOS
•
Un árbol binario lleno de altura h tiene todas
sus hojas a nivel h y todos los nodos que están
a nivel menor que h tiene cada uno dos hijos.
•
Un árbol binario completo de altura h es un
árbol binario que está relleno a partir del nivel
h-1, con el nivel h relleno de izquierda a
derecha.
•
Un árbol binario lleno, es completo.
40
CONCEPTOS BÁSICOS
•
Un árbol perfectamente equilibrado es un
árbol binario en el que para todo nodo, el
número de nodos en el subárbol izquierdo y
el número de nodos en el subárbol derecho
difieren como mucho en una unidad.
•
Un árbol equilibrado en sentido AVL
(Adelson-Velskii y Landis, 1962) es un árbol
binario en el que la diferencia de alturas de
los subárboles izquierdo y derecho
correspondientes a cualquier nodo del árbol
no es superior a uno.
41
CONCEPTOS BÁSICOS
•
Un árbol binario completo es un árbol
equilibrado, mientras que un árbol binario
lleno es totalmente equilibrado.
En la figura:
a) Árbol equilibrado AVL
b) Árbol totalmente equilibrado
c) y d) Árboles no equilibrados
42
CONCEPTOS BÁSICOS
•
Un árbol binario de búsqueda va perdiendo o
ganando equilibrio al insertar o suprimir
elementos.
•
Ejemplo:
Árbol
Árbol
perfectamente
binario de
equilibrado,
búsqueda tras
equilibrado.
trasinsertar
insertar14.
10.
Árbol
totalmente
equilibrado,
Árbol lleno.
43
ÁRBOL BINARIO
EQUILIBRADO (AVL)
•
La altura o profundidad de un árbol binario
es el nivel máximo de sus hojas. La altura de
un árbol nulo se considera cero.
•
El factor de equilibrio o balance de un
nodo se define como la altura del subárbol
derecho menos la altura del subárbol
izquierdo correspondiente.
•
El factor de equilibrio de cada nodo en un
44
árbol equilibrado será 1, -1 ó 0.
BUSCANDO EL EQUILIBRIO
•
Los algoritmos de inserción y borrado de los
ABB no garantizan que la estructura resultante
sea equilibrada en sentido AVL.
•
Es necesario definir otras operaciones
auxiliares que se van a utilizar para garantizar
que estas inserciones y supresiones sean
equilibradas.
•
Estas operaciones o manipulaciones se
denominan rotaciones de nodos.
•
Existen dos tipos de rotaciones de nodos:
A) Simples: Izquierda y derecha.
B) Dobles: Sucesiones de dos simples.
45
BUSCANDO EL EQUILIBRIO
•
ROTACIÓN SIMPLE IZQUIERDA:
A1 < A < A2 < B < A3
•
Ejemplo:
46
BUSCANDO EL EQUILIBRIO
•
ROTACIÓN SIMPLE DERECHA:
A1 < A < A2 < B < A3
•
Ejemplo:
•
Construir el ABB mediante la inserción de los
elementos 1, 2, 3, 4, 5, 6 y 7 de forma que
quede equilibrado AVL.
47
BUSCANDO EL EQUILIBRIO
•
ROTACIÓN DOBLE IZQUIERDA-DERECHA:
•
Ejemplo:
48
BUSCANDO EL EQUILIBRIO
•
ROTACIÓN DOBLE DERECHA-IZQUIERDA:
•
Ejemplo:
.
49
Diseño e implementación
de árboles AVL
•
•
DECLARACIÓN DE TIPOS:
Añadimos al tipo de datos que representa
cada nodo un campo más: el factor de
equilibrio (fe).
type
tInfo = ...;
tArbolE = ^NodoAE;
NodoAE = record
Info: tInfo;
Fe: -1..1;
Iz, De: tArbolE
end;
50
INSERCIÓN EN AVL
•
Se quiere insertar un nodo en un árbol
equilibrado en sentido AVL de raíz R y
subárboles izquierdo I y derecho D.
•
Supóngase que se inserta en I aumentando su
altura. Esta inserción puede dar lugar a tres
situaciones distintas:
Caso A:
•
hI = hD Tras la inserción se conserva el
equilibrio. No es necesario realizar ninguna
operación para restaurar el equilibrio.
51
INSERCIÓN EN AVL
Caso B:
•
hI < hD Tras la inserción, ambos subárboles
tienen la misma altura. Se mejora la condición
de equilibrio del árbol.
Caso C:
•
hI > hD Tras la inserción, la diferencia de
alturas entre los subárboles es mayor que la
unidad. El árbol se desequilibra y hay que
hacer rotaciones para que siga siendo AVL.
Dos subcasos:
1. Inserción de un nodo menor que el raíz de
52 I.
2. Inserción de un nodo mayor que el raíz de I.
INSERCIÓN EN AVL
Caso C: Ejemplo
1.
Se produce al insertar un nodo de clave 1 ó 3.
Este índice es menor que el nodo raíz del
subárbol izquierdo (4). La rotación a llevar a
cabo para reequilibrar el árbol sería una
rotación simple izquierda sobre el nodo raíz
del árbol desequilibrado: el 8.
2.
Se produce al insertar un nodo de clave 5 ó 7.
Este índice es mayor que el nodo raíz del
subárbol izquierdo (4). La rotación a llevar a
cabo sería una rotación doble izquierda53
derecha sobre el nodo raíz del árbol
desequilibrado.
Diseño e implementación
de árboles AVL
•
•
INSERCIÓN: (tratamiento rotaciones)
Inserción de las claves 68, 45, 29:
•
Movimiento de los punteros: Rotación I
(1) n^.iz := n1^.de;
(2) n1^.de := n;
(3) n := n1
(1)
nil
54
Diseño e implementación
de árboles AVL
•
•
INSERCIÓN: (tratamiento rotaciones)
Inserción de las claves 75 y 90:
•
Movimiento de los punteros: Rotación D
(1) n^.de := n1^.iz;
(2) n1^.iz := n;
(3) n := n1
(1)
nil
55
Diseño e implementación
de árboles AVL
•
•
INSERCIÓN: (tratamiento rotaciones)
Inserción de la clave 70:
•
Movimiento de los punteros: Rotación DI
(1) n1^.iz := n2^.de;
(2) n2^.de := n1;
(3) n^.de := n2^.iz;
(4) n2^.iz := n;
(5) n := n2
(3)
nil
56
Diseño e implementación
de árboles AVL
•
•
INSERCIÓN: (tratamiento rotaciones)
Inserción de la clave 34:
•
Movimiento de los punteros: Rotación ID
(1) n1^.de := n2^.iz;
(2) n2^.iz := n1;
(3) n^.iz := n2^.de;
(4) n2^.de := n;
(5) n := n2
(1) (3)
nil nil
57
Diseño e implementación
de árboles AVL
•
INSERCIÓN:
function EsVacio (R: tArbolE): boolean;
begin
EsVacio:= (R = nil)
end;
function Crear (Clave: tInfo): tArbolE;
var n: tArbolE;
begin
new (n);
with n^ do
begin
info:= Clave;
iz := nil;
de := nil;
fe := 0 {propio de un nodo hoja}
end;
Crear := n
end;
58
Diseño e implementación
de árboles AVL
•
INSERCIÓN:
procedure rsi (var n: tArbolE; n1: tArbolE);
begin
Ajuste del factor de equilibrio
(1) n^.iz := n1^.de;
(2) n1^.de := n;
if n1^.fe = -1 then
begin{Si la rotación es por inserción se cumple}
n^.fe := 0;
n1^.fe := 0
end
else begin {n1^.fe=0}
n^.fe := -1;
n1^.fe := 1
end;
(3) n := n1; Los factores de equilibrio se
end;
incrementan en uno si se fue por la
rama derecha, se decrementa en 1
59
si se fue por la rama izquierda.
Diseño e implementación
de árboles AVL
•
INSERCIÓN:
procedure rdid (var n: tArbolE; n1: tArbolE);
var n2: tArbolE
begin
n2 := n1^.de;
(3) n^.iz := n2^.de;
(4) n2^.de := n;
(1) n1^.de := n2^.iz;
(2) n2^.iz := n1; Ajuste del factor de equilibrio
if (n2^.fe = 1) then n1^.fe := -1
else n1^.fe := 0;
if (n2^.fe = -1) then n^.fe :=1
else n^.fe := 0;
n2^.fe := 0;
(5) n := n2;
end;
60
Diseño e implementación
de árboles AVL
•
INSERCIÓN:
procedure rsd (var n: tArbolE; n1: tArbolE);
begin
(1) n^.de := n1^.iz;
(2) n1^.iz := n;
if n1^.fe = 1 then Ajuste del factor de equilibrio
begin
{Si la rotación es por
inserción se cumple}
n^.fe := 0;
n1^.fe := 0
end
else begin {n1^.fe=0}
n^.fe := 1;
n1^.fe := -1
end;
(3) n := n1;
end;
61
Diseño e implementación
de árboles AVL
•
INSERCIÓN:
procedure rddi (var n: tArbolE; n1: tArbolE);
var n2: tArbolE
begin
n2 := n1^.iz;
(3) n^.de := n2^.iz;
(4) n2^.iz := n;
(1) n1^.iz := n2^.de;
(2) n2^.de := n1;
if (n2^.fe = 1) then n^.fe := -1
else n^.fe := 0;
if (n2^.fe = -1) then n1^.fe :=1
else n1^.fe := 0;
n2^.fe := 0;
(5) n := n2;
end;
62
Diseño e implementación
INSERCIÓN:de árboles AVL
•
procedure InsertarE (var r: tArbolE; var hh: boolean; Clave:
tInfo);
var n1: tArbolE;
begin
if EsVacio (r) then {se ha llegado a nodo hoja}
begin
r := Crear (Clave); hh := true {la altura del árbol ha crecido}
end;
else if (Clave < r^.info) then {Seguimos por la izquierda}
begin
InsertarE (r^.iz, hh, Clave);
if hh then {decrementar en 1 Fe porque se insertó por
case r^.fe of
rama izquierda}
1: begin
r^.fe := 0; hh := false
end;
0: r^.fe := -1;
-1: begin {Debe valer –2. Desequilibrio izquierda}
n1 := r^.iz;
if (n1^.fe = -1) then rsi (r, n1) {desequilibrio izq}
else rdid (r, n1); {n1^.fe = 1}
hh := false
end
63
end; {case}
end {if}
•
Diseño e implementación
de árboles AVL
INSERCIÓN:
else if (Clave > r^.info) then {Seguimos por la derecha}
begin
InsertarE (r^.de, hh, clave);
if hh then {incrementar en 1 Fe porque se insertó por
case r^.fe of
rama derecha}
-1: begin {se reequilibra solo}
r^.fe := 0; hh := false
end;
0: r^.fe := 1;
1: begin {Debe valer 2. Desequilibrio derecha}
n1 := r^.de;
if (n1^.fe = 1) then rsd (r, n1) {desequilibrio dcha}
else rddi (r, n1);
hh := false
end
end; {case}
end {if}
else begin {Clave = r^.info}
writeln (‘No está previsto insertar claves repetidas’);
hh := false
end
64
end;
SUPRIMIR EN AVL
•
Sigue la estrategia del algoritmo de supresión
en árboles binarios de búsqueda.
•
Al suprimir un nodo con cierta clave, el árbol
resultante debe seguir siendo un árbol
equilibrado.
•
Una vez eliminado un nodo siguiendo los
criterios ABB, se regresa por el camino
calculando los nuevos factores de equilibrio
(Fe).
•
Si en alguno de los nodos se viola el criterio
de equilibrio debe restaurarse el mismo,
teniendo en cuenta que pueden producirse
más de una rotación en el retroceso.
•
En los procedimientos el argumento boolean
hh, será activado cuando la altura del árbol
disminuya por eliminación de nodo o
reestructuración del subárbol.
65
SURPIMIR EN AVL
•
Casos en la reestructuración:
Caso A: Eliminar el nodo con clave 42
Rotación I, porque n^.fe := -2 y n1^.fe < = 0
66
SUPRIMIR EN AVL
•
Casos en la reestructuración:
Caso B: Eliminar el nodo con clave 21
El Fe del nodo
visitado disminuye
en 1 si la eliminación
se hizo por su rama
derecha y se
incrementa en 1 si la
eliminación se hizo
por su rama
izquierda.
Rotación DI, porque n^.fe := 2 y n1^.fe < 0
67
SUPRIMIR EN AVL
•
Casos en la reestructuración:
Caso C: Eliminar el nodo con clave 25
Rotación D, porque n^.fe := 2 y n1^.fe >= 0
68
SUPRIMIR EN AVL
•
Casos en la reestructuración:
Caso B: Reestructurar 65:
Rotación DI, porque n^.fe := 2 y n1^.fe < 0
69
Diseño e implementación
de árboles AVL
•
SUPRIMIR:
procedure EquilibrarI (var n: tArbolE; var hh:
var n1: tArbolE;
boolean);
begin
case n^.fe of
-1: n^.fe := 0;
0 : begin
n^.fe := 1; hh := false
end;
1: begin {Hay que restaurar el equilibrio}
n1:= n^.de;
if n1^.fe >=0 then
begin
if n1^.fe = 0 then hh := false; {no disminuye h}
rsd (n, n1)
end
else rddi (n, n1)
end;
70
end
end;
Diseño e implementación
de árboles AVL
•
SUPRIMIR:
procedure EquilibrarD (var n: tArbolE; var hh:
var n1: tArbolE;
boolean);
begin
case n^.fe of
1 : n^.fe := 0;
0 : begin
n^.fe := -1; hh := false
end;
-1: begin {Hay que restaurar el equilibrio}
n1:= n^.iz;
if n1^.fe <=0 then
begin
if n1^.fe = 0 then hh := false;
rsi (n, n1)
end
else rdid (n, n1)
end;
71
end
end;
Diseño e implementación
de árboles AVL
•
SUPRIMIR:
procedure SuprimirE (var r: tArbolE; var hh:
boolean; Clave: tInfo);
var q: tArbolE;
procedure bor (var d: tArbolE; var hh: boolean);
begin
if d^.de <> nil then
begin
bor (d^.de,hh);
if hh then EquilibrarD (d, hh);
end
else begin
q^.info := d^.info;
q := d;
d := d^.iz;
hh := true
end
end;
72
Diseño e implementación
de árboles AVL
•
SUPRIMIR:
begin {Suprimir}
if not EsVacio(r) then
if Clave < r^.info then
begin
Suprimir (r^.iz, hh, Clave);
if hh then EquilibrarI (r, hh)
end
else if Clave > r^.info then
begin
Suprimir (r^.de, hh, Clave);
if hh then EquilibrarD (r, hh)
end
else begin {Ha sido encontrado el nodo}
q := r;
if q^.de = nil then
begin
r := q^.iz;
hh:= true {Disminuye la altura}
73
end
(Sigue)
Diseño e implementación
de árboles AVL
•
SUPRIMIR:
else if q^.iz = nil then
begin
r := q^.de;
hh := true
end
else begin
bor ( q^.iz, hh);
if hh then EquilibrarI (r, hh)
end
dispose (q);
end {else encontrar nodo}
end;
74
Ejemplos de supresión de nodos
•
Dado el siguiente árbol, realizar las
supresiones de nodos siguientes de forma
que en cada paso quede un árbol AVL: 5,
9, 8, 6, 3
75
Universidad de Valladolid
Departamento de informática
Campus de Segovia
Estructura de datos
Tema 5: Árboles equilibrados
Prof. Montserrat Serrano Montero
76
Nadie que no haya cometido nunca un error
ha intentado nunca algo nuevo.
Einstein
ÍNDICE
Segunda parte:
• Conceptos básicos
• Buscando el equilibrio.
• Diseño e implementación
de árboles AVL
77
INTERÉS DE LOS ÁRBOLES DE
BÚSQUEDA
•
Optimizar el proceso de búsqueda.
En el caso de un árbol binario ordenado
habrá que hacer un máximo de k
comparaciones para encontrar el elemento
buscado, siendo k la altura del árbol.
En el caso más favorable, el árbol binario está
completo. Así, el número máximo de
elementos que puede tener un árbol binario de
altura h es:
nmax = 1 + 2 + 4 + 8 + ...+ 2 k-1 = 2k –1
78
k = log2(nmax + 1)
CONCEPTOS BÁSICOS
•
Si los elementos se añaden en el árbol según
el algoritmo de inserción visto para los ABB,
la estructura resultante del árbol dependerá
del orden en que sean añadidos.
•
Si todos los elementos se insertan en orden
creciente o decreciente, el árbol va a tener
todas sus ramas izquierda o derecha,
respectivamente, vacías.
•
La búsqueda en estos árboles será totalmente
79
secuencial. Comparaciones: O (n)
CONCEPTOS BÁSICOS
•
La idea asociada a la eficiencia en la
búsqueda de un elemento es la de árbol
equilibrado.
•
Intuitivamente quiere decir que “una rama
del árbol no sea mucho más larga que otra”,
“que el número de niveles no sea demasiado
grande para el número de nodos existentes”,
“que no haya desproporción de elementos de
una rama con respecto a otra”.
80
CONCEPTOS BÁSICOS
•
Un árbol binario lleno de altura h tiene todas
sus hojas a nivel h y todos los nodos que están
a nivel menor que h tiene cada uno dos hijos.
•
Un árbol binario completo de altura h es un
árbol binario que está relleno a partir del nivel
h-1, con el nivel h relleno de izquierda a
derecha.
•
Un árbol binario lleno, es completo.
81
CONCEPTOS BÁSICOS
•
Un árbol perfectamente equilibrado es un
árbol binario en el que para todo nodo, el
número de nodos en el subárbol izquierdo y
el número de nodos en el subárbol derecho
difieren como mucho en una unidad.
•
Un árbol equilibrado en sentido AVL
(Adelson-Velskii y Landis, 1962) es un árbol
binario en el que la diferencia de alturas de
los subárboles izquierdo y derecho
correspondientes a cualquier nodo del árbol
no es superior a uno.
82
CONCEPTOS BÁSICOS
•
Un árbol binario completo es un árbol
equilibrado, mientras que un árbol binario
lleno es totalmente equilibrado.
En la figura:
a) Árbol equilibrado AVL
b) Árbol totalmente equilibrado
c) y d) Árboles no equilibrados
83
CONCEPTOS BÁSICOS
•
Un árbol binario de búsqueda va perdiendo o
ganando equilibrio al insertar o suprimir
elementos.
•
Ejemplo:
Árbol
Árbol
perfectamente
binario de
equilibrado,
búsqueda tras
equilibrado.
trasinsertar
insertar14.
10.
Árbol
totalmente
equilibrado,
Árbol lleno.
84
ÁRBOL BINARIO
EQUILIBRADO (AVL)
•
La altura o profundidad de un árbol binario
es el nivel máximo de sus hojas. La altura de
un árbol nulo se considera cero.
•
El factor de equilibrio o balance de un
nodo se define como la altura del subárbol
derecho menos la altura del subárbol
izquierdo correspondiente.
•
El factor de equilibrio de cada nodo en un
85
árbol equilibrado será 1, -1 ó 0.
BUSCANDO EL EQUILIBRIO
•
Los algoritmos de inserción y borrado de los
ABB no garantizan que la estructura resultante
sea equilibrada en sentido AVL.
•
Es necesario definir otras operaciones
auxiliares que se van a utilizar para garantizar
que estas inserciones y supresiones sean
equilibradas.
•
Estas operaciones o manipulaciones se
denominan rotaciones de nodos.
•
Existen dos tipos de rotaciones de nodos:
A) Simples: Izquierda y derecha.
B) Dobles: Sucesiones de dos simples.
86
BUSCANDO EL EQUILIBRIO
•
ROTACIÓN SIMPLE IZQUIERDA:
A1 < A < A2 < B < A3
•
Ejemplo:
87
BUSCANDO EL EQUILIBRIO
•
ROTACIÓN SIMPLE DERECHA:
A1 < A < A2 < B < A3
•
Ejemplo:
•
Construir el ABB mediante la inserción de los
elementos 1, 2, 3, 4, 5, 6 y 7 de forma que
quede equilibrado AVL.
88
BUSCANDO EL EQUILIBRIO
•
ROTACIÓN DOBLE IZQUIERDA-DERECHA:
•
Ejemplo:
89
BUSCANDO EL EQUILIBRIO
•
ROTACIÓN DOBLE DERECHA-IZQUIERDA:
•
Ejemplo:
.
90
Diseño e implementación
de árboles AVL
•
•
DECLARACIÓN DE TIPOS:
Añadimos al tipo de datos que representa
cada nodo un campo más: el factor de
equilibrio (fe).
type
tInfo = ...;
tArbolE = ^NodoAE;
NodoAE = record
Info: tInfo;
Fe: -1..1;
Iz, De: tArbolE
end;
91
INSERCIÓN EN AVL
•
Se quiere insertar un nodo en un árbol
equilibrado en sentido AVL de raíz R y
subárboles izquierdo I y derecho D.
•
Supóngase que se inserta en I aumentando su
altura. Esta inserción puede dar lugar a tres
situaciones distintas:
Caso A:
•
hI = hD Tras la inserción se conserva el
equilibrio. No es necesario realizar ninguna
operación para restaurar el equilibrio.
92
INSERCIÓN EN AVL
Caso B:
•
hI < hD Tras la inserción, ambos subárboles
tienen la misma altura. Se mejora la condición
de equilibrio del árbol.
Caso C:
•
hI > hD Tras la inserción, la diferencia de
alturas entre los subárboles es mayor que la
unidad. El árbol se desequilibra y hay que
hacer rotaciones para que siga siendo AVL.
Dos subcasos:
1. Inserción de un nodo menor que el raíz de
93 I.
2. Inserción de un nodo mayor que el raíz de I.
INSERCIÓN EN AVL
Caso C: Ejemplo
1.
Se produce al insertar un nodo de clave 1 ó 3.
Este índice es menor que el nodo raíz del
subárbol izquierdo (4). La rotación a llevar a
cabo para reequilibrar el árbol sería una
rotación simple izquierda sobre el nodo raíz
del árbol desequilibrado: el 8.
2.
Se produce al insertar un nodo de clave 5 ó 7.
Este índice es mayor que el nodo raíz del
subárbol izquierdo (4). La rotación a llevar a
cabo sería una rotación doble izquierda94
derecha sobre el nodo raíz del árbol
desequilibrado.
Diseño e implementación
de árboles AVL
•
•
INSERCIÓN: (tratamiento rotaciones)
Inserción de las claves 68, 45, 29:
•
Movimiento de los punteros: Rotación I
(1) n^.iz := n1^.de;
(2) n1^.de := n;
(3) n := n1
(1)
nil
95
Diseño e implementación
de árboles AVL
•
•
INSERCIÓN: (tratamiento rotaciones)
Inserción de las claves 75 y 90:
•
Movimiento de los punteros: Rotación D
(1) n^.de := n1^.iz;
(2) n1^.iz := n;
(3) n := n1
(1)
nil
96
Diseño e implementación
de árboles AVL
•
•
INSERCIÓN: (tratamiento rotaciones)
Inserción de la clave 70:
•
Movimiento de los punteros: Rotación DI
(1) n1^.iz := n2^.de;
(2) n2^.de := n1;
(3) n^.de := n2^.iz;
(4) n2^.iz := n;
(5) n := n2
(3)
nil
97
Diseño e implementación
de árboles AVL
•
•
INSERCIÓN: (tratamiento rotaciones)
Inserción de la clave 34:
•
Movimiento de los punteros: Rotación ID
(1) n1^.de := n2^.iz;
(2) n2^.iz := n1;
(3) n^.iz := n2^.de;
(4) n2^.de := n;
(5) n := n2
(1) (3)
nil nil
98
Diseño e implementación
de árboles AVL
•
INSERCIÓN:
function EsVacio (R: tArbolE): boolean;
begin
EsVacio:= (R = nil)
end;
function Crear (Clave: tInfo): tArbolE;
var n: tArbolE;
begin
new (n);
with n^ do
begin
info:= Clave;
iz := nil;
de := nil;
fe := 0 {propio de un nodo hoja}
end;
Crear := n
end;
99
Diseño e implementación
de árboles AVL
•
INSERCIÓN:
procedure rsi (var n: tArbolE; n1: tArbolE);
begin
Ajuste del factor de equilibrio
(1) n^.iz := n1^.de;
(2) n1^.de := n;
if n1^.fe = -1 then
begin{Si la rotación es por inserción se cumple}
n^.fe := 0;
n1^.fe := 0
end
else begin {n1^.fe=0}
n^.fe := -1;
n1^.fe := 1
end;
(3) n := n1; Los factores de equilibrio se
end;
incrementan en uno si se fue por la
rama derecha, se decrementa en 1
100
si se fue por la rama izquierda.
Diseño e implementación
de árboles AVL
•
INSERCIÓN:
procedure rdid (var n: tArbolE; n1: tArbolE);
var n2: tArbolE
begin
n2 := n1^.de;
(3) n^.iz := n2^.de;
(4) n2^.de := n;
(1) n1^.de := n2^.iz;
(2) n2^.iz := n1; Ajuste del factor de equilibrio
if (n2^.fe = 1) then n1^.fe := -1
else n1^.fe := 0;
if (n2^.fe = -1) then n^.fe :=1
else n^.fe := 0;
n2^.fe := 0;
(5) n := n2;
end;
101
Diseño e implementación
de árboles AVL
•
INSERCIÓN:
procedure rsd (var n: tArbolE; n1: tArbolE);
begin
(1) n^.de := n1^.iz;
(2) n1^.iz := n;
if n1^.fe = 1 then Ajuste del factor de equilibrio
begin
{Si la rotación es por
inserción se cumple}
n^.fe := 0;
n1^.fe := 0
end
else begin {n1^.fe=0}
n^.fe := 1;
n1^.fe := -1
end;
(3) n := n1;
end;
102
Diseño e implementación
de árboles AVL
•
INSERCIÓN:
procedure rddi (var n: tArbolE; n1: tArbolE);
var n2: tArbolE
begin
n2 := n1^.iz;
(3) n^.de := n2^.iz;
(4) n2^.iz := n;
(1) n1^.iz := n2^.de;
(2) n2^.de := n1;
if (n2^.fe = 1) then n^.fe := -1
else n^.fe := 0;
if (n2^.fe = -1) then n1^.fe :=1
else n1^.fe := 0;
n2^.fe := 0;
(5) n := n2;
end;
103
Diseño e implementación
INSERCIÓN:de árboles AVL
•
procedure InsertarE (var r: tArbolE; var hh: boolean; Clave:
tInfo);
var n1: tArbolE;
begin
if EsVacio (r) then {se ha llegado a nodo hoja}
begin
r := Crear (Clave); hh := true {la altura del árbol ha crecido}
end;
else if (Clave < r^.info) then {Seguimos por la izquierda}
begin
InsertarE (r^.iz, hh, Clave);
if hh then {decrementar en 1 Fe porque se insertó por
case r^.fe of
rama izquierda}
1: begin
r^.fe := 0; hh := false
end;
0: r^.fe := -1;
-1: begin {Debe valer –2. Desequilibrio izquierda}
n1 := r^.iz;
if (n1^.fe = -1) then rsi (r, n1) {desequilibrio izq}
else rdid (r, n1); {n1^.fe = 1}
hh := false
end
104
end; {case}
end {if}
•
Diseño e implementación
de árboles AVL
INSERCIÓN:
else if (Clave > r^.info) then {Seguimos por la derecha}
begin
InsertarE (r^.de, hh, clave);
if hh then {incrementar en 1 Fe porque se insertó por
case r^.fe of
rama derecha}
-1: begin {se reequilibra solo}
r^.fe := 0; hh := false
end;
0: r^.fe := 1;
1: begin {Debe valer 2. Desequilibrio derecha}
n1 := r^.de;
if (n1^.fe = 1) then rsd (r, n1) {desequilibrio dcha}
else rddi (r, n1);
hh := false
end
end; {case}
end {if}
else begin {Clave = r^.info}
writeln (‘No está previsto insertar claves repetidas’);
hh := false
end
105
end;
SUPRIMIR EN AVL
•
Sigue la estrategia del algoritmo de supresión
en árboles binarios de búsqueda.
•
Al suprimir un nodo con cierta clave, el árbol
resultante debe seguir siendo un árbol
equilibrado.
•
Una vez eliminado un nodo siguiendo los
criterios ABB, se regresa por el camino
calculando los nuevos factores de equilibrio
(Fe).
•
Si en alguno de los nodos se viola el criterio
de equilibrio debe restaurarse el mismo,
teniendo en cuenta que pueden producirse
más de una rotación en el retroceso.
•
En los procedimientos el argumento boolean
hh, será activado cuando la altura del árbol
disminuya por eliminación de nodo o
reestructuración del subárbol.
106
SURPIMIR EN AVL
•
Casos en la reestructuración:
Caso A: Eliminar el nodo con clave 42
Rotación I, porque n^.fe := -2 y n1^.fe < = 0
107
SUPRIMIR EN AVL
•
Casos en la reestructuración:
Caso B: Eliminar el nodo con clave 21
El Fe del nodo
visitado disminuye
en 1 si la eliminación
se hizo por su rama
derecha y se
incrementa en 1 si la
eliminación se hizo
por su rama
izquierda.
Rotación DI, porque n^.fe := 2 y n1^.fe < 0
108
SUPRIMIR EN AVL
•
Casos en la reestructuración:
Caso C: Eliminar el nodo con clave 25
Rotación D, porque n^.fe := 2 y n1^.fe >= 0
109
SUPRIMIR EN AVL
•
Casos en la reestructuración:
Caso B: Reestructurar 65:
Rotación DI, porque n^.fe := 2 y n1^.fe < 0
110
Diseño e implementación
de árboles AVL
•
SUPRIMIR:
procedure EquilibrarI (var n: tArbolE; var hh:
var n1: tArbolE;
boolean);
begin
case n^.fe of
-1: n^.fe := 0;
0 : begin
n^.fe := 1; hh := false
end;
1: begin {Hay que restaurar el equilibrio}
n1:= n^.de;
if n1^.fe >=0 then
begin
if n1^.fe = 0 then hh := false; {no disminuye h}
rsd (n, n1)
end
else rddi (n, n1)
end;
111
end
end;
Diseño e implementación
de árboles AVL
•
SUPRIMIR:
procedure EquilibrarD (var n: tArbolE; var hh:
var n1: tArbolE;
boolean);
begin
case n^.fe of
1 : n^.fe := 0;
0 : begin
n^.fe := -1; hh := false
end;
-1: begin {Hay que restaurar el equilibrio}
n1:= n^.iz;
if n1^.fe <=0 then
begin
if n1^.fe = 0 then hh := false;
rsi (n, n1)
end
else rdid (n, n1)
end;
112
end
end;
Diseño e implementación
de árboles AVL
•
SUPRIMIR:
procedure SuprimirE (var r: tArbolE; var hh:
boolean; Clave: tInfo);
var q: tArbolE;
procedure bor (var d: tArbolE; var hh: boolean);
begin
if d^.de <> nil then
begin
bor (d^.de,hh);
if hh then EquilibrarD (d, hh);
end
else begin
q^.info := d^.info;
q := d;
d := d^.iz;
hh := true
end
end;
113
Diseño e implementación
de árboles AVL
•
SUPRIMIR:
begin {Suprimir}
if not EsVacio(r) then
if Clave < r^.info then
begin
Suprimir (r^.iz, hh, Clave);
if hh then EquilibrarI (r, hh)
end
else if Clave > r^.info then
begin
Suprimir (r^.de, hh, Clave);
if hh then EquilibrarD (r, hh)
end
else begin {Ha sido encontrado el nodo}
q := r;
if q^.de = nil then
begin
r := q^.iz;
hh:= true {Disminuye la altura}
114
end
(Sigue)
Diseño e implementación
de árboles AVL
•
SUPRIMIR:
else if q^.iz = nil then
begin
r := q^.de;
hh := true
end
else begin
bor ( q^.iz, hh);
if hh then EquilibrarI (r, hh)
end
dispose (q);
end {else encontrar nodo}
end;
115
Universidad de Valladolid
Departamento de informática
Campus de Segovia
Estructura de datos
Tema 5:Otros árboles
116
ÍNDICE
Tercera parte:
• Árboles generales
• Bosques
• Árboles enhebrados
117
ÁRBOLES GENERALES
•
Un árbol de otro grado se puede transformar
a binario.
•
Pasos:
a) Quedarse con el enlace al hijo situado más
a la izquierda de cada nodo.
b) El hermano derecho más próximo se sitúa
como subárbol derecho del hermano
izquierdo.
118
ÁRBOLES GENERALES
1.
2.
3. El nodo raíz es A
119
BOSQUES
• Un bosque es un conjunto de dos o más
árboles disjuntos.
• Para poderse transformar a un árbol
binario, los árboles disjuntos tienen que
estar ordenados.
• Pasos:
a) Transformar cada árbol del bosque en
binario según el criterio de transformación
de árboles generales.
b) Situar el nodo raíz de cada árbol como
subárbol derecho del árbol más situado a su
izquierda.
120
BOSQUES
Bosque:
Árbol binario:
121
BOSQUES
• Recorrido preorden:
a) Visitar la raíz del primer árbol.
b) Recorrer los subárboles del primer árbol (en
preorden).
c) Recorrer los árboles restantes (en preorden).
Equivale a recorrer en preorden el árbol binario
correspondiente.
Resultado: A-B-C-D-E-F-G-H-I
122
BOSQUES
• Recorrido postorden:
a) Recorrer los subárboles del primer árbol (en
postorden).
b) Visitar la raíz del primer árbol.
c) Recorrer los árboles restantes (en postorden).
Equivale a recorrer enorden el árbol binario.
Resultado: B-C-D-A-F-E-H-I-G
123
ÁRBOLES ENHEBRADOS
• Una forma de aprovechar los nodos a nil de un
árbol binario consiste en utilizarlos como
apuntadores a otros nodos del árbol.
• A estos punteros se les llama hebras:
a) El puntero derecho de un nodo hoja apunta
al nodo sucesor del árbol en el recorrido
enorden.
b) El puntero izquierdo apunta al nodo
predecesor.
124
ÁRBOLES ENHEBRADOS
• Para distinguir los hijos de las hebras,
modificamos la estructura del árbol binario.
• Se introducen dos campos booleanos que
indican si el puntero es un enlace a un hijo o a
una hebra:
type
tipoInfo = ...;
tArbolEn=^Nodo;
Nodo = record
info: tipoInfo;
hiz, hde: boolean;
iz, de: tArbolEn
end;
• Así si hiz ó hde valen true, esto hace que iz y
de sean hebras.
125
ÁRBOLES ENHEBRADOS
• Se incluye un nodo cabecera que no tiene
información. Su estructura es:
126