Questão 163057

• Banca: CESGRANRIO
• Órgão: Petrobras
• Ano: 2010
• Provas: CESGRANRIO - 2010 - Petrobrás - Analista de Sistemas Júnior - Processos de Negócios
• Disciplina: Algoritmos e Estrutura de Dados

Uma árvore B é um tipo de árvore que se mantém balanceada com o decorrer do tempo. Para tanto, ela usa uma série de operações que garantem a manutenção de uma série de propriedades importantes, uma das quais é a ordem da árvore que pode ser definida como o número máximo de elementos que podem ser armazenados em um nó da árvore. Com base nesses conceitos, qual das situações a seguir representa uma propriedade das árvores B?

• A. Em uma árvore B de ordem maior do que 1, não é permitido que uma folha armazene apenas um elemento.
  
• B. Em uma árvore B de ordem d, a raiz armazena um número de elementos n tal que .
  
• C. Em uma árvore B de ordem d, pode haver folhas em alturas diferentes da árvore até que tenham sido inseridos, pelo menos, 2d+1 elementos.
  
• D. Em um nó de uma árvore B que contenha n elementos não vazios, podem-se ter, no máximo, n/2 ponteiros apontando para vazio (nil ou null).
  
• E. Em um nó interno de uma árvore B que contenha n elementos, têm-se exatamente n+1 ponteiros que não apontam para vazio (nil ou null).

Gabarito: E

Comentários

• Nós em árvores B, também denominado páginas, geralmente são representados por um conjunto de elementos apontando para seus filhos, estes que por sua vez também podem ser conhecidos como folhas. Alguns autores consideram a ordem de uma árvore B como sendo a quantidade de registros que a página pode suportar. Outros consideram a ordem como a quantidade de campos apontadores. Todo nó da árvore tem um número mínimo de elementos, que é dado pela metade do valor da ordem do nó, truncando o número caso a árvore seja de ordem ímpar, exceto para a raiz da árvore, que pode ter o mínimo de um registro. Por exemplo, os nós de uma árvore de ordem 5, devem ter, no mínimo 5 / 2 = 2,5 registros, ou seja, dois registros. A quantidade de filhos que um nó pode ter é sempre a quantidade de registros do nó mais 1 (V+1). Por exemplo, se um nó tem 4 registros, este nó terá obrigatoriamente 5 apontamentos para os nós filhos.

  Exemplo de estrutura em C:

  #define M 5 //ordem da arvorestruct No{    int n;    char chave[M-1];    struct No *pProx[M];};

• a) Em uma árvore B de ordem maior do que 1, não é permitido que uma folha armazene apenas um elemento.
  
  Errado. Seja a ordem = 2, logo a árvore tem no máximo ordem/2 filhos, que neste exmplo tem 1 filho.
  
  b) Em uma árvore B de ordem d, a raiz armazena um número de elementos n tal que .
  Errado. A raiz armazena 1 < n < 2d
  
  c) Em uma árvore B de ordem d, pode haver folhas em alturas diferentes da árvore até que tenham sido inseridos, pelo menos, 2d+1 elementos.
  Errado. Uma das propriedades da árvore B é o seu fator de preenchimento em que a quantidade de descendente no nó não poderá ultrapassar a sua ordem e nem ser menor que a sua ordem dividida por 2.
  
  d) Em um nó de uma árvore B que contenha n elementos não vazios, podem-se ter, no máximo, n/2 ponteiros apontando para vazio (nil ou null).
  Errado. Pode ter no máximo n+1 ponteiros que apontam para o vazio, se o nó for folha.
  
  
  
  
• Fernanda,  permita-me discordar da sua solução para o item a.
  Uma árvore B de ordem d um nó interno deve ter entre d < n < 2d chaves. Então uma árvore de ordem 2, um nó deve ter no mínimo 2 chaves e no máximo 4.
  Acredito que esse item está errado, pois o nó raiz, no início da montagem da árvore, é também um nó folha e como você corretamente colocou um nó raiz pode ter entre 1 < raiz < 2d chaves. Somente nesse instante é que um nó folha, independente de sua ordem poderia ter uma única chave armazenada.
  Se meu entendimento estiver incorreto, peço que me esclareçam.
  Bons estudos.
• Sobre a alternativa e) , Não haveria um caso em que por exemplo um nó interno com 1 elemento apontase para apenas uma sub-arvore ? é obrigado apontar para 2 subarvores ?
• Para mim a letra E não está totalmente correta, pois está falando que "não apontam para o vazio" mas segundo http://www.lcad.icmc.usp.br/~nonato/ED/B_arvore/btree.htm temos :
  "Se X é um nó interno então ele possui n+1 ponteiros f₁, f₂...f_n+1 para seus filhos (podendo alguns serem nulos)"