Desenhe a árvore AVL resultante da inserção dos seguintes nós:
, 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
\ /
25 32 35