Questão de Tecnologia da Informação · FGV STN 2024 (nº 69)

Uma Árvore B é uma estrutura de dados que organiza chaves (valores para busca) de forma hierárquica, como um índice de livro, permitindo encontrar informações rapidamente, mesmo em grandes bancos de dados. Ela garante que todas as buscas levem aproximadamente o mesmo tempo, pois todos os caminhos até os dados são igualmente longos.

• (A) Incorreta: A afirmativa 4 está incorreta, pois a complexidade de inserção em uma Árvore B é logarítmica, não linear.
• (B) Correta:
  • 1. Todas as folhas estão no mesmo nível de profundidade na árvore: Esta é uma propriedade fundamental das Árvores B, garantindo que o tempo de busca para qualquer chave seja consistente e otimizado.
  • 2. Todos os nós podem conter, no máximo, 2g - 1 chaves: De acordo com a convenção comum para o grau g (onde g é o número mínimo de filhos que um nó pode ter, exceto a raiz), um nó pode ter no máximo $2g-1$ chaves.
  • 3. Exceto pelo nó raiz, todos os demais nós devem conter, no mínimo, g -1 chaves: Esta é outra propriedade essencial que assegura que a árvore não se torne muito esparsa, mantendo sua eficiência. A raiz é a única exceção porque pode ter menos chaves quando a árvore é pequena.
  • 5. Para uma árvore com N chaves, a complexidade do algoritmo de inserção é O(log n): A eficiência das operações em Árvores B (busca, inserção, remoção) é logarítmica em relação ao número de chaves (N), pois a altura da árvore cresce logaritmicamente com N.
• (C) Incorreta: A afirmativa 4 está incorreta.
• (D) Incorreta: A afirmativa 4 está incorreta e a afirmativa 1, que é correta, não foi incluída.
• (E) Incorreta: A afirmativa 4 está incorreta. (Armadilha da banca) A complexidade O(n) é linear, significando que o tempo de execução cresce proporcionalmente ao número de elementos N. Em uma Árvore B, as operações são muito mais eficientes, pois o tempo de execução cresce com o logaritmo de N (O(log n)), o que é significativamente mais rápido para grandes volumes de dados. Confundir O(n) com O(log n) é um erro comum que desconsidera a principal vantagem de estruturas como a Árvore B.