C/Traballar con árbores
| C | ||
| ← Volver a Traballar con listas encadeadas | Traballar con árbores | Seguir con Comentarios → |
Introdución á programación recursiva
editarAntes 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
editarUnha á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
editarVisto 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
editarUnha 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
editarPercorrer 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
editarUnha á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
editarÁ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
editarPara 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
editarCrear 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
editarInserir 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
editarPara 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
editarA 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
editarUnha 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
editarPara 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 / 2nodosdadereita = total - nodosdaesquerda - 1
- E a continuación, para cada nodo:
- Xérase unha árbore subordinada esquerda cunha cantidade
nodosdaesquerdade nodos. - Utilízase o propio nodo.
- Xérase unha árbore subordinada dereita cunha cantidade
nodosdadereitade nodos. - Devólvese o enderezo do nodo.
- Xérase unha árbore subordinada esquerda cunha cantidade
Crear unha árbore binaria equilibrada
editarPartindo 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
editar- ↑ 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
editarExercicios
editar
| C | ||
| ← Volver a Traballar con listas encadeadas | Traballar con árbores | Seguir con Comentarios → |