Linguagem C - Árvores Binárias

Neste artigo, falarei sobre o que é e como implementar uma estrutura de dados chamada Árvore Binária. Com tempos de pesquisa, inserção e remoção expressivamente melhores que de listas encadeadas, esta estrutura é usada principalmente em bancos de dados e sistemas de arquivos.

[ Hits: 50.231 ]

Por: Enzo de Brito Ferber em 07/05/2015 | Blog: http://www.maximasonorizacao.com.br


Recursividade



Recursão, pode ser definida em termos matemáticos ou de programação. Como este é um artigo de programação e as funções em C podem chamar a si mesmas, definiremos que uma função é recursiva se ela chama a si mesma em seu escopo. Recursão é o processo de definir algo em termo de si mesmo, e também é chamado de definição circular.

É necessário tomar um certo cuidado quando for construir funções recursivas, já que é muito fácil criar uma recursão sem fim, terminando o programa. Todo código recursivo deve conter uma condição para pausa e o programador deve garantir que toda vez que a função for chamada, essa condição será testada e, acima de tudo, deve reforçar um comportamento que faça o desenvolvimento da função caminhar em direção a essa condição.

Não adianta colocar uma condição como "se X == 0, termine", se a função incrementa X a cada chamada.
Linux: Linguagem C - Árvores Binárias
Abaixo, alguns códigos ilustrando funções recursivas.

1. Fatorial:

O fatorial de um número é dado pela multiplicação de todos os valores menores que o número e maiores que 1 (um).

fat(n) = fat(n) * fat(n - 1) * fat(n - 2) * ... * fat(1)

Fácil perceber que ela se define em termos de si mesma.

