Please enable JavaScript.
Coggle requires JavaScript to display documents.
IF672 (2020.1) - Levitin Aluno: Marcos André - Coggle Diagram
IF672 (2020.1) - Levitin Aluno: Marcos André
(6) Transform-and-Conquer
(6.3) Balanced Search Trees (218-223)
Estrutura principal para implementar dicionários
Elementos na subárvore da esquerda menores
Elementos na subárvore da direita maiores
Seu uso para representar dicionários é mais eficiente no caso médio
Ө(log n)
O pior caso não é tão eficiente
Ө(n)
Abordagens para evitar essa perda no pior caso
Variedade de Simplificação por instância
Balanceamento da árvore
Balanceamento Próprio
Difere pela definição de balanceamento
Árvore AVL
Diferença entre as alturas das subárvores não passar de 1
Árvore Red-black
Altura da subárvore ser o dobro da outra
Rotações
Restauram o balanço
Variedade de mudança de representação
Permite mais de um elemento no nó da árvore de busca
Árvores 2-3
Árvores 2-3-4
Árvores-B
Árvores AVL
Fator de balanceamento de cada nó é sempre 0, 1 ou -1
Diferença entre as alturas dos nós da esquerda e direita
Inserção de nó que "desbalanceia" a árvore
Rotação
Rotação única para a direita (Rotação-R)
Transfere a raiz para a subárvore da direita
Balanço de +1 antes da inserção
Rotação única para a esquerda (Rotação-L)
Balanço de -1 antes da inserção
Transfere a raiz para a subárvore da esquerda
Rotação dupla da esquerda para a direita (Rotação-LR)
Combinação das duas rotações
Balanço de +1 antes da inserção
Rotação dupla da direita para a esquerda (Rotação-RL)
É o inverso da anterior
Eficiência
Busca e inserção, deleção
Ө(log n)
Parecida com a de busca binária num array ordenado
Desvantagens
Rotações frequentes
Manter o balanceamento dos nós