Dando continuidade ao estudo da Árvore Binária de Busca Balanceada AVL, vamos aprender nesta aula como realizar a operação de rotação à esquerda para rebalancear nossa árvore.
Desenvolver uma rotação envolve vários passos lógicos. Então, ajuda se você tiver uma figura, um desenho, que simule a rotação que você irá implementar. A figura a seguir tem exatamente este objetivo, ajudar a entender a sequência de passos a serem realizados para que a rotação ocorra sem nenhum problema.
O trecho de código a seguir apresenta a função que fará uma rotação à esquerda em nossa Árvore AVL.
Observe que há uma sequência que precisa ser seguida. Na rotação à esquerda o nó raiz deve e se tornar filho à esquerda do nó que era seu filho à direita. Contudo, quem garante que o filho à direita não possui nenhum filho? Então, a primeira ação é garantir que não iremos perder esse filho caso ele exista. A variável y aponta para o filho à direita da raiz e a variável f (de filho) aponta para o filho à esquerda de y.
Agora podemos fazer a troca. O filho à esquerda de y será o nó raiz e o filho à direita do nó raiz será o filho que salvamos na variável f.
Os nós r e y foram movidos de posição na árvore, então precisamos recalcular a altura deles. A altura de um nó na árvore é a altura de sua maior subárvore mais 1.
Por fim, observe que a raiz da árvore é alterada ao fazer uma rotação, então precisamos retornar a nova raiz, que neste caso é y.
/*
função para a rotação à esquerda
*/
No* rotacaoEsquerda(No *r){
No *y, *f;
y = r->direito; // y aponta para a subárvore direita da raiz r
f = y->esquerdo; // f aponta para o filho esquerdo de y
y->esquerdo = r; // o filho esquerdo de y passa a ser a raiz r
r->direito = f; // o filho direito de r passa a ser f
// recalcula a altura dos nós que foram movimentados
r->altura = maior(alturaDoNo(r->esquerdo), alturaDoNo(r->direito)) + 1;
y->altura = maior(alturaDoNo(y->esquerdo), alturaDoNo(y->direito)) + 1;
return y;
}
Na aula seguinte faremos a rotação à direita.
