C/Traballar con árbores

C
← Volver a Traballar con listas encadeadas	Traballar con árbores	Seguir con Comentarios →

Introdución á programación recursiva

Antes de comezar a aprender o que son as árbores e como traballar con elas, cómpre coñecer un pouco por riba unha forma de programar moi empregada: a “programación recursiva”.

Ata o momento as funcións que se programaron estaban escritas para ser chamadas por outras funcións ─ou polo sistema operativo no caso da función principal─ e asemade chamar a outras funcións. Existe un caso especial en que unha función se chama a si mesma ─ou máis exactamente, chama a unha función igual ca ela─. Neste caso estaremos falando de programación recursiva.

Un exemplo simple dunha función en que se pode empregar a programación recursiva sería o dunha función para calcular o factorial^[1] dun número. Seguindo o procedemento que se leva empregado ata o de agora, probablemente escribiríamos unha función como a seguinte para o cálculo do factorial:

signed long CalcularOFactorial(signed long numero)
{
  signed long factorial = 1;
  signed long indice;

  for(indice=1; indice<numero; indice++)
    factorial = factorial * indice;
  
  return factorial;
}

Porén, a programación recursiva pode axudar aquí permitindo reducir a función ao seguinte código:

signed long CalcularOFactorial(signed long numero)
{
  if(numero==1)
    return 1;
  else
    return numero * CalcularOFactorial(numero-1);
}

Este tipo de programación é o que fai posible o uso de estruturas de datos recursivas, coma as árbores ou os gráficos (ou grafos).

Introdución ás árbores

Unha árbore é unha estrutura ─unha colección organizada de datos─ dinámica non lineal recursiva almacenada en memoria interna, formada por un conxunto de nodos e un conxunto de pólas. É dinámica porque se almacena en memoria dinámica, polo que o seu tamaño ─a cantidade de nodos que contén─ pode variar durante a execución dun programa. Non é lineal porque existe máis dun camiño posible entre un elemento da estrutura e outro. E é recursiva porque cada nodo da árbore é a raíz dunha nova árbore, «unha árbore é un conxunto de árbores».

Nunha árbore existe un nodo especial, a “raíz da árbore”, que é o único nodo de nivel 0, é dicir, é o que serve de referencia para toda a árbore, do que colgan o resto de nodos ou árbores subordinadas. Como toda estrutura de datos dinámica, as árbores constan dun punteiro que sinala á árbore, e cuxo valor será nulo ─NULL─ cando non haxa árbore. Dito punteiro sinalará á raíz da árbore. Asemade, cada nodo da árbore ─incluída a raíz─ sinalará a unha certa cantidade de nodos subordinados a el.

Os nodos finais, os que xa non teñen ningún nodo subordinado a eles, teñen a mesma estrutura que o resto dos nodos ─datos e punteiros aos nodos directamente subordinados─, coa diferencia de que os punteiros aos subordinados están baleiros ─non apuntan a ningures─.

Hai outros conceptos cos que cómpre familiarizarse antes de empezar a traballar con árbores:

O número de pólas dun nodo denomínase “grao do nodo”.
O “nivel dun nodo” nunha árbore equivale á distancia entre dito nodo e a raíz da árbore ─que ten nivel 0─.
O nivel do nodo de maior nivel dunha árbore é a “altura da árbore”.

Organización dunha árbore

Visto en que consiste unha árbore, cómpre agora entender de que maneira están ordenados os distintos nodos dunha árbore. Para iso utilizaremos como exemplo o caso dunha árbore binaria ─que máis adiante se estudarán en profundidade─, que simplemente é unha árbore cuxos nodos sinalan a dous nodos subordinados.

Chamando a estes dous nodos subordinados de cada nodo «esquerdo» e «dereito», e tomando como referencia un dato ou conxunto de datos concreto dos nodos ─por exemplo unha variable chamada “dato”─, cumprirase sempre que o dato do nodo subordinado esquerdo dun nodo será sempre inferior ao dato do nodo, e o dato do nodo subordinado dereito dun nodo será sempre superior ao dato do nodo.

