Algoritmos e estrutura de dadosÁrvores

• (FGV 2021)

Considere uma árvore B+ com as seguintes características.

I. A raiz é uma folha ou um nó que contém, no mínimo, dois filhos.

II. Cada nó diferente do nó raiz e das folhas possui no mínimo d filhos.

III. Cada nó tem no máximo 2 d filhos. Cada nó possui entre d -1 e 2 d -1 chaves, exceto o raiz que possui entre 1 e 2 d -1 chaves.

IV. Somente os nós folhas contêm dados associados às chaves.

Assinale o número máximo de acessos necessários para localizar uma chave, com d =10, num universo de 10 milhões de chaves.