Please enable JavaScript.
Coggle requires JavaScript to display documents.
Árvores de busca balanceadas - Coggle Diagram
Árvores de busca balanceadas
basicamente, existem duas abordagens para obtermos uma árvore balanceada:
simplificação de instância
nesta abordagem uma árvore não balanceada é transformada em uma balanceada.
entretanto, implementações específicas diferem sobre a definição de balanceamento:
para
AVL tree
's, a diferença entre as alturas das subárvores da direita e esqueda não podem exceder 1 unidade.
já
red-black tree
's são classificadas como balanceadas se a altura de uma das subárvores não ultrapassa 2 vezes a altura da outra.
quando uma inserção ou deleção desbalanceia a árvore, é utilizada uma operação chamada de
rotação
, para que a árvore volte a ficar equilibrada.
mudança de representação
esta abordagem é famosa por permitir mais de um elemento registrado em seus nós.
aqui também existem distinções de árvores relacionadas ao tipo que estamos implementando, normalmente em relação a quantidade de elementos que cada nó suporta, mas todas continuam perfeitamente balanceadas:
2-3 trees
2-3-4 trees
B-trees
AVL trees
tratando mais especificamente sobre
AVL tress
, essa é uma estrutura que pode ser definida como uma
árvore de busca binária
com fator de balanceamento que pode variar entre
1
,
0
e
-1
- definido pela diferença entre as alturas das subárvores da esquerda e da direita.
nesse tipo de árvore, a operação de
rotação
sempre é aplicada em um nó quando seu balanceamento se torna
2
ou
-2
, assim, a árvore volta ponto considerado de equilíbrio.
existem 4 tipos de rotação:
single left rotation
(ou
L-rotation
): é executada quando um nó é inserido no filho à direita da subárvore da direita nos casos em que a árvore fique desbalanceada.
single right rotation
(ou
R-rotation
): é executada quando um nó é inserido no filho à esquerda da subárvore da esquerda nos casos em que a árvore fique desbalanceada.
double left-right rotation
(ou
LR-rotation
): é aplicada quando inserimos um novo nó na árvore à direita de um filho à esquerda do nó raiz quando este já possuia fator de balanceamento
+1
antes da inserção; esta combinação de duas rotações simples, primeiro é aplicada uma
L-rotation
na subárvore à esquerda do nó raiz e, em seguida, é aplicada uma
R-rotation
na nova subárvore formada agora à partir daquele nó que anteriormente era considerado a raiz da árvore.
double right-left rotation
(ou
RL-rotation
): é aplicada quando inserimos um novo nó na árvore à esquerda de um filho à direita do nó raiz quando este já possuia fator de balanceamento
+1
antes da inserção; esta combinação de duas rotações simples, primeiro é aplicada uma
R-rotation
na subárvore à direita do nó raiz e, em seguida, é aplicada uma
L-rotation
na nova subárvore formada agora à partir daquele nó que anteriormente era considerado a raiz da árvore.
eficiência
para as operações de busca e inserção (e no pior caso), esse tipo de estrutura possui uma classificação de
big theta(log de n)
a implementação da remoção nesse tipo de estrutura é um pouco mais complexa do que a inserção, mas em questão de eficiência ela pode ser classificada da mesma maneira.