Árvores Binárias

FLÁVIO CÔRTES TEIXEIRA

SEMINÁRIO DE ESTRUTURA DE DADOS DE DADOS

BRASÍLIA
2014
Sumário

Apresentação

Esta pesquisa apresenta conceito e exemplos sobre árvore binária e árvore binária de busca.

Introdução

Uma das dificuldades em armazenar e gerenciar dados em arquivo é pela forma que serão acessados os registros posteriormente. A busca é feita sequencialmente, o que acarreta um desempenho extremamente baixo, em se tratando de milhares de registros em um arquivo. Outra dificuldade encontrada é quanto à forma de excluir um registro fisicamente, pois não existe um meio de excluir bytes de um arquivo. O máximo que pode ser feito, é construir uma estrutura que possa gerenciar se o registro está em uso, em caso negativo, o registro será considerado excluso do arquivo do ponto de vista do sistema, mas continua ocupando espaço na unidade de massa, diminuindo desempenho do sistema que está utilizando o arquivo.
Embora possa haver muitos tipos diferentes de árvores, árvores binárias são especiais porque, quando ordenadas, permitem pesquisas, inserções e exclusões rápidas. Cada item em uma árvore consiste em informação juntamente com um elo ao membro esquerdo e um elo ao membro direito.

Definição

Uma árvore binária é uma estrutura de dados caracterizada por: Ou não tem elemento algum (vazia). Ou tem um elemento distinto, denominado raiz, com dois ponteiros para duas estruturas diferentes, denominadas subárvore esquerda e subárvore direita.

Termo de uma árvore binária

Raiz de uma árvore: primeiro elemento da árvore;
Nó filho / nó pai: o filho é apontado pelo seu pai, então um nó que tem outro nó em seu link direito/esquerdo é pai do nó que está no seu link direito/esquerdo e esse nó por sua vez é filho do dono do link que está apontando para ele;
Folha de uma árvore: um nó folha é um nó sem filhos (seus links são nulos);
Nó interno de uma árvore: é um nó que tem pelo menos um filho;
Nível de um