Please enable JavaScript.
Coggle requires JavaScript to display documents.
Árvores - Coggle Diagram
Árvores
Grafo acíclico
Um grafo sem cíclos - mas não necessariamente conectado - é uma floresta. Todos seus componentes são árvores.
Árvore binária
Cada node possui um elemento. Um set de elementos ordenáveis.
Arranjados de forma que todos elementos na subárvore esquerda são menores e todos elementos na subárvore direita são maiores que o elemento na raiz da subárvore.
Árvore de busca binária
SEARCH
Recursivo
Ao procurar "v" na árvore, verifica-se se a árvore está vazia, caso positivo retorna falha
Se não estiver vazia, compara "v" com elemento na raiz. Se forem iguais, valor encontrado
Caso contrário, se v < K(r) procura-se na subárvore esquerda. Se v > K(r) procura-se na subárvore direita.
Cada iteração do algorítmo o problema é reduzido a procurar por "v" em uma árvore cada vez menor.
Eficiência
WORST CASE: Θ(n)
AVERAGE CASE: Θ(log n)
A definição de árvore binária divide ela em duas subárvores esquerda e direita a partir de sua raiz (quando ela não está vazia ou tem apenas a própria raiz).
Problemas com árvores binárias são resolvidos utilizando "dividir para conquistar"
HEIGHT
Def: Maior caminho da raiz até uma folha
+1 para computar a raiz
Senão, retorna max(HEIGHT(TL), HEIGHT(TR)) +1
Se a árvore for vazia, retorna -1
Comparações: C(n) = 2n + 1
Adições: A(n) = n
Dessa forma, HEIGHT faz 1 adição de 1 para cada node interno
DESLOCAMENTO
Existem 3 algorítmos clássicos de deslocamento em uma árvore binária
INORDER TRAVERSAL
Left -> Root -> Right
POSTORDER TRAVERSAL
Left -> Right -> Root
PREORDER TRAVERSAL
Root -> Left -> Right
|E| = |V| - 1