0

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 1

0

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.

Ilustração de rotação de nós de árvore.

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).

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .