Arvore binária

Faculdade de Estudos Avançados do Pará

Curso: Sistemas de Informação

Turma: 4SIN1

Estruturas de Dados II

Jorge Miranda

Milton Costa

Árvores Binárias

Belém – Pará

Introdução

Uma das dificuldades em armazenar e gerenciar dados em arquivo é a forma de acesso aos registros. A busca é feita seqüencialmente, o que acarreta a uma performance extremamente baixa, 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 a performance do sistema que está utilizando o arquivo. O propósito deste trabalho é mostrar uma biblioteca que permita manipular registros contendo dados genéricos, utilizando uma árvore binária balanceada o que trará uma otimização no sistema de busca.

1-Definição e exemplos iniciais

Uma árvore binária (chamada de binária pois de cada nó podem nascer até 2 novos nós) é uma estrutura de dados caracterizada por:
- Ou não tem elemento algum (árvore vazia).
- Ou tem um elemento distinto, denominado raiz, com dois ponteiros para duas estruturas diferentes, denominadas sub-árvore esquerda e sub-árvore direita.

[pic]

Perceba que a definição é recursiva e, devido a isso, muitas operações sobre árvores binárias utilizam recursão. É o tipo de árvore mais utilizado na computação. A principal utilização de árvores binárias são as árvores de busca binária.

Uma definição mais concreta
Uma árvore binária (= binary tree) é formada de nós; cada nó tem um certo conteúdo (por exemplo, um número