Eliminaci�n
La estrategia para dise�ar el algoritmo de eliminaci�n sobre �rboles AVL es la misma que para la inserci�n: Se utiliza el mismo algoritmo que sobre �rboles binarios de b�squeda, pero en cada recursi�n se detectan y corrijen errores por medio de balancear() y se actualiza la altura del nodo actual.
Recordamos un poco la idea del algoritmo de eliminaci�n sobre �rboles binarios de b�squeda. Primero se recorre el �rbol para detectar el nodo a eliminar. Una vez hecho esto hay tres casos a diferenciar por su complejidad:
Si dicho nodo es una hoja procedemos a eliminarlos de inmediato, sin m�s.
Si dicho nodo tiene un s�lo hijo, el nodo puede eliminarse despu�s de ajustar un apuntador del padre para saltar el nodo. Esto se muestra en Figure 13.
Si dicho nodo tiene dos hijos el caso es un poco m�s complicado. Lo que se estila hacer (y que de hecho se hace en el algoritmo gracias a la funci�n auxiliar eliminar_min()) reemplazar el nodo actual por el menor nodo de su sub�rbol derecho (y luego eliminar �ste).
void eliminar (AVLTree ** t, int x);
/* elimina x del �rbol en un tiempo O(log(n)) peor caso.
Precondici�n: existe un nodo con valor x en el �rbol
t. */
int eliminar_min (AVLTree ** t);
/* Funci�n auxiliar a eliminar(). Elimina el menor nodo del �rbol
*t devolviendo su contenido (el cual no se libera de
memoria). Se actualizan las alturas de los nodos.
Precondici�n: !es_vacio(*t) */
void
eliminar (AVLTree ** t, int x)
{
AVLTree *aux;
if (x < raiz (*t))
eliminar (&(*t)->izq, x);
else if (x > raiz (*t))
eliminar (&(*t)->der, x);
else /* coincidencia! */
{
if (es_vacio (izquierdo (*t)) && es_vacio (derecho (*t)))
{/* es una hoja */
free (*t);
(*t) = vacio();
}
else if (es_vacio (izquierdo (*t)))
{/* sub�rbol izquierdo vacio */
aux = (*t);
(*t) = (*t)->der;
free (aux);
}
else if (es_vacio (derecho (*t)))
{/* sub�rbol derecho vacio */
aux = (*t);
(*t) = (*t)->izq;
free (aux);
}
else /* caso m�s complicado */
{
(*t)->dato = eliminar_min (&(*t)->der);
}
}
balancear (t);
actualizar_altura (*t);
}
int
eliminar_min (AVLTree ** t)
{
if (es_vacio (*t))
{
fprintf (stderr,
"No se respeta precondici�n de eliminar_min()\n");
exit(0);
}
else
{
if (!es_vacio (izquierdo (*t)))
{
int x = eliminar_min (&(*t)->izq);
balancear (t);
actualizar_altura (*t);
return x;
}
else
{
AVLTree *aux = (*t);
int x = raiz (aux);
*t = derecho (*t);
free (aux);
balancear (t);
actualizar_altura (*t);
return x;
}
}
}
|