Java

Introdução: A base deste trabalho é a implementação das Arvores Binárias. Para uma melhor comparação de desempenho entre outras arvores binárias.
Definição:
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.

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 inteiro) e os endereços (das raízes) de duas subárvores: uma esquerda e uma direita.As árvores B são árvores balanceadas projetadas para trabalhar com dispositivos de armazenamento secundário como discos magnéticos. Elas visam otimizar as operações de entrada e saída nos dispositivos. O tempo de acesso às informações em um disco é prejudicado principalmente pelo tempo de posicionamento do braço de leitura. Uma vez que o braço esteja posicionado no local correto, a leitura pode ser feita de forma bastante rápida. Desta forma, devemos minimizar o número de acessos ao disco. Diferente das árvores binárias, cada nó em uma árvore B pode ter muitos filhos, isto é, o grau de um nó pode ser muito grande.
Algoritmo da inserção em Java: public void Inserir(No novo, No anterior){ if (anterior != null){ if (novo.ObtemValor() < anterior.ObtemValor()) //Como o novo nó tem valor menor do que o do nó anterior, desce para a esquerda do nó anterior. inicio.filho_Esq=this.Insere(novo, anterior.filho_Esq); else