3.2. Relaciones de equivalencia.

• El procedimiento Unión supone que raiz1 y raiz2 representan las clases de equivalencia (son raíces de los árboles). ¿Cómo sería la operación para unir las clases asociadas a dos elementos?

• En el caso medio la operación Encuentra es de orden menor que O(log n). Sin embargo, en el peor caso los árboles son cadenas y el coste es O(n).

• Debemos garantizar que los árboles sean lo más anchos posible.

procedure Inicia (var C: Relacion_equiv);

var

i: Tipo_conj;

begin

for i:= 1 to num_elems do

C[i]:= 0;

end;

procedure Unión (var C: Relacion_equiv; raiz1, raiz2: Tipo_conj);

begin

C[raiz2]:= raiz1;

end;

function Encuentra (x: Tipo_elemento; var C: Relacion_equiv): Tipo_conj;

begin

if C[x] = 0 then

return x

else

return Encuentra (C[x], C);

end;

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica