Uma B-árvore de grau \boldsymbol{k} é um árvore enraizada tal que todas as suas folhas estão em um mesmo nível, sua raiz tem no mínimo dois e no máximo k filhos, a menos que seja uma folha, e todo vértice interno diferente da raiz tem pelo menos \lceil k / 2\rceil, mas não mais do que k, filhos. Arquivos de computador podem ser acessados eficientemente quando B-árvores são usadas para representá-los.
Desenhe três B-árvores de grau 3 diferentes com altura 4.

Passo 1

Resumindo o enunciado, queremos três B-árvores de grau k=3 e altura 4. Numa B-árvore de grau 3:
  • A raiz, se não for folha, tem entre 2 e 3 filhos.
  • Todo vértice interno diferente da raiz tem entre \lceil3/2\rceil=2 e 3 filhos.
  • Todas as folhas devem estar exatamente no nível 4.

Passo 2

Árvore 1 (caso mínimo): escolhemos sempre o número mínimo de filhos em cada vértice interno.
  • Nível 0 (raiz): 1 nó com exatamente 2 filhos.
  • Nível 1: 2 nós, cada um com \lceil3/2\rceil=2 filhos.
  • Nível 2: 2\times2=4 nós, cada um com 2 filhos.
  • Nível 3: 4\times2=8 nós, cada um com 2 filhos.
  • Nível 4 (folhas): 8\times2=16 folhas.
É, na prática, uma árvore “binária perfeita” de altura 4.

Passo 3

Árvore 2 (caso máximo): escolhemos sempre o número máximo de filhos em cada vértice interno.
  • Nível 0 (raiz): 1 nó com 3 filhos.
  • Nível 1: 3 nós, cada um com 3 filhos.
  • Nível 2: 3\times3=9 nós, cada um com 3 filhos.
  • Nível 3: 9\times3=27 nós, cada um com 3 filhos.
  • Nível 4 (folhas): 27\times3=81 folhas.
É uma árvore “ternária perfeita” de altura 4.

Passo 4

Árvore 3 (caso misto): combinamos ramos mínimos e máximos para variar a forma, mantendo a altura 4. Por exemplo:
  • A raiz tem 2 filhos, A e B.
  • No ramo A (subárvore “cheia”), cada vértice interno em níveis 1,2,3 tem 3 filhos, gerando os valores por nível 1,3,9,27,81.
  • No ramo B (subárvore “esbelta”), cada vértice interno em níveis 1,2,3 tem \lceil3/2\rceil=2 filhos, gerando por nível 1,2,4,8,16.
  • Todas as folhas de A e de B ficam exatamente no nível 4.
Isso respeita \lceil3/2\rceil\le\#filhos\le3 em cada interno e mantém altura 4.

Resposta

Árvore 1 (mínima): níveis com 1,2,4,8,16 nós.
Árvore 2 (máxima): níveis com 1,3,9,27,81 nós.
Árvore 3 (mista): raiz com 2 filhos, gerando subárvore cheia 1,3,9,27,81 e subárvore esbelta 1,2,4,8,16.

Exercícios de Livros Relacionados