Arvores B

Monitoria de Algoritmos
Árvore binária
Aula prática 1

Pra que árvores binárias?
Uma lista dinâmica, apesar de seus benefícios de memória “ilimitada” tem um problema:
Acesso Sequencial (ou Linear) [O(n)].
Para contornar esse problema foram criadas as árvores

O que são árvores binárias?
As árvores binárias são estruturas de dados encadeadas (assim como uma lista) onde cada elemento subdivide a árvore.
Termos:
Nó: Elemento que contém a informação a ser guardada e os ponteiros.
Raiz: Primeiro elemento da árvore. [Ex:
A]

Pai: Nó que tem um Filho. [Ex: B é pai de
D]
Filho: Nó posterior à algum outro nó.
[Ex. D é filho de B]
Folhas: Nós sem filhos. [G, H e I]

Obs: Posto (ou altura) = Altura relativa entre o pai e nó estudado.
[Ex. E tem altura 2]

O que são árvores binárias?
“Mas é só isso? Não!!”
As árvores apresentam uma propriedade específica:
1) O filho à esquerda de qualquer nó X, tem valor maior que X.
2) O filho à direita de qualquer nó X, tem valor menor que X
OBS: Válido para caracteres (consultar tabela ASCII)

E como manipulá-las?
A palavra-chave é: Recursão.
“E porque recursão?”

A recursão usa um método que será estudado mais a frente no curso, chamado dividir para conquistar, basicamente dividindo o problema em subproblemas menores.
OBS: Há como fazer de modo iterativo.

Falando em complexidade
Veremos a partir de agora alguns algoritmos usados em árvores binárias.
Inserção
Remoção
Encaminhamento
In – Ordem
Pré – Ordem
Pós – Ordem
Complexidade: O(log n) ou O(h)*
Obs: O(h) caso a árvore esteja degenerada (Veremos à frente)

Inserção
A inserção é feita somente nas folhas.
O algoritmo deve chegar a folha onde deve ser adicionada (lembrando de respeitar a propriedade da árvore binária).
Elementos que já pertencem a árvore, não devem ser adicionados novamente.

Encaminhamento
In – Ordem:
Nó Esquerdo → Raiz → Nó
Direito
Pré – Ordem:
Raiz → Nó Esquerdo → Nó
Direito
Pós – Ordem: