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