Desenhe a árvore AVL resultante da inserção dos seguintes nós: 35,39,51,20,13,28, 22, 32, 25, 33 (nesta ordem).

Passo 1

O enunciado pede para inserir, em ordem, os valores 35, 39, 51, 20, 13, 28, 22, 32, 25 e 33 em uma árvore AVL, aplicando rotações sempre que o fator de balanceamento (diferença de alturas entre subárvores esquerda e direita) ficar fora de -1, 0 ou +1. Vamos usar as rotações LL, RR, LR e RL conforme cada caso.

Passo 2

Inserimos 35, depois 39 (fica 35→39) e depois 51. Essa última inserção deixa o nó 35 com fator de balanceamento −2 (caso RR), então aplicamos uma rotação à esquerda em 35. A árvore fica com raiz 39, filhos 35 e 51.

Passo 3

Agora inserimos 20 e depois 13. Após 13, o nó 35 fica com fator +2 (caso LL), então rotacionamos à direita em 35. O resultado é raiz 39 com subárvore esquerda cuja raiz é 20 e filhos 13 e 35.

Passo 4

Ao inserir 28, ele entra como filho esquerdo de 35, provocando fator +2 em 39 (subárvore 20 mais alta) e, dentro dela, fator −1 em 20 (inserção em sua subárvore direita). É caso LR: rotaciona-se à esquerda em 20 e depois à direita em 39. A nova raiz vira 28, com subárvores 20 e 39.

Passo 5

Os valores 22, 32 e 25 entram em seguida e, após cada inserção, a árvore permanece balanceada (não há fator de balanceamento fora de −1…+1), então não é necessária nenhuma rotação extra.

Passo 6

Finalmente inserimos 33, que vai para a subárvore de 35 (à direita de 32). Isso desbalanceia 35 com fator +2 e, dentro dele, fator −1 em 32, configurando um caso LR. Aplicamos rotação à esquerda em 32 e depois à direita em 35. A árvore volta a ficar balanceada.

Passo 7

Reorganizando tudo, obtemos a árvore AVL final com raiz 28; à esquerda 20 (filhos 13 e 22→25 à direita); à direita 39 (filhos 33→32 à esquerda e 35 à direita, e 51 como filho direito).

Resposta

     28
    /  \
  20    39
 /  \   / \
13 22 33 51
\ /
25 32 35

Exercícios relacionados