Por exemplo, imaxínese unha árbore que contén os datos: 1, 3, 5, 7, 8, 9, 10, 12, 13, 14, 15, 20, 25 e 35. Seguindo o enunciado no parágrafo anterior, a árbore quedaría coa forma seguinte:

            10    
       /           \
      7            15  
   /    \       /      \
  3      9     13      25
 / \    /     /  \    /  \
1   5  8     12  14  20  35

Eficiencia das árbores

Unha vez familiarizados coa forma en que se organizan os nodos dunha árbore, pódese comprender a eficiencia en certos casos ─especialmente á hora de buscar datos─ do uso de árbores ante, por exemplo, o uso de listas encadeadas. Visualícese a árbore binaria do exemplo anterior.

Durante unha busca de datos, a árbore binaria resultaría moito máis eficiente que a lista para esta busca. Cada comprobación na árbore permitirá descartar directamente a metade dos datos, de aí a súa eficiencia. Porén, na lista, se se buscase un dos últimos datos serían necesarias moitas comprobacións. Vexamos algúns números para o exemplo dado:

Dato a buscar	Comprobacións (lista)	Comprobacións (árbore)
1	1	4
9	6	3
10	7	1
13	9	3
35	14	4

Percorrido dunha árbore

Percorrer unha árbore consiste en visitar todos e cada un dos nodos que contén, de xeito que cada nodo se visite unha única vez. Este percorrido é posible mediante o uso de funcións recursivas.

As funcións para percorrer árbores variarán dependendo do grao da árbore, dos datos utilizados para organizar a árbore, así como da tarefa que se vaia realizar durante o percorrido ─gravar os datos en disco, borrar os nodos da árbore, etc.─.

Equilibrio

Unha árbore está equilibrada se para cada nodo o número de nodos que “colgan” de cada un dos seus nodos directamente subordinados non difiren os uns dos outros en máis dunha unidade.

O problema é que a medida que se utilizan, as árbores desequilíbranse ─algunhas das pólas quedan máis longas que outras─, polo que será necesario utilizar unha función para equilibralas.

Por exemplo, visualícese a árbore binaria que se utilizou previamente. Imaxínese como quedaría dita árbore en caso de inserir nela outro nodo co valor 16. A árbore quedaría entón así:

            10    
       /           \
      7            15  
   /    \       /      \
  3      9     13      25
 / \    /     /  \    /  \
1   5  8     12  14  20  35
                    /
                   16

E en caso de meterlle a continuación outro nodo de valor 17, e a continuación outro de valor 18, e logo un de valor 19, a árbore quedaría completamente desequilibrada:

            10    
       /           \
      7            15  
   /    \       /      \
  3      9     13      25
 / \    /     /  \    /  \
1   5  8     12  14  20  35
                    /
                   16
                     \
                     17
                       \
                       18
                         \
                         19

É por esta razón que ás veces, tras o seu uso continuado, adoita facerse necesario equilibrar as árbores.

Árbores binarias

Ás arbores binarias conteñen en cada nodo, ademais dos datos do elemento, dous punteiros, un a cada un dos seus nodos directamente subordinados. Podemos ver isto como se os subordinados estivesen cada un a un lado ─esquerdo e dereito─, pois esta forma de visualizar as árbores binarias facilita a comprensión do funcionamento das funcións que traballan con elas.

Declarar unha árbore binaria

Para declarar unha árbore binaria é necesario, primeiro, definir a estrutura dos seus nodos, e segundo, declarar un punteiro a unha estrutura dese tipo. O valor inicial de dito punteiro debería ser nulo, de xeito que se poida saber durante a execución do programa se nun momento dado a árbore está baleira ou non.

O seguinte código define a estrutura dun nodo sinxelo que contén, ademais dos punteiros aos seus nodos subordinados, un único dato de tipo signed int:

typedef struct estruturasimpledunnodo
{
  signed int dato;
  struct estruturasimpledunnodo * nodoesquerdo;
  struct estruturasimpledunnodo * nododereito;
}
estruturanodo;

Partindo desta estrutura, a declaración dunha árbore deste tipo realizaríase así:

estruturanodo * arbore;

Os seguintes exemplos de funcións para o traballo con árbores binarias utilizarán como base a estrutura aquí declarada.

Crear un nodo binario

Crear un nodo consiste en facer espazo en memoria para un novo nodo que vai ser inserido nunha árbore.

