Inserción

Como dijimos en the Section called Balance del árbol, implementaremos la inserción de elementos en un árbol AVL de forma análoga a cómo lo haríamos para árboles binarios de búsqueda salvo que en cada recursión del algoritmo verificaremos y corregiremos el equilibrio del árbol. También es importante ir actualizando las alturas de cada nodo en cada recursión dado que las rotaciones, inserciónes y eliminaciones pueden modificarlas.

Dado que ya vimos funciones tanto para balancear un árbol y para actualizar la altura de un nodo (ambas de tiempo de ejecución constante), estamos listos para implementar el algoritmo de inserción. Esperamos que sea intuitivo.

void insertar (AVLTree ** t, int x);
/* inserta x en el árbol en un tiempo O(log(n)) peor caso. */


void
insertar (AVLTree ** t, int x)
{
  if (es_vacio (*t))
    *t = hacer (x, vacio (), vacio ());	/* altura actualizada
					   automáticamente */
  else
    {
      if (x < raiz (*t))
	insertar (&(*t)->izq, x);

      else
	insertar (&(*t)->der, x);

      balancear (t);
      actualizar_altura (*t);
    }
}