Please enable JavaScript.
Coggle requires JavaScript to display documents.
Arvores - Coggle Diagram
Arvores
Conceito Geral
Nó
Nó é uma unidade básica da árvore que contém um valor ou dados e pode ter zero ou mais nós filhos. Em muitos contextos, um nó pode também ter referências para outros nós.
Raiz
A raiz é o nó superior da árvore e não possui nenhum nó pai. É o ponto de partida da árvore e de onde todos os outros nós descendem. Uma árvore pode ter apenas uma raiz.
Folhas
Folhas são nós que não têm filhos. Em outras palavras, são os nós terminais da árvore. Eles estão localizados na extremidade da hierarquia.
Filho
Um filho é um nó que está diretamente conectado a um outro nó (pai) e está em um nível mais baixo na hierarquia da árvore. Cada nó pode ter zero ou mais filhos.
-
Nível
O nível de um nó é a distância do nó até a raiz. A raiz está no nível 0, seus filhos estão no nível 1, e assim por diante.
Altura
A altura de uma árvore é a distância máxima da raiz até uma folha. Em termos mais técnicos, é o maior nível de qualquer nó na árvore. Para um nó específico, a altura é a maior distância até uma folha.
Profundidade
A profundidade de um nó é a distância do nó até a raiz. Ou seja, é o número de arestas no caminho do nó até a raiz.
Subárvore
Uma subárvore é uma árvore que consiste em um nó específico e todos os seus descendentes. Cada nó de uma árvore pode ser visto como a raiz de uma subárvore.
-
Grau
O grau de um nó é o número de filhos que o nó tem. Em uma árvore, o grau máximo entre todos os nós é conhecido como o grau da árvore.
Caracteristicas gerais
Em uma árvore com n nós, a quantidade total de arestas será sempre n - 1.
Em uma árvore, se cada nível está completamente preenchido até a altura h, o número de folhas é dado por 2^h.
-
Tipos de Árvores
Árvore de Segmentos
Uma árvore de segmentos é uma estrutura de dados usada para armazenar informações sobre intervalos ou segmentos e responder rapidamente a consultas sobre esses segmentos. É particularmente útil para operações de intervalo em arrays, como consultas de soma ou mínimo.
Árvore AVL
Uma árvore B é uma árvore balanceada que mantém dados ordenados e permite buscas, inserções e exclusões em tempo logarítmico. Diferente das árvores binárias, a árvore B pode ter mais de dois filhos por nó.
Trie
Uma trie é uma árvore de busca onde os nós representam caracteres de strings. É frequentemente usada para armazenar um conjunto de strings e permite buscas rápidas por prefixos comuns.
Árvore Binária de Busca
Uma árvore binária de busca é um tipo especial de árvore binária que mantém uma ordem específica entre os nós.
Árvore B
Uma Árvore B é uma estrutura de dados balanceada e ordenada usada principalmente em sistemas de gerenciamento de banco de dados e sistemas de arquivos.
Árvore Binária
Uma árvore binária é uma estrutura de dados em que cada nó tem no máximo dois filhos: um filho à esquerda e um filho à direita. A principal característica é a sua simplicidade e a capacidade de representar hierarquias e estruturas de árvore.
Operações em Árvores
-
Árvores AVL
Em uma Árvore AVL, que é um tipo de BST auto-balanceada, a busca é eficiente devido ao balanceamento garantido. A árvore mantém um fator de balanceamento entre -1 e 1 para cada nó, garantindo que a profundidade da árvore seja O(log n). A busca segue a mesma lógica de uma BST, mas com a vantagem de garantir que a altura da árvore é minimizada.
Árvores Trie
Em uma Trie, a busca é baseada na estrutura de prefixos. A busca segue o caminho de caracteres da raiz até os nós correspondentes à string procurada. Cada nível da Trie representa um caractere da string. A busca é eficiente e a complexidade é O(m), onde m é o comprimento da string a ser buscada.
Árvore Binária
Em uma Árvore Binária, a busca é realizada de maneira geral e não segue uma ordem específica. Inicia-se na raiz e percorre-se os filhos esquerdo e direito de forma recursiva ou iterativa. A complexidade da busca pode ser O(n) no pior caso, pois não há garantias sobre a estrutura da árvore.
Árvore B
Em uma Árvore B, a busca é feita navegando pelos nós e filhos, cada um podendo ter várias chaves e filhos. A árvore mantém a estrutura balanceada, o que garante que a busca, inserção e remoção sejam realizadas em tempo O(log n). A busca percorre os nós e suas chaves para encontrar o intervalo que contém o valor procurado.
Árvore de Segmentos
Na Árvore de Segmentos, a busca é otimizada para intervalos. Cada nó da árvore cobre um intervalo específico e a busca consulta esses intervalos para encontrar informações agregadas, como a soma ou o mínimo dentro de um intervalo. As consultas são realizadas em tempo O(log n), refletindo a estrutura balanceada da árvore.
Aplicações
Árvore B
Sistemas de gerenciamento de banco de dados (DBMS) e sistemas de arquivos, onde o balanceamento e a capacidade de lidar com grandes volumes de dados são essenciais para operações rápidas e eficientes.
Árvore AVL
Implementação de dicionários e bancos de dados que requerem busca, inserção e exclusão eficientes, onde o balanceamento constante melhora a performance.
Árvore Binária de Busca
strutura de dados para armazenamento e busca rápida de dados ordenados, como em sistemas de indexação e implementações de tabelas de símbolos em compiladores.
Árvore de Segmentos
Algoritmos de consulta de intervalo e atualização em arrays, como encontrar a soma ou o mínimo de subarrays, útil em gráficos e problemas de análise de intervalos.
Árvore Binária
Estruturas de dados básicas para implementação de árvores de expressão e árvores de decisão. Usada em algoritmos de parsing e construção de sintaxe.
Trie
Implementação de sistemas de autocompletar e verificação ortográfica, bem como indexação de prefixos em bancos de dados e sistemas de busca.