Árvore 2-3-4: Uma Alternativa Balanceada

Prévia do material em texto

1
Árvore 2-3-4
Árvores Balanceadas
• Algoritmo de árvore binária de pesquisa tem um 
pior caso ruim (se os dados estão em ordem 
crescente ou decrescente)
• Para isto usa-se algoritmos de árvores 
balanceadas 
– Árvores balanceadas são aquelas que os nós 
externos (folhas) aparecem em no máximo dois 
níveis adjacentes
• O custo para manter uma árvore balanceada 
após cada inserção é muito alto.
2
Árvore 2-3-4
• Precisa flexibilizar os dados para isso, permitir 
que o nó contenha mais de um dado. O nó 
poderá ter 2 ou 3 chaves – chamados nós-3 ou 
nós-4.
– Nó-3 tem 3 arestas saindo dele: 1 para os nós 
contendo registros menores que as 2 chaves; outro 
para os nós maiores que as 2 chaves; e outro para 
nós entre as 2 chaves
– Similarmente, os nós 4 têm 4 arestas saindo dele: 1 
para cada intervalo
• (Nós em árvores binárias poderiam ser nós-2)
Exemplo
ER
AAC HIN S
3
Inserção
• Inserir: Faz uma busca “sem sucesso” (como 
em árvores binárias)
– Se for Nó 2 o transforme em nó-3
– Se for nó-3 transforme em nó-4
– Se for nó-4? 
• Divide o nó-4 (HIN) em 2 nós e passa uma de suas chaves 
(a do meio) para seu pai (passa a ser um nó 4)
• No entanto, se o pai do nó a ser dividido já for um nó 4, teria 
que ir subindo na árvore até que encontrasse um que não 
fosse.
• Solução: divide todos os nós 4 na descida a procura da 
posição da nova chave.
Exemplo – Insere G
EIR
AAC GH N S
4
Análise
• Buscas em árvores 2-3-4 nunca passam mais de log n + 
1 nós, logo O(log n)
– A distância da raiz para as folhas é sempre a mesma. 
Transformações não mudam esta distância, exceto no pior caso 
em que a transformação divide a raiz e aumenta em 1 a 
distância de todos os nós para a raiz.
– Se todos os nós forem nós-2, então a árvore será uma árvore 
binária completa (altura log n), se tiver nós 3 ou 4, isto só pode 
diminuir a altura.
• Inserções requerem menos de logn N + 1 divisões de nó 
nos pior caso (na média menos de 1)
– O pior caso da inserção seria todos os nós no caminho de 
inserção fossem nós-4, e neste caso todos seriam divididos. 
– Árvores construídas a partir de uma permutação randômica de 
n, o pior caso se torna pouco provável