Consideraciones sobre la altura de los nodos

Como vimos en la definici�n del tipo abstracto para nodos de �rboles AVL, se necesitar� tener acceso a la altura cada nodo del �rbol en tiempo constante. Dado que una funci�n para hallar la altura de un nodo dado en un �rbol tendr� un tiempo de ejecuci�n de O(log(n)) peor caso, no nos queda otra alternativa que almacenar una variable altura en cada nodo e irla actualizando en las inserciones y eliminaciones que se efect�en sobre el �rbol.

Como el lector ya deber�a saber, una funci�n para calcular la altura de un nodo puede escribirse recursivamente como:

int altura(AVLTree *t)
{
  if(es_vacio(t)) 
    return -1;
  else 
    return max(altura(izquierdo(t)), altura(derecho(t)));
}

Queremos que la altura de un �rbol que consta de s�lo un nodo sea 0. Entonces debemos definir la altura de un �rbol vac�o como -1.

Sin embargo, no podemos darnos el lujo de tener una funci�n cuyo tiempo de ejecuci�n siempre es O(n) ya que, como dijimos, necesitamos la altura de un nodo en tiempo constante. Para ello, redefiniremos la funci�n de la siguiente manera, aprovechando el campo altura que ahora tiene cada nodo del �rbol.

int altura (AVLTree * t)
{
  if(es_vacio(t))
    return -1;
  else 
    return t->altura;
}

As�, es importante tener una funci�n que nos permita actualizar la altura de un nodo cualquiera del �rbol y cuyo tiempo de ejecuci�n sea O(1) en el peor de los casos. A continuaci�n se lista una tal funci�n:

void
actualizar_altura (AVLTree * t)
{
  if(!es_vacio(t))
    t->altura = max (altura ((t)->izq), altura ((t)->der)) + 1;
}