Linguagem C - Árvores Binárias

EnzoFerber

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: 52.169 ]

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

25 0

Denuncie Favoritos Indicar Impressora

Pesquisa

De todas as operações que podem ser feitas em uma árvore, a pesquisa é a mais simples. O código abaixo:

Folha procurar (Folha raiz, int info)
{
	/* Parada de Recursão
	 *
	 * elemento não encontrado!
	 */
	if (!raiz) return NULL;

	if (info > raiz->info) return procurar(raiz->direita, info);
	else return procurar (raiz->esquerda, info);

	return NULL;
}

O código, além de muito simples, é auto-explicativo. Nosso teste de parada de recursão é o mesmo de sempre: if(!raiz). Vale ressaltar que para essa função, se a recursão chegar a um ponto onde o argumento raiz é NULL, significa que o elemento não existe na árvore.

O método de tomada de decisão para pesquisa segue o algoritmo de inserção. Como o algoritmo já foi explicado na seção anterior, não explicarei os detalhes aqui.

Essa é a função de pesquisa. E muito eficiente, por sinal!

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

Tutorial SDL

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

Otimização de algoritmos

Dicas para aprender programação

Análise dos Métodos de Ordenação usados em Algoritmos Computacionais

Comentários

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

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

3 0

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

Completissimo, muito bom, parabéns.

0 0

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

Muito obrigado, pessoal.

0 0

[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.

0 0

[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

1 0

[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,

0 0

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

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

0 0

[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!

0 0

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

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

1 0

[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

0 0

[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

0 0