Questão de Informática

Duas implementações muito comuns de árvore binária balanceada de busca são as árvores AVL (sigla das iniciais dos autores: “Adelson-Velskii e Landis”) e RB (sigla das iniciais de “Red-Black”, traduzidas como “vermelha e preta” ou “rubro negra”). Considere as seguintes afirmativas: I. Em uma árvore AVL, as alturas das duas sub-árvores (esquerda e direita) de qualquer nó se diferem, no máximo, por 1 (maior altura subtraído pela menor altura). II. Qualquer nó das árvores AVL e RB podem ter 0, 1 ou 2 nós filhos (nenhum filho; um filho à esquerda ou à direita; ou dois filhos, um à esquerda e outro à direta), independentemente de sua posição na árvore. III. Em uma árvore RB, as alturas das duas sub-árvores (esquerda e direita) de qualquer nó se diferem, no máximo, pelo fator 2 (maior altura dividido pela menor altura). Sobre as afirmativas, pode-se concluir que: