Please enable JavaScript.
Coggle requires JavaScript to display documents.
Mapa Mental 9 - Coggle Diagram
Mapa Mental 9
- BSTs balanceadas nomeadas em homenagem aos inventores.
- Fator de balanceamento de cada nó é mantido em 0, +1 ou -1.
- Utiliza rotações para manter o equilíbrio.
- Operações como inserção e exclusão são logarítmicas em eficiência.
- Desvantagens incluem rotações frequentes e manutenção do equilíbrio.
- Introduz nós com múltiplas chaves.
- 2-nós contêm uma chave, 3-nós contêm duas chaves.
- Sempre perfeitamente balanceadas em altura.
- Busca, inserção e exclusão são logarítmicas em eficiência.
- Generalização para B-árvores é discutida.
- Visão Geral da Árvore de Busca Binária (BST):
- Estrutura básica para dicionários.
- Cada nó contém um elemento.
- Elementos na subárvore esquerda são menores, na subárvore direita são maiores.
- Utiliza a técnica de mudança de representação para eficiência.
- Complexidade de tempo para busca, inserção e exclusão é O(log n) no caso médio.
- No pior caso, as operações são O(n) devido à potencial degeneração da árvore.
- Abordagens para Melhorar a Eficiência da BST:
- Simplificação de instância: Transformar BSTs desbalanceadas em balanceadas.
- Mudança de representação: Permitir múltiplos elementos por nó, levando a árvores balanceadas.
-
- BSTs oferecem operações de dicionário eficientes, mas podem degenerar no pior caso.
- Árvores AVL e 2-3 oferecem soluções para balancear BSTs e manter eficiência.
- Árvores AVL usam rotações para equilibrar, mantendo eficiência logarítmica.
- Árvores 2-3 permitem múltiplas chaves por nó, garantindo equilíbrio perfeito e eficiência logarítmica.
- Tanto Árvores AVL quanto Árvores 2-3 têm compensações e são usadas em diferentes contextos com base em requisitos.