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:

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;
	}
    }
}