Árvores Balanceadas e Algoritmos

Prévia do material em texto

Algoritmos e Complexidade
Árvores Balanceadas
Árvores
Existem diversas árvores, com diversos tipos de regramento para alocação e
remoção de dados.
Árvores que se balanceiam para manter os tamanhos e estruturas.
Desta forma, fugimos da possibilidade do pior caso da árvore binária
Crescimento em uma única direção
E mantemos uma estrutura mais coesa e organizada.
Este será o objeto de estudo a nossa próxima aula: ÁRVORES BALANCEADAS
Árvores
Árvore AVL é uma árvore binária de busca balanceada
Uma árvore balanceada (árvore completa) são as árvores que minimizam o
número de comparações efetuadas no pior caso para uma operação.
Contudo, para garantir essa propriedade em aplicações dinâmicas, é preciso
reconstruir a árvore para seu estado ideal a cada operação sobre seus nós
(inclusão ou exclusão)
O nome AVL vem de seus criadores soviéticos Adelson Velsky e Landis, e sua
primeira referência encontra-se no documento "Algoritmos para organização da
informação" de 1962
Árvores
Uma árvore binária é denominada AVL quando a diferença de altura entre as
subárvores da esquerda e direita de um nó qualquer N não é superior a 1.
Uma árvore é considerada desbalanceada quanto esta propriedade não for
verificada.
O fato da árvore estar balanceada resulta em ganho de desempenho para
operações realizadas sobre árvores binárias, como na inserção, remoção e
consulta de valores.
Se a árvore estiver balanceada, todas estas operações gastam, no pior caso, um
tempo O(logn), que neste caso representa a altura da árvore binária balanceada.
Se a árvore não estiver balanceada, o tempo de busca no pior caso pode ser O(n),
ou seja, equivalente ao tempo de busca de valores em uma lista encadeada (no
pior caso, todos os elementos tem que ser consultados).
Árvores
Podemos ter o desbalanceamento de uma árvore em qualquer operação de
inserção ou remoção.
Nestes casos, árvores balanceadas aplicam procedimentos para rebalancear suas
estruturas
Árvores
Numa árvore AVL denotamos por fator de balanceamento a diferença da altura de
sua subárvore da esquerda pela altura da subárvore da direita.
Desta forma, os nós deverão possuir uma estrutura para armazenar sua altura em
relação à raiz.
Árvores
Um nó é dito balanceado quando o seu FB(v) está com os valores
+1 : subárvore esquerda mais alta que a direita em um nível
-1 : subárvore direita mais alta que a esquerda em um nível
0 : subárvore com alturas iguais
Para fatores maiores que 1 ou menores que -1 temos desbalanceamento.
Fazemos inserções e remoções (inicialmente) da mesma forma que em uma
árvore binária de busca.
Mesma regra de direita e esquerda!
Árvores
Quando uma inserção ou remoção realizada em um nó altera o balanceamento da
árvore, é necessário efetuar uma transformação na árvore, tal que:
O percurso em ordem fique inalterado em relação a árvore desbalanceada. Isto é, a árvore
continua a ser uma árvore binária de busca.
A árvore transformada saiu de um estado de desbalanceamento para um estado de
balanceamento
Chamamos de rotações as operações que alteram o balanceamento de uma
árvore T, mantendo a sua lógica.
Para garantirmos as propriedades da árvore AVL rotações devem ser feitas
conforme necessário após operações de remoção ou inserção.
Seja P o nó pai, FE o filho da esquerda de P e FD o filho da direita de P podemos definir 4
tipos diferentes de rotação:
Árvores
Rotação à esquerda simples:
Árvores
Rotação à esquerda simples:
Colocamos a subárvore esquerda, na parte da subárvore desbalanceada e
verificamos novamente o balanceamento.
Árvores
Rotação à direita simples:
Operação simétrica à rotação à esquerda simples, mas quando o
desbalanceamento ocorre do outro lado.
Qual seria o resultado desta rotação?
Árvores
Rotação dupla à esquerda
Deve ser efetuada quando a diferença das alturas h dos filhos do pai é igual a 2 e a
diferença das alturas h dos filhos de FE é igual a -1.
Nesse caso devemos aplicar uma rotação à esquerda no nó FE e, em seguida, uma
rotação à direita no nó P. 
Árvores
Rotação dupla à direita
Deve ser efetuada quando a diferença das alturas h dos filhos de P é igual a 2 e a
diferença das alturas h dos filhos de FE é igual a -1.
Nesse caso devemos aplicar uma rotação à esquerda no nó FE e, em seguida, uma
rotação à direita no nó P. 
Árvores
Árvores binárias balanceadas:
Árvores
Árvores
Outra forma de balancear uma árvore binária de busca é através do algoritmo DSW.
Desenvolvido por Colin Day, Quentin F. Stout e Bett L. Warren (DSW).
Baseia-se em percorrer uma árvore binária de busca torna-la uma “árvore
degenerada” (uma árvore de pior caso, similar a uma lista encadeada).
Posteriormente percorrendo para torna-la uma árvore balanceada.
Sua lógica funciona de seguinte maneira:
Árvores
Para cada nó vtx da árvore faça:
Se vtx não é raiz e for filho à esquerda
Então faça vtx ser filho direito do seu avô
A subárvore direita de vtx se torna a subárvore esquerda de seu pai
O nó vtx passa a ter seu pai como filho à esquerda
Árvores
Na 2ª fase a espinha dorsal é transformada em uma árvore balanceada.
Em cada descida para baixo, cada segundo (2 depois) nó até um ponto
determinado é rotacionado ao redor de seu ascendente
Árvores
Para reorganizar a árvore faremos compressão, que são rotações a esquerda até
atingirmos o balanceamento da árvore.
Árvores
Árvores
O algoritmo DSW trabalha sobre a árvore toda.
Se houver a necessidade de manter o balanceamento a cada inserção ou remoção,
então sua eficiência fica bastante prejudicada.
Desta forma, apesar da complexidade de desenvolvimento mais elevada, a árvore
AVL possui mais eficiência na sua manutenção.
Árvores
Existem diversos tipos de árvores, com diversas lógicas diferentes e modelos
funcionais!
Algumas das mais importantes são:
Árvores
Árvores
Árvores B+ são extremamente famosas e úteis em computação
Estruturas de dados como essa são muito empregadas em banco de dados e
sistemas de arquivos como o NTFS para o Microsoft Windows, o sistema de
ficheiros ReiserFS para Unix, o XFS para IRIX e Linux, e o JFS2 para AIX, OS/2 e
Linux, usam este tipo de árvore. 
Árvores
Link de como a base de dados PostgreSQL utiliza estas árvores:
https://www.qwertee.io/blog/postgresql-b-tree-index-explained-part-1/