Qual é a forma correta de rotacionar dois nós (A) e (B) conectados em uma árvore binária de busca para balanceá-la?
1 Resposta
Chamemos os nós rotacionados de (a) e (b). Além disso, o ponteiro (P) é o ponteiro de raiz, (Q) é o ponteiro esquerdo de (b), (R) é o ponteiro direito de (a) e a relação de precedência de valores de nós é a seguinte: A <= a <= B <= b <= C
. A imagem a seguir mostra como começa e como termina o pedaço da árvore onde se rotaciona (a) e (b) em qualquer um dos dois sentidos.
Pode-se considerar também que o nó no topo, apontado por (P), não necessariamente é raiz (ele pode ter um nó pai acima dele) e que A, B e C podem não ser apenas nós mas subárvores (e podem ser até subárvores vazias).
Atente-se às marcações azuis e vermelhas (que mostram dois pedaços da árvore que permanecem iguais) e os ponteiros amarelos (esses, assim como o nó (B), de fora dos dois pedaços imutáveis). Repare que para rotacionar (a) e (b) é necessário apenas alterar os apontadores amarelos (P), (Q) e (R).
Para fazer a rotação da árvore da esquerda para a árvore da direita, basta apenas fazer o novo valor de (P) ser igual ao velho valor de (Q), o novo valor de (Q) ser igual ao velho valor de (R) e o novo valor de (R) ser igual ao velho valor de (P). Quer dizer, algo como (Temporário)=(P)
seguido de (P)=(Q)
seguido de (Q)=(R)
e finalmente (R)=(Temporário)
.
Para fazer a rotação da árvore da direita para a árvore da esquerda, basta o processo contrário, apenas fazer o novo valor de (P) ser igual ao velho valor de (R), o novo valor de (R) ser igual ao velho valor de (Q) e o novo valor de (Q) ser igual ao velho valor de (P). Quer dizer, algo como (Temporário)=(P)
seguido de (P)=(R)
seguido de (R)=(Q)
e finalmente (Q)=(Temporário)
.