GabaritoD — 2log(N) + 1
Gabarito: letra D. A altura máxima de uma árvore vermelha e preta com N chaves, quando medida em número de nós no caminho mais longo da raiz até uma folha (contando ambos), é de ≈ 2·log₂(N) + 1. Essa expressão decorre das propriedades da árvore: a altura negra (quantidade de nós pretos em qualquer caminho) é no mínimo log₂(N+1), e a altura total (em nós) é no máximo 2·(altura negra) + 1 ≈ 2·log₂(N) + 1.
A banca testa o conhecimento do limite exato e a definição de altura. Muitos alunos confundem a altura em número de arestas com a altura em número de nós, que acrescenta 1 ao valor.
Alternativa | Fórmula | Descrição | Correta? |
|---|---|---|---|
A | log(N) | Altura de árvore binária perfeitamente balanceada (AVL no melhor caso); ignora desbalanceamento permitido por regras de coloração | ❌ |
B | log(N) + 1 | Próprio de árvores balanceadas ideais (AVL ou B-árvores de grau mínimo); altura pode ser o dobro | ❌ |
C | 2 log(N) | Aproximação assintótica, mas desconsidera constante +1 da contagem de nós ou termo log₂(N+1) no limite exato | ❌ |
D | 2 log(N) + 1 | Limite superior exato: altura em nós ≤ 2·log₂(N+1) + 1 ≈ 2·log₂(N) + 1; decorre da altura negra ≥ log₂(N+1) | ✅ |
E | N/2 | Valor típico de árvore degenerada (lista encadeada); impedido por regras de coloração; altura é O(log N) | ❌ |
log(N). Esse valor corresponde à altura de uma árvore binária perfeitamente balanceada (como uma árvore AVL no melhor caso), não ao pior caso de uma árvore vermelha e preta. Ignora o fator de desbalanceamento permitido pelas regras de coloração (que pode dobrar a altura).
log(N) + 1. Também é próprio de árvores balanceadas ideais (AVL ou B-árvores de grau mínimo). A árvore vermelha e preta pode ter altura até o dobro desse valor.
2 log(N). Expressão que se aproxima, mas desconsidera o ajuste da constante +1 resultante da contagem de nós (ou do termo log₂(N+1) no limite exato). Muitos livros usam essa forma como assintótica, mas a questão exige o valor exato da altura máxima em nós.
2 log(N) + 1. Corresponde ao limite superior exato: a altura (em número de nós) é no máximo 2·log₂(N+1) + 1, que para N grande equivale a ≈ 2·log₂(N) + 1. Esse resultado é consequência direta da propriedade de que a altura negra de uma árvore vermelha e preta com N chaves é ao menos log₂(N+1) e a altura total em nós não ultrapassa 2 vezes a altura negra mais 1.
N/2. Esse valor seria típico de uma árvore degenerada (lista encadeada), o que é impedido pelas regras de coloração da árvore vermelha e preta. A altura máxima é O(log N), não O(N).
A definição de altura varia entre autores: alguns a medem como número de arestas (resultando ≈ 2·log₂N), outros como número de nós (≈ 2·log₂N + 1). A banca optou pela segunda definição, o que justifica o +1 na resposta. Na hora da prova, verifique se o enunciado ou o contexto da disciplina adota essa convenção — principalmente em questões de estruturas de dados.
Gabarito: letra D
Link permanente: /questoes/qq896704