Please enable JavaScript.
Coggle requires JavaScript to display documents.
Árvores de busca balanceadas - Coggle Diagram
Árvores de busca balanceadas
Qual a vantagem da implementação de uma árvore binária sobre um dicionário básico?
Em casos normais, sua eficiência temporal é de Θ(log
n
).
Porém, nos piores casos, suas operações estão em Θ(
n
), porque a árvore pode se degenerar e ficar desbalanceada com sua altura igual a
n-1
.
Foram então desenvolvidos 2 perspectivas para preservar as propriedades de uma clássica árvore de busca binária e evitar seu desbalanceamento:
1.
Uma simplificação de uma instância: árvores de busca binária desbalanceadas transformadas em árvores balanceadas, chamadas
self-balancing
.
Árvores AVL:
requere que a diferença dos tamanhos dos nós das subárvores à direita e à esquerda nunca excedam 1.
Árvores rubro-negra (red-black):
aceita que o tamanho de uma subárvore seja o dobro do tamanho de outra subárvore do mesmo nó.
Se uma inserção ou remoção de um nó, cria uma árvore com um requisito violado de balanceamento, a árvore é reestruturada por uma transformação especial chamada
rotação
, que recupera seu balanceamento.
Árvores splay
2.
Uma troca de representação: permite mais de um elemento em um nó de uma árvore binária.
Árvores 2-3
Árvores 2-3-4
B-Árvores
Elas se diferem na qtde. de elementos permitidos em um único nó de uma árvore binária, mas todas as 3 são perfeitamente balanceadas.
Árvores AVL
Uma
árvore AVL
é uma árvore de busca binária, na qual o
fator de balanceamento
(diferença entre o tamanho dos nós das subárvores à direita e à esquerda) de cada nó é 0, +1 ou -1.
Se um novo nó inserido faz a árvore ficar desbalanceada, a árvore é transformada usando rotação.
Uma
rotação
em uma árvore AVL é uma transformação local na sua subárvore enraizada na qual o balanço do seu nó é +2 ou -2.
Se este caso acontecer em muitos nós, a árvore enraizada no nó desbalanceado que estiver mais perto da folha que foi inserida, é rotacionada.
Existem 4 tipos de rotações, com dois deles sendo espelho dos outros:
Rotação-R ou single right rotation
: acontece quando uma chave nova é inserida na subávore à esquerda do filho à esquerda de uma árvore que tinha o balanço da sua raiz como +1 antes da inserção.
Rotação-L ou single left rotation
: é o espelho da rotação-R, e acontece quando uma chave nova é inserida na subávore à direita do filho à direita de uma árvore que tinha o balanço da sua raiz como -1 antes da inserção.
Rotação-LR ou double left-right rotation:
é uma combinação de duas rotações: da rotação-L da subárvore à esquerda de raiz
r
seguida pela rotação-R na nova árvore enraizada em
r
. Acontece depois que uma nova chave é inserida na subárvore à direita do filho à esquerda de uma árvore que tinha o balanço da sua raiz como +1 antes da inserção.
Rotação-RL ou double right-left rotation:
é o espelho da rotação-LR.
As rotações não são transformações triviais, mas podem ser feitas em tempo constante. Elas não somente devem garantir que as árvores estejam balanceadas, mas também devem preservar os requisitos básicos de uma árvore de busca binária.
Eficiência das árvores AVL
Como com qualquer árvore de busca, sua característica crítica é sua altura.
Suas operações de inserção e procura estão em Θ(log
n
) no pior caso.
A operação de busca em uma árvore AVL, requere, em casos normais, quase a mesma qtde. de comparações que uma operação de busca em um array ordenado por busca binária.
A operação de remoção em uma árvore AVL é consideravelmente mais difícil que a inserção, mas felizmente está na mesma classe de eficiência que a inserção, que seria a logarítmica.
As desvantagens de uma árvore AVL são suas rotações frequentes e sua necessidade de manter os nós balanceados.