Please enable JavaScript.
Coggle requires JavaScript to display documents.
Árvores - Coggle Diagram
Árvores
Aplicações e Implementações
Árvores são usadas para representar hierarquias (ex.: diretórios de arquivos, organogramas).
Árvores Binárias de Busca: Usadas para implementar dicionários e acessar grandes conjuntos de dados de forma eficiente.
Representação Computacional: Árvores binárias são geralmente implementadas com nós contendo valores e ponteiros para filhos esquerdo e direito.
Árvore: Um grafo conexo e acíclico.
Em uma árvore com V vértices, há exatamente :V−1 arestas.
Árvore Enraizada: Uma árvore com um vértice escolhido como raiz. Os níveis são definidos a partir da raiz (nível 0).
Ancestores: Vértices no caminho da raiz até um dado vértice.
Pai e Filho: Se(u,v) é a última aresta no caminho da raiz até v.,u é o pai e v é o filho.
Folha: Vértice sem filhos.
Subárvore: Todos os descendentes de um vértice formam uma subárvore enraizada nesse vértice.
Profundidade: tamanho do caminho da raiz até um vértice.
Para uma árvore binária com n nós, a altura h satisfaz log2 ≤ ℎ ≤ −1 log 2n ≤ h ≤ n−1.
Altura: tamanho do caminho mais longo da raiz até uma folha.
Representação Filho-Próximo Irmão
Cada nó tem um ponteiro para seu primeiro filho e outro para seu próximo irmão, transformando uma árvore ordenada em uma árvore binária.
Árvores Ordenadas e Binárias
Árvore Ordenada: Árvore enraizada onde os filhos de cada vértice são ordenados.
Árvore Binária: Árvore ordenada onde cada vértice tem no máximo dois filhos, designados como esquerdo e direito.
Árvore de Busca Binária (BST): Árvore binária onde para cada nó, os valores na subárvore esquerda são menores e na subárvore direita são maiores.
Busca e Inserção em uma Árvore Binária de Busca
Definição: Em uma árvore binária de busca, cada nó contém um elemento de um conjunto ordenável, de modo que todos os elementos na subárvore esquerda são menores e todos os elementos na subárvore direita são maiores que o elemento na raiz da subárvore.
Algoritmo de Busca:
Caso Base: Se a árvore está vazia, a busca termina em falha.
Comparação: Se o valor v procurado é igual ao valor da raiz K(r), o elemento desejado é encontrado.
Subárvore: Se <v < K(r), a busca continua na subárvore esquerda; se > v>K(r), a busca continua na subárvore direita.
Inserção
A inserção de uma nova chave é similar à busca.
Determina-se a posição correta para o novo nó, garantindo que a propriedade da BST (subárvore esquerda menor, subárvore direita maior) seja mantida.
Floresta: Um grafo acíclico que pode não ser conexo; seus componentes conectados são árvores.
Para cada par de vértices em uma árvore, existe exatamente um caminho simples entre eles.
Técnica de Dividir e Conquistar em Árvores Binárias
Percursos Clássicos da Árvore Binária
Preorder: Visita a raiz antes das subárvores esquerda e direita.
Inorder: Visita a raiz após a subárvore esquerda, mas antes da subárvore direita.
Postorder: Visita a raiz após as subárvores esquerda e direita.
Eficiência: A análise de eficiência dos percursos é idêntica à análise do algoritmo de altura, pois cada nó da árvore estendida é visitado recursivamente.