estruturanodo * NovoNodo(void)
{
  // Declárase un punteiro ao novo nodo, con valor inicial nulo.
  estruturanodo * novo = NULL;

  // Resérvase espazo en memoria dinámica para dito nodo.
  novo = (estruturanodo *) malloc(sizeof(estruturanodo);

  // Devólvese o enderezo de memoria en que está situado o novo nodo.
  return novo; // A función devolverá valor nulo se non puido reservar o novo nodo.
}

Inserir un nodo nunha árbore binaria

Inserir un nodo consiste en facer espazo para un novo nodo na árbore, encher o novo nodo cuns certos datos, e situar o nodo no lugar correcto da árbore en función dun deses datos ─ou conxunto de datos─, de xeito que a árbore quede organizada.

Nótese que os novos nodos sempre se colocan ao final das árbores, é dicir, colgando dun nodo pero sen que deles colgue nodo ningún.

signed short int InserirUnNodo(estruturanodo ** punteirosuperior, signed int dato)
{
  // Recíbese o enderezo do nodo superior ou do punteiro á árbore se estaba baleira:
  estruturanodo * arbore = *punteirosuperior; 
  estruturanodo * novo = NULL; 		      // Punteiro ao novo nodo que se vai inserir.
  signed short int control = 0; 	      // Valor para controlar o correcto funcionamento da función.

  if(arbore == NULL) // Se se chegou ao lugar do que vai colgar o novo nodo...
  {
    novo = NovoNodo(); // ...solicítase que se reserve un espazo en memoria para o nodo.
    if(novo == NULL)
      return -1; // Se ocorre un erro a función devolve -1;
    else
    { 
      // De se reservar o espazo en memoria correctamente,
      // énchese o novo nodo coa información recibida pola función:
      novo->dato = dato;

      // e dáselles valor nulo aos punteiros aos seus nodos subordinados
      // dado que os novos nodos nunca teñen subordinados.
      novo->esquerda = NULL;
      novo->dereita = NULL;

      // O nodo superior ten que apuntar ao novo nodo.
      // En caso de que sexa o primeiro nodo da árbore e non haxa nodo superior,
      // quen apuntará ao novo nodo será o punteiro á árbore.
      *punteirosuperior = novo;
    }
  }
  else // Se aínda non se chegou ao lugar do que vai colgar o novo nodo, séguese buscando.
  {
    if(arbore->dato < dato)
      control = InserirUnNodo(&arbore->dereita,dato); // Ben pola dereita,
    else
      control = InserirUnNodo(&arbore->esquerda,dato); // ben pola esquerda.
  }

  // Se houbese algún erro durante o proceso de inserción do novo nodo,
  // a función devolverá -1. Se todo marchou correctamente, devolverá 0.
  return control;
}

Percorrer unha árbore binaria

Para percorrer todos os nodos das árbores existen tres formas posibles:

Preorde. Para cada nodo visítase primeiro a raíz, logo a árbore esquerda e logo a dereita. “RED”.

Para o exemplo inicial a orde quedaría: 10, 7, 3, 1, 5, 9, 8, 15, 13, 12, 14, 25, 20, 35.

Inorde. Para cada nodo visítase primeiro a árbore subordinada esquerda, lodo a raíz e logo a árbore subordinada dereita. “ERD”.

Nótese que o método inorde obtén os datos ordenados en función do valor que se utilizou para ordenar a árbore. Para que esta orde vaia á inversa, abondaría con facer un inorde inverso, é dicir, “DRE” en vez de “ERD”.

Para o exemplo inicial, a orde quedaría: 1, 3, 5, 7, 8, 9, 10, 12, 13, 14, 15, 20, 25, 35.

Postorde. Para cada nodo visítase primeiro a árbore subordinada dereita, logo a esquerda, e logo a raíz. “DER”.

O percorrido postorde é o método que se utilizará á hora de borrar a árbore ─liberar o espazo que ocupa en memoria─.

Para o exemplo inicial, a orde quedaría: 35, 20, 25, 12, 14, 13, 15, 1, 5, 3, 8, 9, 7, 10.

Asemade podería considerarse unha cuarta forma de percorrer arbores binarias: inorde inversa. É o sentido inverso da forma inorde (“DRE”), e permite percorrer os valores da árbore ordenados de forma inversa, é dicir, en lugar de facelo dende o menor ao maior, farase dende o maior ao menor.

Trátase de definicións recursivas, é dicir, a orde aplícase ao nodo raíz da árbore, pero tamén a todos os outros nodos (na orde estipulada pola propia definición).

Percorrido inorde dunha árbore binaria

A continuación preséntase un exemplo básico de percorrido da árbore polo método inorde. Neste caso simplemente se imprimen os seus valores.

// Esquerda, raíz, dereita. ERD.
void Inorde(estruturanodo * arbore)
{
  if(arbore != NULL)
  {
    Inorde(arbore->esquerda);
    printf("%d\t",arbore->dato);
    Inorde(arbore->dereita);
  }
}

Borrar unha árbore binaria

Unha forma de borrar unha árbore completa podería ser recorréndoa en postorde:

void BorrarAArbore(estruturanodo * arbore);
{
  if(arbore != NULL)
  {
    BorrarAArbore(arbore->esquerda);
    BorrarAArbore(arbore->dereita);
    free(arbore);
  }
}

Equilibrar unha árbore binaria

Para crear unha árbore binaria perfectamente equilibrada realízase o seguinte proceso recursivo:

Para un número “total” dado de nodos, sendo “nodosdaesquerda” o número de nodos á esquerda e “nodosdadereita” o número de nodos á dereita, calcúlase:

nodosdaesquerda = total / 2

nodosdadereita = total - nodosdaesquerda - 1

E a continuación, para cada nodo:

Xérase unha árbore subordinada esquerda cunha cantidade nodosdaesquerda de nodos.
Utilízase o propio nodo.
Xérase unha árbore subordinada dereita cunha cantidade nodosdadereita de nodos.
Devólvese o enderezo do nodo.

Crear unha árbore binaria equilibrada

Partindo dunha lista ordenada de datos pódese crear unha árbore equilibrada mediante unha función. esta función recibirá o número de elementos ou nodos a inserir na árbore. A función devolverá un punteiro á raíz da árbore construída. Vexamos un exemplo deste tipo de función:

estruturanodo * CrearUnhaArboreEquilibrada(signed int total)
{
  signed int nodosdaesquerda, nodosdadereita; // Variables previamente enunciadas.
  estruturanodo * novo = NULL; // Variable para almacenar os novos nodos.

  if(total == 0) // Se non hai ningún valor a introducir na árbore.
    return NULL;  // Devólvese o valor nulo.

  nodosdaesquerda = total / 2; // Calcúlanse os nodos da árbore subordinada esquerda,
  nodosdadereita = total - nodosdaesquerda - 1; // e os da árbore subordinada dereita.

  // Resérvase espazo en memoria dinámica para o novo nodo.
  // Esta función xa se enunciou previamente máis arriba.
  novo = NovoNodo();

  // Créase ─de maneira equilibrada─ a árbore subordinada esquerda:
  novo->nodoesquerdo = CrearUnhaArboreEquilibrada(nodosdaesquerda);

  // Énchese de información este nodo.
  // Neste exemplo non se meterá ningunha información, pero podería
  // lerse a información dun ficheiro de xeito que se fose avanzando
  // no ficheiro. O mesmo se aplica a unha pila ou unha cola.

  // Créase ─de maneira equilibrada─ a árbore subordinada dereita:
  novo->nododereito = CrearUnhaArboreEquilibrada(nodosdadereita);

  // Devólvese o punteiro ao novo nodo.
  return novo;
}

Notas

↑ O factorial dun número é a multiplicación de todos os números enteiros entre 1 e o propio número. Por exemplo, o factorial de 3 sería (1×2×3=) 6, o de 6 sería (1×2×3×4×5×6=) 720.

Véxase tamén

Exercicios

Exercicios de traballo con árbores

C
← Volver a Traballar con listas encadeadas	Traballar con árbores	Seguir con Comentarios →

[1] O factorial dun número é a multiplicación de todos os números enteiros entre 1 e o propio número. Por exemplo, o factorial de 3 sería (1×2×3=) 6, o de 6 sería (1×2×3×4×5×6=) 720.

[1]