Questão de Tecnologia da Informação · CESGRANRIO CAIXA 1/2021/NM (nº 37)

Uma Árvore Binária de Busca (ABB) é uma árvore onde, para cada nó, todos os valores da subárvore esquerda são menores que o nó, e todos os valores da subárvore direita são maiores que o nó. Essa regra vale para todos os nós, não apenas para a raiz.

• (A) Incorreta: O nó raiz (valor 10) tem o valor 8 à sua direita, mas 8 é menor que 10, violando a regra de que à direita só podem estar valores maiores.
• (B) Incorreta: O nó de valor 6 tem o valor 7 à sua esquerda, mas 7 é maior que 6, violando a regra de que à esquerda só podem estar valores menores.
• (C) Correta: Para cada nó, todos os elementos da esquerda são menores e todos os da direita são maiores (ex: raiz 8, esquerda 3 e 1, direita 10 e 14), cumprindo a definição de ABB.
• (D) Incorreta: O nó de valor 5 tem o valor 9 à sua esquerda, mas 9 é maior que 5, quebrando a propriedade fundamental.
• (E) Incorreta: O nó de valor 12 tem o valor 7 à sua direita, mas 7 é menor que 12, violando a regra da subárvore direita.

Armadilha da banca (distrator mais tentador, provavelmente B ou D): A pegadinha clássica é verificar apenas a raiz ou apenas os filhos imediatos, esquecendo de checar todos os descendentes. Por exemplo, numa árvore com raiz 10, filho esquerdo 5 e neto direito 8, o 8 está à esquerda da raiz (correto, pois é menor que 10), mas está à direita do 5 (incorreto, pois 8 > 5). A banca desenha árvores que parecem "quase certas" na raiz, mas escondem uma violação em um nó mais profundo. A solução é testar cada nó individualmente, comparando com seus filhos imediatos, e depois verificar se a ordem global (esquerda < nó < direita) se mantém para todos.