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
filhos, a menos que seja uma folha, e todo vértice interno diferente da raiz tem pelo menos
, mas não mais do que
, 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.
Desenhe três B-árvores de grau 3 diferentes com altura 4.
Passo 1
Resumindo o enunciado, queremos três B-árvores de grau
e altura
. Numa B-árvore de grau
:
- A raiz, se não for folha, tem entre
e filhos. - Todo vértice interno diferente da raiz tem entre
e filhos. - Todas as folhas devem estar exatamente no nível
.
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):
nó com exatamente filhos. - Nível 1:
nós, cada um com filhos. - Nível 2:
nós, cada um com filhos. - Nível 3:
nós, cada um com filhos. - Nível 4 (folhas):
folhas.
É, na prática, uma árvore “binária perfeita” de altura
.
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):
nó com filhos. - Nível 1:
nós, cada um com filhos. - Nível 2:
nós, cada um com filhos. - Nível 3:
nós, cada um com filhos. - Nível 4 (folhas):
folhas.
É uma árvore “ternária perfeita” de altura
.
Passo 4
Árvore 3 (caso misto): combinamos ramos mínimos e máximos para variar a forma, mantendo a altura
. Por exemplo:
- A raiz tem
filhos, e . - No ramo
(subárvore “cheia”), cada vértice interno em níveis tem filhos, gerando os valores por nível . - No ramo
(subárvore “esbelta”), cada vértice interno em níveis tem filhos, gerando por nível . - Todas as folhas de
e de ficam exatamente no nível .
Isso respeita
em cada interno e mantém altura
.
Resposta
Árvore 1 (mínima): níveis com
nós.
Árvore 2 (máxima): níveis com nós.
Árvore 3 (mista): raiz com filhos, gerando subárvore cheia
e subárvore esbelta
.
Árvore 2 (máxima): níveis com
Árvore 3 (mista): raiz com