Please enable JavaScript.
Coggle requires JavaScript to display documents.
M8 (Binary Tree Traversals and Related Properties, Trees, Searching and…
M8
Binary Tree Traversals and Related Properties
Conjunto finito de nós com raiz, esquerda e direita
Uso da técnica divide-and-conquer
Exemplo: Algoritmo Recursivo para Altura de uma Árvore Binária
Divide-and-conquer: Altura = max{altura da subárvore esquerda, altura da subárvore direita} + 1
Recorrência para comparações e adições
Computação da altura: Maior caminho da raiz a uma folha
Análise da Eficiência
Recorrência para comparações e adições (A(n))
Análise da eficiência em termos de comparações e adições
Medida de tamanho da instância: Número de nós na árvore (n)
Extensão da Árvore com Nós Externos
Nós externos (externos) e nós originais (internos)
Número de nós externos (x) em relação ao número de nós internos (n)
Introdução de nós externos para análise
Prova da Relação entre Nós Internos e Externos
Equação: x = n + 1
Aplicabilidade a árvores binárias cheias
Algoritmo de Travessias: Pré-Ordem, Em Ordem e Pós-Ordem
Pré-ordem: Raiz, Subárvore Esquerda, Subárvore Direita
Em ordem: Subárvore Esquerda, Raiz, Subárvore Direita
Pós-ordem: Subárvore Esquerda, Subárvore Direita, Raiz
Análise da Eficiência das Travessias
Eficiência idêntica à análise da altura da árvore
Chamadas recursivas para cada nó da árvore
Trees
Aplicações de Árvores na Computação
Descrição de hierarquias
Implementação de dicionários
Acesso eficiente a grandes conjuntos de dados
Codificação de dados
Análise de algoritmos recursivos
Conceitos em Árvores com Raiz
Ancestrais, descendentes, filhos, pais
Folhas, altura, profundidade
Subárvores
estruturas em árvores que consistem em um vértice (nó) e todos os seus descendentes (filhos, netos, etc.). De forma mais simples, uma subárvore é uma parte de uma árvore que é, por si só, uma árvore. Ela mantém a estrutura hierárquica da árvore maior da qual faz parte.
Altura de um vértice e altura da árvore
Árvores Ordenadas
Ordem nos filhos de cada vértice
Exemplo de árvore binária
Árvores de busca binária (BST)
Eficiência de Algoritmos em Árvores
Importância da altura da árvore
Inequalidades para a altura de uma árvore binária
Implementação de árvores em computadores
Representação de Árvores em Computadores
Nós com informações e ponteiros para filhos
Representação de árvores binárias de busca
Representação de árvores ordenadas: first child–next sibling
Propriedades das Árvores
Número de arestas é sempre |V| - 1
Importância para detecção de ciclos em grafos conectados
Árvores com Raiz
Um caminho simples entre dois vértices
Transformação de árvore livre para árvore com raiz
Searching and Insertion in a Binary Search Tree
Árvore binária com elementos ordenados
Comparação de elementos: Menor à esquerda, maior à direita
Busca em uma Árvore de Busca Binária
Abordagem Recursiva
Comparação com o nó raiz
Caso base: Árvore vazia ou correspondência encontrada
Continuação da busca na subárvore adequada
Inserção em uma Árvore de Busca Binária
Variável-Size-Decrease Algorithm: Redução do problema em cada iteração
Altura da árvore é crucial
Semelhança com a busca: Comparação e inserção recursiva
Pior Caso na Busca Binária
Construção com inserções sucessivas em sequência crescente ou decrescente
Eficiência no pior caso: O(n) devido à altura da árvore
Árvore Severamente Inclinada
Eficiência na Busca Binária
Número médio de comparações: 2ln n ≈ 1.39 log2 n
Inserção tem eficiência semelhante à busca
Média: O(log n)