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.
*12. Dê um limitante superior e um limitante inferior para a altura de uma B-árvore de grau
com
folhas.
*12. Dê um limitante superior e um limitante inferior para a altura de uma B-árvore de grau
Passo 1
O enunciado define uma B-árvore de grau
como uma árvore enraizada, balanceada (todas as folhas no mesmo nível), em que a raiz tem entre 2 e
filhos (a menos que seja folha) e todo vértice interno, exceto a raiz, tem entre
e
filhos. Queremos dar um limitante superior e um limitante inferior para a altura
de uma B-árvore de grau
que tenha
folhas.
Passo 2
Para obter um limitante inferior de
(ou seja, o menor possível), vamos supor que cada vértice interno tenha o número máximo de filhos, isto é,
. Nesse caso, o número máximo de folhas que uma B-árvore de altura
pode ter é
Tomando logaritmo na base
, obtemos
Logo, limitante inferior:
Passo 3
Para obter um limitante superior de
(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
filhos. Assim, o número mínimo de folhas em uma árvore de altura
é
Isolando
:
Logo, limitante superior:
Resposta
limitante inferior:
limitante superior: