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.
*12. Dê um limitante superior e um limitante inferior para a altura de uma B-árvore de grau k com n folhas.

Passo 1

O enunciado define uma B-árvore de grau k como uma árvore enraizada, balanceada (todas as folhas no mesmo nível), em que a raiz tem entre 2 e k filhos (a menos que seja folha) e todo vértice interno, exceto a raiz, tem entre \lceil k/2\rceil e k filhos. Queremos dar um limitante superior e um limitante inferior para a altura h de uma B-árvore de grau k que tenha n folhas.

Passo 2

Para obter um limitante inferior de h (ou seja, o menor possível), vamos supor que cada vértice interno tenha o número máximo de filhos, isto é, k. Nesse caso, o número máximo de folhas que uma B-árvore de altura h pode ter é
n \;\le\; k^h.
Tomando logaritmo na base k, obtemos
h \;\ge\; \log_{k}n.
Logo, limitante inferior:
h \;\ge\; \log_{k}n.

Passo 3

Para obter um limitante superior de h (ou seja, o maior possível), vamos supor que cada vértice interno tenha o número mínimo de filhos. A raiz tem pelo menos 2 filhos, e todo outro interno tem pelo menos \lceil k/2\rceil filhos. Assim, o número mínimo de folhas em uma árvore de altura h é
n \;\ge\; 2 \,\bigl(\lceil k/2\rceil\bigr)^{\,h-1}.
Isolando h:
\bigl(\lceil k/2\rceil\bigr)^{\,h-1} \;\le\;\frac{n}{2} \quad\Longrightarrow\quad h-1 \;\le\;\log_{\lceil k/2\rceil}\!\bigl(n/2\bigr) \quad\Longrightarrow\quad h \;\le\;1+\log_{\lceil k/2\rceil}\!\bigl(n/2\bigr).
Logo, limitante superior:
h \;\le\;1+\log_{\lceil k/2\rceil}\!\bigl(\tfrac n2\bigr).

Resposta

limitante inferior:
h \;\ge\;\log_{k}n
limitante superior:
h \;\le\;1+\log_{\lceil k/2\rceil}\!\bigl(\tfrac n2\bigr).

Exercícios de Livros Relacionados