Please enable JavaScript.
Coggle requires JavaScript to display documents.
IF672 (2020.1) - Levitin Aluno: Marcos André - Coggle Diagram
IF672 (2020.1) - Levitin Aluno: Marcos André
Árvores Cap. 1 (31–35)
Grafo acíclico conectado
Floresta
Junção de árvores, não necessariamente conectadas
E = V - 1
Árvores enraizadas
Exatamente um caminho de um dos vértices para o outro
Possível escolher uma raiz
Usos na computação
Descrever hierarquias
Implementar dicionários
Acesso para conjuntos com muita informação
Codificação de dados
Análise de algoritmos recursivos
Árvores state-space
Backtracking
Branch-and-bound
Componentes
Vértices ancestrais
Ancestrais próprios
Pai
Filho
Irmão
Folha
Parental
Descendentes
Descendentes próprios
Subárvore
Profundidade
Altura
Árvores ordenadas
Todos os filhos estão ordenados da esquerda pra direita
Árvore binária
Cada vértice não tem mais do que dois filhos
Uso de recursão
Árvore de busca binária
Valores na subárvore da esquerda são menores e na direita maiores
Árvores de busca multiway
Eficiência
Função piso(log2 n) <= h <= n-1
Os vértices viram nós
first child–next sibling
(4.5) Variable-Size-Decrease Algorithms
Busca e inserção em uma árvore de busca binária
Feito de forma recursiva
Árvore vazia, a busca termina em falha
Se não está vazia compara "v" com a raiz
Buscando um valor "v"
Se forem iguais, a busca termina
Se for menor, busca na subárvore da esquerda
Se for maior, busca na subárvore da direita
Inserção é feita de forma muito semelhante
Eficiência
Pior caso: Θ(n)
Caso médio: Θ(log n)
(5) Divide-and-Conquer
(5.3) Binary Tree Traversals and Related Properties
Árvore dividida em duas menores
Operação mais comum
Checar se a árvore está vazia
C(n) = 2n + 1
Adições
A(n) = n
Nós extras
Externos
Internos
Nós externos = nós internos + 1
Árvore binária cheia
Cada nó tem 0 ou dois filhos
Traversal
Preorder
Raiz
Subárvore da esquerda
Subárvore da direita
Inorder
Subárvore da esquerda
Raiz
Subárvore da direita
Postorder
Subárvore da esquerda
Subárvore da direita
Raiz