Please enable JavaScript.
Coggle requires JavaScript to display documents.
ÁRVORES - Coggle Diagram
ÁRVORES
Uma árvore é um grafo acíclico conectado
Uma
floresta
é um grafo que não possui ciclos, mas também não está necessariamente ligado
O
número de pontas
em uma árvore é
sempre 1 a menos
que o
número de vértices
\(|E|=|V|-1\)
Para cada par de vértices
em uma árvore,
sempre
existe
apenas 1 caminho de um vértice ao outro
É possível escolher arbitrariamente um vértice e considerá-lo como a
raiz
da árvore
Árvores enraizadas
A
raiz
é o
nível 0
da árvore, os
vértices diretamente ligados à raiz
são o
nível 1
, os
vértices ligados a esses
são o
nível 2
e assim continua
Dois exemplos de usos computacionais são a implementação de dicionários e a análise de algoritmos recursivos
Todos os vértices em um caminho simples da raíz da árvore até um vértice \(v\) são ditos
ancestrais de \(v\)
Vértice pai
\(u\) de \(v\) é o vértice ancestral imediatamente antes de \(v\)
\(v\) é
filho
de \(u\)
Um
vértice sem filhos
é chamado de
folha
Vértices com o mesmo pai são
irmãos
Todos os vértices
dos quais \(u\) é ancestral são chamados de
descendentes
de \(u\)
A
profundidade
de um vértice é o comprimento do caminho entre a raíz e esse vértice
A
altura
de uma árvore é comprimento do maior caminho simples entre a raíz e uma folha
Árvores ordenadas
Uma árvore enraizada na qual todas as crianças de cada vértice estão ordenadas
É considerado que as crianças estão ordenadas da esquerda para a direita
Uma
árvore binária
é uma árvore ordenada na qual cada vértice tem, no máximo, 2 filhos
Pode ser definida recursivamente
Árvores binárias de busca
O número do vértice pai é maior que todos os números de sua
sub-árvore esquerda
e menor que todos os números de sua
sub-árvore direita
A
eficiência
de vários algoritmos das árvores binárias de busca depende da altura da árvore
Altura \(h\) de uma árvore binária com \(n\) vértices (nós)
\(\lfloor\log_2n\rfloor\le h \le n-1\)
É
implementada computacionalmente
como uma coleção de nós, que correspondem aos vértices da árvore
Cada nó possui a informação do vértice e dois ponteiros (um para o filho da esquerda e outro para o da direita)
Operação de busca
É feita de forma recursiva utilizando a ordenação da árvore binária
Busca por um elemento \(v\)
4 more items...
Operação de inserção
Quase idêntica à operação de busca
1 more item...
Travesia e outras propriedades
Dividir e conquistar
aplicada às árvores binárias
A própria definição desse tipo de árvore à divide em duas estruturas iguais, porém menores
Ex: Algoritmo recursivo para computar a altura de uma árvore binária
3 more items...
3 algoritmos para caminhas pela árvore
3 more items...