Download Tema 3. Representación de Conjuntos

Tema 3. Representación de
Conjuntos
1
OBJETIVOS
• Estudiar los conjuntos desde un punto de
vista algorítmico (conjuntos dinámicos).
• Estudiar técnicas de representación de
conjuntos (algoritmos de manipulación).
• Estudiar los tipos de datos: diccionario, cola
de prioridad.
• Aprender a seleccionar el tipo de datos y la
implementación más adecuados al problema
2
a resolver.
ÍNDICE
1. Conceptos Generales
2. Representaciones básicas:listas
3. Árboles Binarios de Búsqueda
4.Tablas de Dispersión
5. Árboles Parcialmente Ordenados (Heaps)
6. Conjuntos Disjuntos (Mfsets)
3
BIBLIOGRAFÍA
• T.H. Cormen, C.E. Leiserson, R.L. Rivest
Introduction to Algorithms. MIT Press, 1990.
– Parte III: Introducción y capítulos 12 y 13
– Parte V: Capítulos 19 y 22
• G. Brassard, P. Bratley.
Fundamentos de Algoritmia. Prentice Hall, 1997.
Sección 1.9.
• Aho A.V., Hopcroft J.E., Ullman J.E.
Estructuras de datos y Algoritmos.
Addison-Wesley, 1988. Capítulos 4 y 5
4
1. CONCEPTOS GENERALES
• Elementos de un conjunto (dinámico).
Típicamente:
– clave: campo de identificación
– información satélite: asociada al objeto
• Algunos conjuntos se caracterizan porque
en el conjunto de claves se puede establecer
una relación de orden total.
– En este caso se puede definir el elemento
mínimo de un conjunto, o el sucesor.
5
Operaciones sobre conjuntos
• Consultoras:
– Buscar, Mínimo, Máximo, Predecesor, Sucesor
• Modificadoras:
– Insertar, Borrar
6
Operaciones sobre conjuntos (cont.)
– BUSCA(S,k): dado un cjto S y una clave k
devuelve la posición x tal que clave[x]=k, o un
valor especial si x∉S.
– INSERTA(S,x): añade a S el elemento
apuntado por x.
– BORRA(S,x): borra el elemento apuntado por x
de S
7
Operaciones sobre conjuntos (cont.)
– MÍNIMO(S): devuelve el elemento de S con la
clave más pequeña
– MÁXIMO(S): devuelve el elemento de S con la
clave más grande.
– SUCESOR(S,x): devuelve el elemento de clave
inmediatamente superior a la de x o un valor
especial si x es el máximo
– PREDECESOR(S,x): devuelve el elemento de
clave inmediatamente inferior a la de x o un
8
valor especial si x es el mínimo
Algunos tipos de conjuntos dinámicos
• Pilas y Colas
– Se inserta y se borra un elemento
predeterminado
– Pila: política LIFO
– Cola: política FIFO
• Diccionarios
– Operaciones Inserta, Borra y Busca
• Colas de prioridad
– Operaciones Inserta, Elimina_Max
9
2. Implementaciones básicas
• Vector de bits
• Listas enlazadas
–
–
–
–
doblemente enlazadas
ordenadas
circulares
otras...
10
Ejemplo.
• Lista doblemente enlazada. Notación
– Una lista L tiene el atributo primero para acceder al principio de la
misma (primero[L])
– Si x es un elemento de la lista:
• clave[x] es la clave
• suc[x] apunta a su sucesor
• pred[x] apunta a su predecesor
– Si pred[x]=NIL x no tiene predecesor, es el primer elemento de la
lista
– Si suc[x]=NIL x no tiene sucesor, es el último elemento de la lista
11
Ejemplo. Buscar
Buscar(L,k)
/* Encuentra el primer elemento con clave k en L y devuelve su posición. Si no lo
encuentra devuelve NIL*/
x:=primero[L];
mientras x<>NIL y clave[x]<>k x:=suc[x]
devuelve x
El coste es O(n), con n=|L| (en el peor caso hay que recorrer
toda la lista).
12
Ejemplo. Insertar
Inserta(L,x)
/* Dado un elemento x lo inserta en cabeza de lista L*/
suc[x]:=primero[L];
Si primero[L]<>NIL entonces
pred[primero[L]]:=x
primero[L]:=x
pred[x]:=NIL
El coste es O(1).
13
Ejercicio. Borrar
Borra(L,x)
/* Dado un elemento x lo borra de la lista L */
Si pred[x]<>NIL entonces
suc[pred[x]]:=suc[x]
sino primero[L]:=suc[x]
Si suc[x]<>NIL entonces
pred[suc[x]]:=pred[x]
El coste es O(1).
Si queremos borrar un elemento con una clave
determinada primero hay que Buscar. Coste O(n)
14
Estudio comparativo de costes
Operación
Lista
BUSCA(S,k)
O(|S|)
Lista
ordenada
O(|S|)
INSERTA(S,x)
O(1)
O(|S|)
BORRA(S,x)
O(|1|)
O(|1|)
MÍNIMO(S) /
MÁXIMO(S)
O(|S|)
O(1)
PREDECESOR(S,x)
/ SUCESOR(S,x)
O(|S|)
O(|S|)
15
3) ÁRBOLES BINARIOS DE BÚSQUEDA
Un árbol binario es de búsqueda si:
• Todos los elementos del subárbol izquierdo son
menores que el de la raíz
• Todos los elementos del subárbol derecho son
mayores que el de la raíz
• Propiedad: Si se listan los elementos según recorrido en
inorden resulta una secuencia ordenada.
Ejercicio: ¿Cuál es la diferencia entre la propiedad de los ABB y la de Heaps?, ¿Puede
utilizarse la propiedad de Heaps para listar de forma ordenada las claves de un árbol
con n nodos en tiempo O(n)?
16
EJEMPLOS
Ejemplos: Representación del conjunto S={5,2,7,4,8,3}
5
3
2
2
7
4
3
8
7
5
8
4
Ejercicio: Dibujar árboles binarios de búsqueda de alturas 2,3,4,5,6
para el conjunto de claves {1,4,5,10,16,17,21}
17
IMPLEMENTACIÓN
x
Der[x]
5
Izq[x]
3
2
7
4
8
18
IMPLEMENTACIÓN DE OPERACIONES
SOBRE CONJUNTOS
•
•
•
•
•
Busca (S,k)
Mínimo(S) y Máximo(S)
Sucesor(S,x) y Predecesor(S,x)
Inserta(S,x)
Borra(S,x)
19
BÚSQUEDA DE UNA CLAVE EN UN ABB
{x es un puntero a la raíz de un ABB y k es una clave}
ABB_BUSCAR(x,k)
{Devuelve un puntero al nodo con clave k si existe o
Nil si no existe}
Si
x=nil ∨ k=clave[x]
Coste O(h)
entonces devuelve x
Si k<clave[x]
entonces devuelve ABB_BUSCAR(izq[x],k)
sino devuelve ABB_BUSCAR(der[x],k)
ABB_BUSCAR(T,k)
20
BÚSQUEDA DE UNA CLAVE EN UN ABB(cont)
{x es un puntero a la raíz de un ABB y k es una clave}
ABB_BUSCAR_I(x,k)
{Devuelve un puntero al nodo con clave k si existe o Nil
si no existe}
mientras
x≠nil ∧ k≠clave[x] hacer
si k<clave[x]
entonces x:=izq[x]
sino x:=der[x]
fsi
devuelve x
ABB_BUSCAR(T,k)
21
MÍNIMO Y MÁXIMO EN UN ABB
ABB_MÍNIMO (x)
{Devuelve un puntero al nodo con la clave más pequeña del
árbol x, x <> nil}
mientras izq[x]≠nil hacer x:=izq[x]
devuelve x
ABB_MÁXIMO (x)
{Devuelve un puntero al nodo con la clave más grande del
árbol x, x <> nil}
mientras der[x]≠nil hacer x:=der[x]
devuelve x
22
SUCESOR EN UN ABB
15
6
3
2
18
7
4
17
20
13
9
Sucesor del 15?
Sucesor del 13?
23
SUCESOR EN UN ABB
ABB_SUCESOR (x)
{Devuelve un puntero al sucesor del nodo x si existe o
Nil si la clave de x es la mayor del ABB}
si der[x]≠nil entonces
devuelve ABB_MÍNIMO(der[x])
{buscar el antecesor más pequeño de x cuyo hijo
izquierdo también sea antecesor de x}
y:=p[x];
mientras y≠nil ∧ x=der[y] hacer
x:=y;
y:=p[y];
Coste O(h)
devuelve y
24
INSERTAR EN UN ABB
ABB_INSERTA (T,z)
{Inserta un valor v en una posición adecuada en un ABB T,
clave[z]=v,izq[z]=nil, der[z]=nil}
y:=nil;x:=T;
mientras x≠nil hacer
y:=x;
si clave[z]<clave[x] entonces x:=izq[x]
sino x:=der[x]
p[z]:=y;
si y=nil entonces T:=z
sino si clave[z]<clave[y]entonces izq[y]:=z
sino der[y]:=z
25
Insertar en un ABB. Ejemplo
Insertar un nodo con clave 13
12
6
3
18
7
20
15
13
17
26
BORRAR EN UN ABB. Ejemplo
Borrar z
15
Caso 3: Tiene 2 hijos 5
z
3
Caso 2: Solo tiene 1 hijo
16
12
20
Caso 1: No tiene hijos
10
z
13
z
18
23
6
7
27
BORRAR EN UN ABB. Ejemplo (cont.)
15
Caso 1: z no tiene hijos
5
16
3
12
10
20
18
23
6
7
28
BORRAR EN UN ABB. Ejemplo (cont.)
15
Caso 2: z tiene 1 hijo
5
16
3
z
12
10
20
13
18
23
6
7
29
BORRAR EN UN ABB. Ejemplo (cont.)
15
Caso 3: z tiene 2 hijos
5 z
16
intercambio
3
12
10
20
18
23
Sucesor con 1 hijo 6
7
30
BORRAR EN UN ABB
ABB_BORRA (T,z)
si izq[z]=nil ∨ der[z]=nil entonces y:=z
sino y:=ABB_SUCESOR(z);
si izq[y]≠nil entonces x:=izq[y]
sino x:=der[y]
si x ≠nil entonces p[x]:=p[y];
si p[y]=nil entonces T:=x
sino si y=izq[p[y]] entonces izq[p[y]]:=x
sino der[p[y]]:=x
si y≠z entonces clave[z]:=clave[y]
Si y tiene otros campos copiar
devuelve y
31
4. TABLAS DE DISPERSIÓN
• Estructura de datos especialmente diseñada para la
implementación de DICCIONARIOS.
• Puntos a tratar:
–
–
–
–
Definición
Resolución de colisiones
Diccionarios
Funciones de dispersión
32
Tablas de direccionamiento directo
• Si |U|<<< y asumimos que no hay dos elementos con la
misma clave:
T
0
U
información
1
0
7
9
4
1
S
clave
2
6
5
3
2
2
3
3
4
5
5
6
8
7
8
U={0,1,..,9}; S={2,3,5,8}
8
9
33
Tablas de Dispersión (cont.)
• Complejidad espacial:
– Sea |U|el tamaño del conjunto universal y |S| el tamaño
del conjunto a representar. El espacio en memoria para
representar S es Θ (|U|).
• Si |U|>>>>
??
• Si |S|<<<<|U| ??
• Usar un vector T[0..B-1], con B<<|U|. Un
elemento de clave k se almacena en la posición h(k). T es
una tabla de dispersión (tabla hash) y h es la función de
dispersión. A cada una de las T[j] se les llama cubeta.
34
Tablas de dispersión (cont.)
l
Función de dispersión
h: U -> {0,1,2,..,B-1}, Coste Θ(1)
T
0
U
h(k1)
h(k4)
S
k1
h(k2)=h(k5) COLISIONES
k2
k4
k5
k3
h(k3)
B-1
35
Tratamiento de las colisiones
• Definir una función de dispersión que
minimice el número de colisiones
(Dispersión efectiva).
• Dos métodos para tratar las colisiones:
– Encadenamiento
– Direccionamiento abierto
36
Resolución de colisiones por encadenamiento
• Lista de claves que tienen el mismo valor de
la función de dispersión
T[j]: puntero a la cabeza de lista de aquellos
elementos cuya función hash es j (h(k)=j)
37
Resolución de colisiones por encadenamiento
T
0
U
k1
k4
k6
S
k1
k2
k4
k6
k7
k2
k5
k7
k5
k3
k3
B-1
38
Implementación de un diccionario
• Buscar(T,k)
Busca elemento con clave k en la lista T[h(k)]
• Insertar(T,x)
Inserta x en cabeza de la lista T[h(clave[x])]
• Borrar(T,x)
Borra el elemento x de la lista T[h(clave[x])]
39
Análisis de costes
• Insertar: O(1)
– Si tenemos que comprobar previamente que no
está: el coste de Buscar.
• Buscar: O(|S|)en el peor de los casos
– Todos los elementos de S están en la misma
cubeta
• Borrar: O(1)
– Si no tenemos la dirección hay que buscar
previamente el elemento: el coste de Buscar.
40
Análisis del CM de Buscar
• Asumimos hashing uniforme simple:
– La probabilidad de que un elemento de U se
almacene en cualquier posición de la tabla es la
misma.
• Asumimos que el coste de calcular h es
O(1)
• Suponemos que las colisiones se han
resuelto por encadenamiento.
• Definimos el factor de carga de la tabla
como α≡n/B, donde n=|S|.
41
CM de Buscar (cont.)
• El coste de Buscar es O(1+α)
– Si n es proporcional a B, n∈Θ(B), α=n/B∈Θ(1)
– Y por lo tanto el coste de Buscar es O(1)
– Así, todas las operaciones del tipo diccionario
se pueden efectuar con coste constante
42
LA FUNCIÓN DE DISPERSIÓN
• Hashing Uniforme Simple:
• Definición:
∑
1
p(k) =
B
k / h(k)= j
– Método de la División:
h(k)= k mod B
Restricción: B nº primo no cercano a una potencia de 2.
– Método de la Multiplicación:
h(k)= B *(k*A-[k*A]), o<A<1
B se suele tomar una potencia de 2
A≅(51/2-1)/2=0.6180339887..
– Hashing Universal
43
Funciones hash sobre cadenas
• f1(s)
x:=0;
for i:=1 to length(s) do x:=x+ord(s[i])
dev x mod B
Problemas:
–
f1(abc)=f1(bca)
• f2(s)
dev (ord(s[1])+255ord(s[2])+2552ord(s[3]))modB
44
Funciones hash sobre cadenas (cont.)
• f3(s)
x:=ord(s[1]);
for i:=2 to length(s) do
x:=(x*256)+ord(s[i]))mod B
dev x
Problemas:
–
Cálculo más costoso (bucle con mod)
45
5. ÁRBOLES PARCIALMENTE
ORDENADOS
• Arbol Binario Completo:
Un AB es completo si tiene todos sus niveles completos,
a excepción quizás del último en el cuál todas las hojas
estan tan a la izquierda como sea posible.
• Árbol parcialmente ordenado (Montículo o
Heap):
Es un árbol binario completo,con la propiedad de orden:
el valor de cualquier nodo es mayor o igual (o menor o
igual) que el de sus nodos hijos.
Heaps
Ejemplo:
150
125
80
15
20
30
75
25
72
15
• Propiedades:
– todas las ramas del árbol son secuencias ordenadas,
– la raíz del árbol es el nodo de máximo (mínimo) valor,
y
– todo subárbol de un heap es, a su vez, un heap.
Implementación de un heap
• Un AB completo, y por lo tanto un heap admite una
representación en forma de vector, numerando sus nodos de
arriba abajo y de izquierda a derecha, fijando este orden la
posición en el vector:
v[1]
150
75
125
80
15
30
20
v
25
v[4]
72
15
v[5] v[6]
v[8] v[9] v[10]
150 125 75
1
v[3]
v[2]
2
3
80
30
25
4
5
6
72
15
20
7
8
9
15
10
v[7]
Implementación de un heap (cont.)
• v[1]es la raíz,
• Dado un nodo v[i],
– si 2i≤n entonces v[2i]es el nodo hijo izquierdo,
– si 2i+1≤ n entonces v[2i+1] es el nodo hijo derecho,
– si i≠1, v[idiv2] es el nodo padre.
• Si es heap: ∀i:2≤i≤n:v[idiv2]≥v[i]
• Un montículo de n elementos tiene una altura
Θ(log n).
Operaciones básicas sobre Heaps
• Demostrarán la utilidad de esta estructura para:
– el diseño de un algoritmo de ordenación rápido
(HeapSort)
– la representación de colas de prioridad
Operaciones básicas sobre Heaps
(cont.)
– Ajustar, es la operación clave para mantener la
propiedad de heap. Coste O(log n) (Heapify)
– Construir_heap, para convertir un vector, en principio
desordenado, en un heap. Coste O(n). (Build_Heap)
– HeapSort, para ordenar un vector. Coste O(nlogn)
– EliminaMax e Inserta, para extraer el máximo de un
conjunto y eliminarlo y para insertar, características de
las colas de prioridad. Costes O(log n) (Extraxt_Max e
Insert)
Ajustar. Algoritmo.
{Izq(i) y Der(i) son heaps y 1<=i<=n}
Ajustar (A,i)
O(log n), n=Talla[A]
l:=Izq(i); r:=Der(i);
Si l<=Talla[A] y A[l]>A[i]
entonces mayor:=l sino mayor:=i;
Si r<=Talla[A] y A[r]>A[mayor]
entonces mayor:=r
Si mayor<>i entonces
intercambiar(A[i],A[mayor])
Ajustar(A,mayor)
{A[i..n]es un heap}
Construir un heap. Algoritmo.
Construir_Heap (A)
{ Convierte un vector A[1..n], donde n=Longitud[A], en un heap }
Talla[A]:=Longitud[A]
For i:=[Longitud[A]/2] downto 1 do
Ajustar(A,i)
Complejidad Temporal:
•El coste de ajustar un nodo es proporcional a su altura
•En un heap de n elementos hay como mucho (n/2h+1)+1 nodos de altura h.
T(n) =
log 2 n
∑
h=0
 n 

  h + 1  + 1 ∗ h ∈ O(n) + Θ(log 2 n) ∈ O(n)
