Um conjunto de 10 chaves, numeradas de 1 a 10, serão inseridas em uma árvore binária de busca (ou árvore binária de pesquisa). Cinco alternativas para a ordem de inserção das chaves são apresentadas a seguir.

Ordem de inserção 1: 1 2 3 4 5 6 7 8 9 10

Ordem de inserção 2: 3 1 10 2 7 5 6 4 8 9

Ordem de inserção 3: 5 3 8 7 10 9 6 4 1 2

Ordem de inserção 4: 1 10 2 9 3 8 4 7 5 6

Ordem de inserção 5: 5 8 7 6 3 1 2 10 9 4

Agora, considere as seguintes afirmações:

I. A altura da árvore gerada pela ordem de inserção 4 é menor do que a altura da árvore gerada pela ordem de inserção 1.

II. Na árvore gerada pela ordem de inserção 1, nenhum nó tem filho da esquerda.

III. A árvore gerada pela ordem de inserção 2 é uma árvore balanceada.

IV. As árvores geradas pelas ordens de inserção 3 e 5 são idênticas.

Está(ão) correta(s)