Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM12 - BST, Trees - Coggle Diagram
MM12 - BST, Trees
PERCURSOS EM ÁRVORES BINÁRIAS
Objetivo: visitar todos os nós
Cada nó visitado exatamente uma vez
Ordem da visita depende do algoritmo
Aplicações
Impressão
Busca
Cópia
Avaliação de expressões
Destruição da árvore
Depth-First Traversal
Explora um ramo até o fim
Depois retorna
Preorder
Aplicações
Cópia da árvore
Representação hierárquica
Serialização
1) Nó atual
2) Subárvore esquerda
3) Subárvore direita
Inorder
Propriedade Fundamental da BST
Produz elementos em ordem crescente
Explora diretamente a propriedade da BST
Aplicações
Ordenação
Impressão ordenada
Recuperação de chaves em ordem
1) Subárvore esquerda
2) Nó atual
3) Subarvore direita
Postorder
Aplicações
Remoção de árvores
Liberação de memória
Avaliação de expressões
1) Subárvore esquerda
2) Subárvore esquerda
3) Nó atual
BINARY SEARCH TREE (BST)
Para qualquer nó:
Subárvore esquerda: todos os valores menores
Subárvore direita: todos os valores maiores
Operação de Busca
Comparação com a Raiz
Igual -> elemento encontrado
Menor -> seguir para esquerda
Maior -> seguir para direita
Repetição
Processo continua recursivamente
Término
Elemento encontrado
Ou ponteiro nulo alcançado
Complexidade
Árvore Balanceada
O(log n)
Árvore Degenerada
O(n)
Inserção em BST
1) Procurar posição adequada
2) Aplicar mesma lógica da busca
3) Ao encontrar posição vazia, inserir novo nó
Influência da Ordem de Inserção
Inserções Ordenadas
Produzem árvores degeneradas
Estrutura semelhante a lista encadeada
Impacto
Altura determina eficiência
Menor altura -> operações mais rápidas
Inserções Balanceadas
Melhor desempenho
Produzem árvores mais baixas
ÁRVORES (Trees)
Definição
Estrutura de dados não linear
Organiza elementos em níveis
Relacionamento pai-filho
Existe um único caminho da raiz até qualquer nó
Componentes Fundamentais
Nó (Node)
Unidade básica da árvore
Armazena informação
Mantém ligações para seus filhos
Raiz (Root)
Primeiro nó da árvore
Não possui pai
Ponto de entrada da estrutura
Aresta (Edge)
Conexão entre pai e filho
Define os relacionamentos da árvore
Folha (Leaf)
Nó sem filhos
Representa o final de um ramo
Nó Interno
Possui pelo menos um filho
Atua como intermediário na estrutura
Medidas da Árvore
Grau de um Nó
Número de filhos do nó
Profundidade (Depth)
Distância da raiz até o nó
Número de arestas percorridas
Altura de um Nó
Maior caminho até uma folha descendente
Altura da Árvore
Altura da raiz
Equivale ao maior nível existente
Nível
Nós com mesma profundidade pertencem ao mesmo nível