2 

HeapSort
HeapSort (A)
/*Ordena el vector A[1..n], donde n=Longitud[A]*/
Construir_Heap(A);
For i:=Longitud[A] downto 2 do
intercambiar(A[1],A[i]);
Talla[A]:=Talla[A]-1;
Ajustar(A,1)
Complejidad Temporal:
Coste de Construir_heap + Coste del bucle
T(n)
∈O(n)+O(nlogn) ∈O(nlogn)
Colas de Prioridad
• Conjunto con las operaciones:
– Insertar(S,x): inserta el elemento x e el conjunto
S.
– Máximo(S): devuelve el elemento de S cuya
clave sea máxima.
– EliminaMax(S) elimina y devuelve el elemento
de S cuya clave sea máxima.
EliminaMax.
EliminaMax (A)
/* Devuelve el máximo de A y lo borra */
Si Talla[A]<1 entonces Error
Coste temporal O(logn)
sino
Max:=A[1];
A[1]:=A[Talla[A]];
Talla[A]:=Talla[A]-1;
Ajustar(A,1);
devuelve Max
Insertar. Algoritmo.
Insertar(A,k)
/* Añade k al Heap A */
Talla[A]:=Talla[A]+1;
i:=Talla[A];
while i>1 and A[Padre[i]]<k do
A[i]:= A[Padre[i]];
i:=Padre[i]; Coste temporal O(logn)
A[i]:=k;
IMPLEMENTACIÓN DE CONJUNTOS. RESUMEN
Cola Prioridad
Diccionario
COSTE PROMEDIO
h∈O(log n)
Busca(S,k)
Lista
ordenada
O(n)
Inserta(S,x)
Tabla Hash
He a p
O(logn)
O(1)
O(n)
O(n)
O(logn)
O(1)
O(logn)
Borra(S,x)
O(n)
O(logn)
O(1)
O(logn)
Mínimo(S)
O(1)
O(logn)
O(n)
O(1)
Eli_Min(S)
O(1)
O(logn)
O(n)
O(logn)
Operación
AB B
S: conjunto; n=|S|;x: puntero a objeto; k:clave del objeto
58
E. de Datos para Conjuntos Disjuntos
• Un MFSet (Merge-Find Set) es una estructura tipo conjunto
en la que los elementos están organizados en subconjuntos
disjuntos y el nº de elementos es fijo (no se añaden ni se
borran). Las operaciones características son:
– Combina: hace la unión de dos conjuntos disjuntos (Merge)
– Encuentra: dado un elemento debe determinar a qué conjunto
pertenece (Find)
59
MFSets. Ejemplo
A
1
C
B
3
7
12
5
4
6
13
2
10
8
11
9
Aplicaciones:
•Equivalencia entre autómatas finitos
•Determinación de componentes conexas de un gnd
•Obtención del AEM en un gnd
60
Operaciones sobre MFSets
• Si x e y son elementos (objetos) del conjunto:
– Construir_Cjto(x): crea un nuevo conjunto cuyo único
miembro es x.
– Combina(x,y): une los conjuntos a los que pertenecen x e
y
– Encuentra(x): devuelve un puntero al representante del
conjunto al que pertenece x.
61
Componentes conexas de un grafo
• Sea G=(V,E) un grafo no dirigido
– V[G] es el conjunto de vértices
– E[G] es el conjunto de arcos
ComponentesConexas(G)
∀v∈V[G] hacer Construir_Cjto(v);
∀(u,v)∈E[G] hacer
Si Encuentra(u)≠Encuentra(v)
entonces Combina(u,v)
62
Ejemplo
a
b
e
c
d
g
f
h
j
i
63
Ejemplo. Iteración 7
a
b
e
c
d
g
Arco
f
h
j
i
Colección de conjuntos disjuntos
{a}
{b}
{c} {d} {e}
{f}
{g}
{h}
{i}
{j}
(b,d)
{a}
{b,d}
{c}
{e}
{f}
{g}
{h}
{i}
{j}
(e,g)
{a}
{b,d}
{c}
{e,g}
{f}
{h}
{i}
{j}
(a,c)
{a,c}
{b,d}
{e,g}
{f}
{h}
{i}
{j}
(h,i)
{a,c}
{b,d}
{e,g}
{f}
{h,i}
{j}
(a,b)
{a,c,b,d}
{e,g}
{f}
{h,i}
{j}
(e,f)
{a,c,b,d}
{e,g,f}
{h,i}
{j}
(b,c)
{a,c,b,d}
{e,g,f}
{h,i}
{j}
64
Representación de un MFSet
• La más sencilla...
• MFSet=vector[1..N] de TipoNombreCjto;
– N es el número de elementos
– M[x] es el conjunto al que pertenece x
• Operaciones
– Encuentra(x): es un acceso a M[x], O(1)
– Combina(x,y): recorrido sobre el vector, O(N)
• Coste amortizado:
– Una secuencia de N-1 operaciones combina tiene un
coste O(N2)
65
Ejemplo
{{1},{2},{3},{4},{5}}
Combina(1,2)
{{1,2},{3},{4},{5}}
Combina(2,3)
{{1,2,3},{4}{5}}
Combina(3,4)
{{1,2,3,4},{5}}
Combina(4,5)
{{1,2,3,4,5}}
1 2
3
4
5
1
2
3
4
5
1 1
3
4
5
1
2
3
4
5
1 1
1
4
5
1
2
3
4
5
1 1
1
1
5
1
2
3
4
5
1 1
1
1
1
1
3
4
5
2
66
MFSet. Representación en árbol
• Cada subconjunto es un árbol en el que cada nodo apunta
al padre.
• La raíz del árbol puede usarse para nombrar el conjunto.
• El MFSet estará representado por una colección de árboles
(un bosque).
3
3
1 7
5
4
9
2
8 10
6
1
8
5
6
9
7 4
10
2
67
MFSet. Rep. en árbol (cont.)
• Los árboles no son necesariamente binarios, pero
su representación es muy fácil ya que sólo
necesitaremos un apuntador al padre:
– MFSet= vector[1..N] de enteros;
– M[i] es el padre del elemento i;
– Podemos hacer que la raíz se apunte a sí mismo: i es
raíz si M[i]=i.
68
Ejemplo
3
1
8
5
6
9
7 4
10
2
5 9 3 5 3 8 5 8 8 6
1 2 3 4 5 6 7 8 9 10
69
Operaciones
• Combina: hacer que la raíz de un árbol sea
hijo del otro. Coste constante.
• Encuentra: devolver la raíz del árbol que
contiene a x. Coste proporcional a la
profundidad del nodo, que en el peor de los
casos es N-1.
• m operaciones de búsqueda tendrían un
coste O(mn) en el peor caso.
70
Mejoras del Coste. Heurísticos
• m operaciones Encuentra tienen un coste O(m)
– Combinar por Rango
– Comprimir Caminos
71
Combinar por Rango
• La idea es hacer la operación combina de
forma que la raíz del árbol con menos nodos
apunte a la raíz del árbol con más nodos.
Para ello en cada nodo se mantiene un
rango que aproxima el logaritmo de la talla
del subárbol, es una cota de la altura del
nodo.
72
Implementación de Combina
• Construir_Cjto(x)
M[x]:=x;
rango[x]:=0;
• Combina(x,y)
Une(Encuentra(x),Encuentra(y))
• Une(x,y)
Si rango[x]>rango[y] entonces p[y]:=x
sino p[x]:=y;
Si rango[x]=rango[y]
entonces rango[y]:=rango[y]+1;
73
Compresión de Caminos
• El efecto de la Compresión de Caminos
sobre la operación Encuentra es que todo
nodo en el camino de x a la raíz cambia su
padre por la raíz.
• Permite realizar las m operaciones de
búsqueda con coste O(m α(m,n)), donde
α(m,n) es una inversa de la función de
Ackerman que crece muy lentamente.
74
Operación Encuentra
1
2
3
4
Encuentra(8)=1
1
2
3
5
6
7
4
5
7
8
6
8
l
Encuentra(x)
Si x≠M[x] entonces M[x]:=Encuentra(M[x]);
devuelve M[x]
75