/* fat.c
 *
 * Linguagem C - Árvores Binárias
 * Viva O Linux
 *
 * Enzo Ferber
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

double fat (double n)
{
	if (n == 1) return 1;

	return n * fat(n - 1);

	// return (n == 1) ? 1 : n * fat(n - 1);
}

int main (int argc, char *argv[])
{
	register int i;

	for (i = 1; i < argc; i++)
		printf("%s: %.0lf
", argv[i], fat( atof(argv[i])));

	return 0;
}

Linux: Linguagem C - Árvores Binárias
2. Fibonacci:

Leonardo Bonacci (1170-1250), também conhecido como Fibonacci, foi um matemático italiano considerado o mais brilhante matemático da Era Medieval. Atribui-se a ele a "criação" da sequência Fibonacci, onde um dado número é definido pela soma dos dois números anteriores. As exceções são os números 0 (zero) e 1 (um), cujo valor na sequência é 1 (um).

Fonte: Fibonacci « wikipedia.org

É fácil perceber que a definição desta sequência é recursiva, uma vez que ela é definida em termo de si mesma.

fib(n) = fib(n - 1) + fib(n - 2)

/* fib.c
 *
 * Linguagem C - Árvores Binárias
 * Viva O Linux
 *
 * Enzo Ferber
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

double fib (double n)
{
	if (n == 0 || n == 1) return 1;

	return fib(n - 1) + fib(n - 2);
	// return (n == 0 || n == 1) ? 1 : fib(n - 1) + fib(n - 2);
}

int main (int argc, char *argv[])
{
	register int i;

	for (i = 1; i < argc; i++)
		printf("%s: %.0lf
", argv[i], fib(atof(argv[i])));

	return 0;
}

Linux: Linguagem C - Árvores Binárias
Através da imagem, podemos perceber como a complexidade aumenta absurdamente, à medida que 'n' aumenta. Também podemos perceber a quantidade imensa de chamadas às funções.

* Lembre-se: cada chamada à função, requer um quadro na pilha (registro de ativação, ou Stack Frame) e isso consome memória! Quando for desenvolver rotinas recursivas, pense em como ela vai se comportar na memória, isso é muito importante!

3. Busca Binária em Matrizes:

Matrizes normalmente são usadas para armazenar sequências congruentes de dados, e a melhor forma de armazenar esses dados é guardando-os de forma ordenada. O problema com matrizes, é que o tempo de inserção, remoção e busca é muito ruim - O(n). O algoritmo de busca binária consiste em dividir o número de elementos da matriz pela metade e analisar esse elemento mediano. Se o elemento procurado for menor que o elemento mediano, então, descartamos a metade superior da matriz, e realizamos a operação novamente na metade inferior.

O tempo gasto para esse algoritmo achar um dado elemento, é de "O(lg(n))" no pior caso, e "O(1)" no melhor caso. Uma melhora considerável na performance! Também é fácil perceber que a função de busca binária é um algoritmo que se define em termos de si mesmo, portanto, recursivo.

/* bbin.c
 *
 * Linguagem C - Árvores Binárias
 * Viva O Linux
 *
 * Enzo Ferber
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

int bbin (int *a, int min, int max, int info)
{
	int pos = (min + max) / 2;

	if (a[pos] == info) return pos;
	else if (min >= max) return -1;
	else if (info > a[pos]) return bbin(a, pos + 1, max, info);
	else return bbin(a, min, pos - 1, info);

	return -1;
}

int main (void)
{
	int a[10] = {1,2,3,4,5,6,7,8,9,10};

	printf("1: %d
", bbin(a, 0, 10, 1));
	printf("5: %d
", bbin(a, 0, 10, 5));
	printf("8: %d
", bbin(a, 0, 10, 8));
	printf("0: %d
", bbin(a, 0, 10, 0));
	printf("9: %d
", bbin(a, 0, 10, 9));

	return 0;
}

Linux: Linguagem C - Árvores Binárias
Muito interessante, mas será que realmente é eficiente? Vamos construir outro programa com a função de busca binária e gerar uma matriz de 50.000 elementos inteiros, organizados sequencialmente e então, pediremos ao usuário para digitar qualquer valor e contaremos quantos passos a função vai gastar para encontrar tal elemento.

Teoricamente, nunca poderão ocorrer mais de 16 operações, já que: 2^16 = 65.536

/* bbin2.c
 *
 * Linguagem C - Árvores Binárias
 * Viva O Linux
 *
 * Enzo Ferber : enzoferber@gmail.com
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define LIMIT		50000

int counter;

int bbin (int *a, int min, int max, int info)
{
	int pos = (min + max) / 2;

	counter++;

	if (a[pos] == info) return pos;
	else if (min >= max) return -1;
	else if (info > a[pos]) return bbin(a, pos + 1, max, info);
	else return bbin(a, min, pos - 1, info);

	return -1;
}

int main (void)
{
	int a[ LIMIT ];
	register int i;
	int n;

	for (i = 0; i < LIMIT; i++)
		a[i] = i + 1;

	printf("Digite -1 para sair

");
	while (1) {
		printf("Digite um número: ");
		scanf("%d", &n);

		if (n == -1) break;

		// contador
		counter = 0;

		printf("Posicao no vetor: %d
", bbin(a, 0, LIMIT, n));
		printf("Operacoes necessarias: %d

", counter);
	}

	return 0;
}

Excelente, funcionou! E o número de operações não passou de 16! Teste você mesmo com os números 150, 25000, 25001, 12499, 12500 e 6250. Em uma pesquisa linear, usaríamos 12500 comparação para achar o número 12500. Com esse algoritmo achamos em apenas 2!

Uma árvore com 1,6 x 10^60 elementos não precisa de mais que 200 operações de comparação para achar o elemento procurado, inseri-lo ou removê-lo! Genial! Agora já sabe como os bancos de dados como o MySQL funcionam (na verdade, a estrutura usada não é uma árvore binária simples como a que vamos implementar nesse artigo, é uma versão muito melhor e mais avançada).

O grande problema é que não podemos usar matrizes para armazenar grandes quantidades de informações em grandes aplicações ou em computadores onde a memória disponível não seja tão disponível assim (hoje em dia não temos muito problema com memória para pequenas e médias aplicações, mas é sempre bom pensar em termos de escalabilidade e estabilidade, quando for desenvolver qualquer tipo de programa).

Já imaginou implementar busca binárias em listas duplamente encadeadas? Essa é a idéia por trás das árvores binárias!

Página anterior     Próxima página

Páginas do artigo
   1. Introdução
   2. Recursividade
   3. Inserção
   4. Pesquisa
   5. Remoção
   6. Transversalização
   7. Conclusão
   8. Código Completo e Comentado
Outros artigos deste autor

Linguagem C - Listas Duplamente Encadeadas

Linguagem C - Funções Variádicas

Leitura recomendada

Dicas para aprender programação

Otimização de algoritmos

Guia de Programação em C/GTK 2 - Construindo uma Calculadora Completa

Algoritmo... como fazer?

Tutorial SDL

  
Comentários
[1] Comentário enviado por fabio em 07/05/2015 - 12:10h

Parabéns pelo trabalho, dissertação completa sobre o assunto.

[2] Comentário enviado por SamL em 09/05/2015 - 12:49h

Completissimo, muito bom, parabéns.

[3] Comentário enviado por EnzoFerber em 09/05/2015 - 13:34h


Muito obrigado, pessoal.

[4] Comentário enviado por pmargreff em 09/05/2015 - 21:09h


Primeiramente, parabéns pelo artigo.
Segundo, gostaria de saber que programa utilizou para fazer as imagens. Abraço.

[5] Comentário enviado por EnzoFerber em 11/05/2015 - 08:44h


[4] Comentário enviado por pablomrg em 09/05/2015 - 21:09h


Primeiramente, parabéns pelo artigo.
Segundo, gostaria de saber que programa utilizou para fazer as imagens. Abraço.


Bom dia.

Para as imagens usei o primo rico do GIMP! Filho da Adobe!

[]'s

[6] Comentário enviado por dianaluz92 em 12/05/2015 - 15:08h


Parabéns pelo trabalho, a parte conceitual está muito clara da para a estrutura da arvore, mas eu queria tirar um duvida se for possível, como inserir um conjunto de elementos na árvore no caso quando o campo info é um ponteiro que deverá receber elemento tipo inteiro,float e um ponteiro char para nome.
Desde já grata,

[7] Comentário enviado por EnzoFerber em 12/05/2015 - 16:19h


[6] Comentário enviado por dianaluz92 em 12/05/2015 - 15:08h


Parabéns pelo trabalho, a parte conceitual está muito clara da para a estrutura da arvore, mas eu queria tirar um duvida se for possível, como inserir um conjunto de elementos na árvore no caso quando o campo info é um ponteiro que deverá receber elemento tipo inteiro,float e um ponteiro char para nome.
Desde já grata,

Boa tarde.
Pelo que entendi, você quer usar árvores para armazenar uma estrutura sua, certo?

typedef struct data {
int i;
float f;
char *nome;
} data_t;

Coloque os ponteiros direita e esquerda na estrutura que está usando.

typedef struct data* data_t;
struct data {
int i;
float f;
char *nome;
data_t esquerda, direita;
};

Agora é só modificar as funções inserir(), deletar(), procurar(), imprimir(), etc.

if (!raiz) {
...
} else if (strcmp(raiz->nome, nome_ptr) > 0) raiz->direita = inserir(raiz->direita, nome_ptr);
else if (strcmp(raiz->nome, nome_ptr) < 0 ) raiz->equerda = inserir(raiz->esquerda, nome_ptr);
else {
// strcmp() == 0
// dado existente
printf("dado existente!");
return raiz;
}
return raiz;

Espero ter ajudado,
[]'s
Enzo Ferber

[8] Comentário enviado por Ragen em 13/05/2015 - 08:41h

Bom dia Enzo,

Parabéns pelo texto. Vejo que hoje muitos do meio acadêmico não tem nem de longe a sua didática - até porque para ser didático, um professor precisa ser profundo conhecedor do tema.

Eu fiz faculdade em 2003 na PUC-Goiás e me recordo das aulas de ICC2 onde fizemos este caso de B-tree. Logo depois a grade mudou, e o curso afundou em total decadência.

Hoje vejo que muitos alunos se formam bacharéis sem ao menos entender o conceito das árvores binárias. Sem entender o que é um ponteiro, endereço de memória - afinal as faculdades estão pondo Java no lugar do C. Moral da história? Os alunos se formam e não sabem programar - então terminam seus cursos e ficam desempregados e não entendem porque nenhum empresa os querem contratar.

Obrigado por compartilhar conosco este material e seu conhecimento!

[9] Comentário enviado por EnzoFerber em 13/05/2015 - 09:04h


[8] Comentário enviado por Ragen em 13/05/2015 - 08:41h

Bom dia Enzo,

Parabéns pelo texto. Vejo que hoje muitos do meio acadêmico não tem nem de longe a sua didática - até porque para ser didático, um professor precisa ser profundo conhecedor do tema.

Eu fiz faculdade em 2003 na PUC-Goiás e me recordo das aulas de ICC2 onde fizemos este caso de B-tree. Logo depois a grade mudou, e o curso afundou em total decadência.

Hoje vejo que muitos alunos se formam bacharéis sem ao menos entender o conceito das árvores binárias. Sem entender o que é um ponteiro, endereço de memória - afinal as faculdades estão pondo Java no lugar do C. Moral da história? Os alunos se formam e não sabem programar - então terminam seus cursos e ficam desempregados e não entendem porque nenhum empresa os querem contratar.

Obrigado por compartilhar conosco este material e seu conhecimento!


Bom dia, Ragen.
Em primeiro lugar, muito obrigado pelos elogios.

Segundo, concordo plenamente com você (Muita gente e eu, na verdade). Uma dessas pessoas é o CEO do StackExchange, que possui um blog muito bom. O nome dele é Joel Spolsky e o blog é o http://www.joelonsoftware.com. Ele escreveu um artigo precisamente sobre a troca de linguagens "mais baixas" pelo Java nas faculdades, e como isto está arruinando o mercado de trabalho e a qualidade dos profissionais. O artigo chama-se "The Perils of JavaSchool". Excelente texto, vale a pena ser lido. (O blog todo, na verdade)
http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html

Pessoalmente, acredito que todos deveriam ter um semestre em Assembly para entender como a CPU/Memória/HD funcionam e interagem - como tudo realmente acontece "embaixo do capô". Faz uma falta danada!

Sobre Joel: http://www.joelonsoftware.com/AboutMe.html
StackExchange: http://www.stackexchange.com

*

http://blog.codinghorror.com/why-cant-programmers-program/
Artigo muito bom também, falando sobre bacharéis que não conseguem programar programas *simples*! Leitura recomendada!


[]'s
Enzo Ferber

[10] Comentário enviado por Ragen em 13/05/2015 - 18:22h


[9] Comentário enviado por EnzoFerber em 13/05/2015 - 09:04h


[8] Comentário enviado por Ragen em 13/05/2015 - 08:41h

Bom dia Enzo,

Parabéns pelo texto. Vejo que hoje muitos do meio acadêmico não tem nem de longe a sua didática - até porque para ser didático, um professor precisa ser profundo conhecedor do tema.

Eu fiz faculdade em 2003 na PUC-Goiás e me recordo das aulas de ICC2 onde fizemos este caso de B-tree. Logo depois a grade mudou, e o curso afundou em total decadência.

Hoje vejo que muitos alunos se formam bacharéis sem ao menos entender o conceito das árvores binárias. Sem entender o que é um ponteiro, endereço de memória - afinal as faculdades estão pondo Java no lugar do C. Moral da história? Os alunos se formam e não sabem programar - então terminam seus cursos e ficam desempregados e não entendem porque nenhum empresa os querem contratar.

Obrigado por compartilhar conosco este material e seu conhecimento!

Bom dia, Ragen.
Em primeiro lugar, muito obrigado pelos elogios.

Segundo, concordo plenamente com você (Muita gente e eu, na verdade). Uma dessas pessoas é o CEO do StackExchange, que possui um blog muito bom. O nome dele é Joel Spolsky e o blog é o http://www.joelonsoftware.com. Ele escreveu um artigo precisamente sobre a troca de linguagens "mais baixas" pelo Java nas faculdades, e como isto está arruinando o mercado de trabalho e a qualidade dos profissionais. O artigo chama-se "The Perils of JavaSchool". Excelente texto, vale a pena ser lido. (O blog todo, na verdade)
http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html

Pessoalmente, acredito que todos deveriam ter um semestre em Assembly para entender como a CPU/Memória/HD funcionam e interagem - como tudo realmente acontece "embaixo do capô". Faz uma falta danada!

Sobre Joel: http://www.joelonsoftware.com/AboutMe.html
StackExchange: http://www.stackexchange.com

*

http://blog.codinghorror.com/why-cant-programmers-program/
Artigo muito bom também, falando sobre bacharéis que não conseguem programar programas *simples*! Leitura recomendada!


[]'s
Enzo Ferber


Opa Enzo,

Valeu pela dica. Eu já conhecia o StackExchange, mas não conhecia o blog do fundador - estou lendo os links que recomendou, realmente ótima leitura!

Se tiver Linkedin, me adiciona lá: https://www.linkedin.com/profile/view?id=80923831

[11] Comentário enviado por EnzoFerber em 18/07/2015 - 12:15h

Pessoal,

Na página 4 há um erro. Na função pesquisa esqueci de fazer justamente a comparação que identifica o elemento procurado.
Para utilizar a função corretamente, favor fazer a seguinte modificação:

Após a linha "if (!raiz) return NULL;"
Colocar:
else if (raiz->info == info) return raiz;

É isso.

[]'s


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts