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: 53.441 ]
Por: Enzo de Brito Ferber em 07/05/2015 | Blog: http://www.maximasonorizacao.com.br
Pesquisa
De todas as operações que podem ser feitas em uma árvore, a pesquisa é a mais simples. O código abaixo:
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!
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áginas do artigo
1. Introdução2. 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 - Funções Variádicas
Linguagem C - Listas Duplamente Encadeadas
Leitura recomendada
Guia de Programação em C/GTK 2 - Construindo uma Calculadora Completa
Linguagem C - Listas Duplamente Encadeadas
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.
Parabéns pelo trabalho, dissertação completa sobre o assunto.
[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.
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
[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,
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
[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!
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
[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
[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
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
Patrocínio
Site hospedado pelo provedor RedeHost.
Destaques
Artigos
Como atualizar sua versão estável do Debian
Cirurgia para acelerar o openSUSE em HD externo via USB
Void Server como Domain Control
Dicas
Quer auto-organizar janelas (tiling) no seu Linux? Veja como no Plasma 6 e no Gnome
Copiando caminho atual do terminal direto para o clipboard do teclado
Script de montagem de chroot automatica
Tópicos
archlinux resolução abaixou após atualização (14)
Conselho distribuiçao brasileira (2)
Não consigo instalar distro antiga no virtualbox nem direto no hd (33)
Top 10 do mês
-
Xerxes
1° lugar - 146.120 pts -
Fábio Berbert de Paula
2° lugar - 63.903 pts -
Buckminster
3° lugar - 22.056 pts -
Alberto Federman Neto.
4° lugar - 20.030 pts -
Mauricio Ferrari
5° lugar - 19.446 pts -
edps
6° lugar - 17.731 pts -
Daniel Lara Souza
7° lugar - 17.117 pts -
Andre (pinduvoz)
8° lugar - 15.796 pts -
Alessandro de Oliveira Faria (A.K.A. CABELO)
9° lugar - 15.407 pts -
Jesuilton Montalvão
10° lugar - 14.722 pts
Scripts
A maior comunidade GNU/Linux da América Latina! Artigos, dicas, tutoriais, fórum, scripts e muito mais. Ideal para quem busca auto-ajuda.
Site hospedado por:
