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

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


Remoção



Agora sim. O melhor para o final. A função para remover um nó da árvore é um pouco mais complexa que as outras, mas nada assustador. Primeiro, delineamos a função:

1. Procurar pelo elemento;
2. Se achado, *excluir* o elemento.

E como excluir? Quais os possíveis casos?

1. Excluir um nó com ambas as raízes presentes.
2. Excluir um nó com apenas uma subárvore (esquerda ou direita):
    2.1. Subárvore direita inexistente.
    2.2. subárvore esquerda inexistente.
3. Excluir um nó onde ambas as subárvores são NULAS.
Linux: Linguagem C - Árvores Binárias
Dê uma olhada no código completo da função e tente imaginar o que ela faz. E o mais importante, como atinge os princípios enumerados acima. Logo abaixo, duas ilustrações sobre 3 casos (1, 2.1 e 2.2).

/* @ Folha deletar (Folha raiz, int info)
 *
 * Argumentos
 * ----------
 *	raiz	raiz principal da arvore
 *	info	informação procurada para deletar
 *
 *  Retorno
 *  -------
 *	raiz	em ambos os casos (erro e sucesso)
 */
Folha deletar (Folha raiz, int info) {
	Folha filho, n_raiz;

	if (!raiz) return NULL;

	if (raiz->info == info) {
		if (raiz->direita) {
			n_raiz = filho = raiz->direita;

			while(filho->esquerda)
				filho = filho->esquerda;

			filho->esquerda = raiz->esquerda;

			free (raiz);
			return n_raiz;

		} else {
			n_raiz = raiz->esquerda;
			free (raiz);
			return n_raiz;
		}

	} else if (info > raiz->info)
		raiz->direita = deletar(raiz->direita, info);
	else
		raiz->esquerda = deletar(raiz->esquerda, info);

	return raiz;
}

Linux: Linguagem C - Árvores Binárias   Linux: Linguagem C - Árvores Binárias
Dissecando a função:

Folha deletar (Folha raiz, int info)

A declaração e o princípio de funcionamento da função "deletar" são exatamente iguais aos da função "inserir". "raiz" é um ponteiro para a raiz principal da árvore sendo analisada e "info" é a informação que queremos remover.

	Folha filho, n_raiz;

	if (!raiz) return NULL;

Esta é a primeira função que declara variáveis: dois ponteiros do tipo (struct folha *). "filho" e "n_raiz" serão usados como suporte nos testes condicionais mais a frente. "if (!raiz)" é o teste condicional de parada de recursão (ou de informe de erro, já que se a recursão chegar a esse ponto significa que o item a ser removido não foi encontrado).

	if (raiz->info == info) {

		// (tratamento dos casos de remoção)

	} else if (info > raiz->info)
		raiz->direita = deletar(raiz->direita, info);
	else
		raiz->esquerda = deletar(raiz->esquerda, info);

	return raiz;

Vamos de "trás para frente". Analisaremos o loop mais externo primeiro, para depois entrar em detalhes sobre os algoritmos de remoção. Esse loop é bem simples de ser entendido. O primeiro teste verifica se a informação na raiz atual é igual a informação a ser removida.

Caso não seja, o próximo teste condicional verificará se a informação a ser removida é MAIOR QUE a informação da raiz, em caso afirmativo, é realizada uma chamada recursiva na subárvore direita. (Lembre-se que para percorrermos a árvore precisamos sempre utilizar o mesmo algoritmo que utilizamos para inserir um novo elemento). Caso contrário, realizamos uma chamada recursiva na subárvore esquerda.

No final, retornamos à raiz.

Nota: o princípio de funcionamento é exatamente igual ao da função de inserção. Caso tenha dúvidas sobre como o processo recursivo vai funcionar, dê uma olhada na página "Inserção" deste artigo, que contém uma explicação maior e uma ilustração do processo.

Agora, o algoritmo de remoção:

if (raiz->direita) {
	n_raiz = filho = raiz->direita;

	while(filho->esquerda)
		filho = filho->esquerda;

	filho->esquerda = raiz->esquerda;

	free (raiz);
	return n_raiz;

} else {
	n_raiz = raiz->esquerda;
	free (raiz);
	return n_raiz;
}

Começamos com um teste condicional para verificar a existência da subárvore direita (itens maiores que a raiz). Caso ela exista, salvamos esse ponteiro nas variáveis "n_raiz" e "filho". "n_raiz" representa nossa nova raiz (como precisamos remover a raiz atual, uma nova raiz deverá tomar seu lugar). "filho" será usado para achar o menor elemento MAIOR QUE a raiz - esse conceito é muito importante e é realizado pelo próximo loop:

while(filho->esquerda)
	filho = filho->esquerda;

Enquanto houver uma raiz esquerda (itens menores) em "filho", avançaremos para ela ("filho = filho->esquerda" - lembra-se de como percorremos listas encadeadas?). Isso serve para encontrar o menor elemento maior que "raiz->info".

filho->esquerda = raiz->esquerda;

Aqui, anexamos as subárvores e resolvemos duas coisas. Primeiro, se a subárvore esquerda da raiz for NULL, ela vai continuar como NULL (caso 2, quando uma das subárvores é NULL). Segundo, se a subárvore esquerda existir (caso 1, ambas as subárvores presentes), vamos anexá-la à subárvore esquerda do menor elemento maior que a raiz, e isso garante a integridade da árvore.

free (raiz);
return n_raiz;

Liberamos a memória utilizada por "raiz", efetivando sua remoção da árvore e retornamos o ponteiro "n_raiz" (que foi salvo como apontando para "raiz->direta", ou o primeiro elemento maior que "raiz"). Esse elemento "n_raiz" passará a ser a nova raiz.

else {
	n_raiz = raiz->esquerda;
	free (raiz);
	return n_raiz;
}

Esse teste condicional é derivado do teste de existência de uma subárvore direita. Isso significa que este "else" vai tratar do caso 2 (subárvore direita inexistente) ou caso 3 (onde ambas as subárvores não estão presentes). "n_raiz = raiz->>esquerda" garante que se houver alguma informação na árvore, ela será retornada como nova raiz, e também garante que se não houver uma subárvore esquerda (caso 3, pois já sabemos que não há uma subárvore direita) NULL será retornado - ela garante que NULL será retornado graças ao algoritmo de inserção, que configura ambos os ponteiros de todos os novos elementos como NULL.

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

Linguagem C - Listas Duplamente Encadeadas

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

Algoritmo... como fazer?

Otimização de algoritmos

Dicas para aprender programação

  
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