55555555

Borrado
La operación de borrado no es tan sencilla como las de búsqueda e inserción. Existen varios casos a tener en consideración:
• Borrar un nodo sin hijos ó nodo hoja:simplemente se borra y se establece a nulo el apuntador de su padre.
[pic]
Nodo a eliminar 74
• Borrar un nodo con un subárbol hijo: se borra el nodo y se asigna su subárbol hijo comosubárbol de su padre.
[pic]
Nodo a eliminar 70
• Borrar un nodo con dos subárboles hijo: la solución está en reemplazar el valor del nodo por el de su predecesor o por el de su sucesoren inorden y posteriormente borrar este nodo. Su predecesor en inorden será el nodo más a la derecha de su subárbol izquierdo (mayor nodo del subarbol izquierdo), y su sucesor el nodo mása la izquierda de su subárbol derecho (menor nodo del subarbol derecho). En la siguiente figura se muestra cómo existe la posibilidad de realizar cualquiera de ambos reemplazos:
[pic]Nodo a eliminar 59
El siguiente algoritmo en C realiza el borrado en un ABB. El procedimiento reemplazar busca la mayor clave del subárbol izquierdo y la asigna al nodo a eliminar.
voidborrar(tArbol **a, int elem)
{
void reemplazar(tArbol **a, tArbol **aux);
tArbol *aux;

if (*a == NULL)
return;

if ((*a)->clave < elem)
borrar(&(*a)->hDerecho,elem);
else if ((*a)->clave > elem)
borrar(&(*a)->hIzquierdo, elem);
else if ((*a)->clave == elem)
{
aux = *a;
if ((*a)->hIzquierdo == NULL)
*a =(*a)->hDerecho;
else if ((*a)->hDerecho == NULL)
*a = (*a)->hIzquierdo;
else
reemplazar(&(*a)->hIzquierdo, &aux);

free(aux);
}
}

void reemplazar(tArbol **a,tArbol **aux)
{
if ((*a)->hDerecho == NULL)
{
(*aux)->clave = (*a)->clave;
*aux = *a;
*a = (*a)->hIzquierdo;
}
else
reemplazar(&(*a)->hDerecho, aux);
}