Please enable JavaScript.
Coggle requires JavaScript to display documents.
ÁRVORES BALANCEADAS DE BUSCA - Coggle Diagram
ÁRVORES BALANCEADAS DE BUSCA
Procuram evitar a degeneração das árvores binárias de busca e a perda de eficiência de suas operações
Procuram manter as propriedades de ordenação e eficiência nas operações que as árvores binárias de busca clássicas possuem
SIMPLIFICAÇÃO DE INSTÂNCIA
Uma árvore não balanceada se torna balanceada
Também chamadas de Árvores de Auto-balanceamento
Se uma operação de inserção ou remoção fere a condição de balanceamento, a árvore executa operações especiais chamadas de rotação com o intuito de tornar-se balanceada de novo
ÁRVORE SPLAY
ÁRVORE RUBRO-NEGRA
Tolera que a altura de uma sub-árvore seja até o dobro da altura da outra sub-árvore
ÁRVORE AVL
Tolera que a diferença entre alturas das sub-árvores seja de até 1
ROTAÇÕES EM ÁRVORES AVL
Aplicadas toda vez que uma inserção ou remoção leva o coeficiente de um nódulo a sair do intervalo 1, -1
ROTAÇÃO L
Realizada quando uma nova chave é inserida na sub-árvore da direita do filho da direita de um nódulo que tinha coeficiente -1
Imagem Espelhada
ROTAÇÃO R
Realizada quando uma nova chave é inserida na sub-árvore da esquerda do filho da esquerda de um nódulo que tinha coeficiente +1
ROTAÇÃO LR
Realizada quando uma nova chave é inserida na sub-árvore da direita do filho da esquerda de um nódulo que tinha coeficiente +1
Imagem Espelhada
ROTAÇÃO RL
Realizada quando uma nova chave é inserida na sub-árvore da esquerda do filho da direita de um nódulo que tinha coeficiente -1
Realizadas na raiz da sub-árvore do nódulo mais proximo da folha que teve seu coeficiente alterado pra 2 ou -2
Associa um valor a cada nódulo que computa a diferença entre a altura da sub-árvore esquerda e da sub-árvore direita
Esse coeficiente pode variar de -1 a 1, sendo qualquer valor fora desse intervalo um marcador de desbalanceamento
MUDANÇA DE REPRESENTAÇÃO
Admite mais de um elemento em cada nódulo da árvore
ÁRVORE 2-3
ÁRVORE 2-3-4
ÁRVORE-B