Dando continuidade ao estudo da Árvore Binária de Busca Balanceada AVL, vamos aprender nesta aula como realizar a operações de rotação dupla para rebalancear nossa árvore.

Antes de mais nada preciso alertar que é fundamental que você tenha entendido as rotações anteriores para entender as rotações duplas. Uma rotação dupla é uma sequência de duas rotações simples.

Uma rotação dupla é necessária quando a árvore não pende apenas para a direita ou apenas para a esquerda, mas há uma alternância nos sentidos.

Rotação Dupla Direita Esquerda

A figura a seguir apresenta um caso onde são necessárias duas rotações, uma para a direita e outra para a esquerda. Observe que a árvore inicialmente pende para a direita e depois para a esquerda, lembrando o sinal matemático de maior ( > ).

A primeira rotação não ocorre na raiz desbalanceada, mas no seu filho à direita. Tem o objetivo de trocar de lugar os nós 200 e 150. Ao realizar esta troca, a árvore obterá a forma que já vimos nas aulas anteriores, neste caso, pendendo completamente para a direita. Agora, podemos aplicar uma rotação à esquerda na raiz 100 para promover o 150 à raiz da árvore tendo como filho à esquerda o 100.

Rotação Dupla Esquerda Direita

Esta rotação é semelhante à anterior apenas invertendo a ordem das rotações.

A figura a seguir apresenta um exemplo típico de uma rotação dupla esquerda direita. Observe que a árvore não pende completamente para a esquerda, lembrando o sinal matemático de menor ( < ).

Neste caso a primeira rotação, para a esquerda, tem o objetivo de trocar os nós 100 e 150, fazendo com que a árvore fique completamente pendendo para a esquerda. Em seguida, mais uma rotação, agora à direita, aplicada na raiz 200, deixa a árvore balanceada novamente.

As funções de rotação simples à direita e à esquerda vistas nas aulas anteriores alteram a raiz da árvore. Assim, precisamos receber esse retorno após a primeira rotação e novamente retornar o resultado da segunda rotação a fim de não perder nenhuma alteração realizada na árvore.

/*
    Funções para as rotações duplas
*/
No* rotacaoEsquerdaDireita(No *r){
    r->esquerdo = rotacaoEsquerda(r->esquerdo);
    return rotacaoDireita(r);
}

No* rotacaoDireitaEsquerda(No *r){
    r->direito = rotacaoDireita(r->direito);
    return rotacaoEsquerda(r);
}