3.2. Relaciones de equivalencia.

• Si un nodo es raíz, C[i] indica (en números negativos) la profundidad del árbol (cero si el árbol no tiene hojas).

• Al unir dos raíces, apuntar la de menor profundidad a la de mayor.

• En la búsqueda se realiza una compresión del árbol. Si encontramos que la raíz del árbol para x es z, entonces apuntar directamente C[x]= z.

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

begin

if C[raiz2] < C[raiz1] then

C[raiz1]:= raiz2

else

begin

if C[raiz2] = C[raiz1] then

C[raiz1]:= C[raiz1] - 1;

C[raiz2]:= raiz1;

end;

end;

function Búsqueda (x: Tipo_elemento; var C: Relacion_equiv): Tipo_conj;

begin

if C[x] ? 0 then

return x

else

begin

C[x]:= Búsqueda (C[x], C);

return C[x];

end;

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica