Estruturas de Dados 2004/2005
Árvores Binárias de Pesquisa – Número de comparações
• Uma pesquisa numa árvore binária corresponde a um caminho desde a raiz até ao
nó que contém a chave pesquisada (ou até uma árvore vazia)
• Número de comparações efectuadas até parar a pesquisa = número de nós no
caminho
• Número de comparações dependente do valor a pesquisar e da ”organização
interna da árvore”
• Número máximo de comparações = nós no caminho mais longo = altura da árvore
• Numa árvore equilibrada, o número de comparações é da ordem de log 2 N (sendo
N o número total de nós na árvore
• Numa árvore ”degenerada” o número de comparações é da ordem de N
20
Estruturas de Dados 2004/2005
Árvores AVL
G.M. Adel´son-Vel´skii e E.M. Landis (1962)
• Uma árvore AVL é uma árvore de pesquisa equilibrada: a diferença em altura
entre a subárvore esquerda e a subárvore direita (em qualquer nó) deve ser −1, 0
ou 1.
• Numa árvore AVL, cada chave é única
• As operações de inserção/ remoção tentam manter o equilibrı́o da árvore
• Habitualmente, em cada nó, existe um campo adicional que indica a situação de
equilı́brio desse nó
21
Estruturas de Dados 2004/2005
22
Árvores AVL - Inserção
• Factor de equilı́brio no nó x: F B(x) = F B(xdir ) − F (xesq )
• Numa árvore AVL, T :
F B(x) ∈ {−1, 0, 1} , ∀x ∈ T
• Caso uma inserção tenha desequilibrado a árvore, procura-se, a partir do último
nó criado ”para cima”, o primeiro nó x t.q., para o seu ”avô”, z, se tenha
F B(z) > 1 ∨ F B(z) < −1
• Uma vez que z se tornou desequilibrado pela inserção de novo nó no seu filho y,
temos que re-equilibrar a árvore através de uma re-estruturação interna entre z, y
ex
Estruturas de Dados 2004/2005
Árvores AVL - Acções de Re-estruturação do equilı́brio da árvore
• Sem acção – não há desequilı́brio
• Rotação Simples à Esquerda
• Rotação Simples à Direita
• Rotação Dupla Esquerda–Direita (L–R)
• Rotação Dupla Direita–Esquerda (R–L)
23
Estruturas de Dados 2004/2005
24
Árvores AVL - Remoção
• Caso uma remoção tenha desequilibrado a árvore, procura-se, a partir do último
nó criado ”para cima”, o primeiro nó x t.q., para o seu ”avô”, z, se tenha
F B(z) > 1 ∨ F B(z) < −1
• Seja y o pai de x. Re-estruturar z, y e x, para equilibrar a sub-árvore com raiz
em z
• Esta re-estruturação pode afectar o equilı́brio de outro nó mais acima na árvore,
pelo que é necessário continuar a verificar o equilı́brio até se atingir a raiz de T