As árvores B são estruturas de dados balanceadas que lidam com múltiplas chaves em cada vértice e mantêm suas folhas no mesmo nível hierárquico. Qual é o processo de inserção em uma árvore B e quais são os passos envolvidos? Assinale a alternativa correta.
Questão
As árvores B são estruturas de dados balanceadas que lidam com múltiplas chaves em cada vértice e mantêm suas folhas no mesmo nível hierárquico. Qual é o processo de inserção em uma árvore B e quais são os passos envolvidos? Assinale a alternativa correta.
Alternativas
A inserção em uma árvore B começa pelo nível mais alto da árvore e desce até as folhas, verificando a existência de espaço disponível. Se houver espaço, a chave é inserida de forma ordenada.
A inserção em uma árvore B começa pela localização da página adequada para a nova chave, seguindo os ponteiros a partir da raiz. Se a página tiver espaço, a chave é inserida; caso contrário, a página é dividida e uma chave sobe para o nó pai.
A inserção em uma árvore B ocorre apenas nas folhas da árvore, e o processo de divisão das páginas é feito automaticamente quando necessário para manter o balanceamento.
A inserção em uma árvore B é realizada de maneira aleatória, não seguindo nenhum processo específico de organização das chaves.
A inserção em uma árvore B é feita de forma que as chaves sejam sempre inseridas na raiz, e a árvore cresce para baixo a partir desse ponto.
Explicação
Em uma árvore B (B-tree), a inserção segue um procedimento determinístico para manter as propriedades de ordenação e balanceamento (todas as folhas no mesmo nível e nós respeitando limites mínimo/máximo de chaves).
Passo a passo do processo de inserção:
- Buscar a posição correta: começa-se na raiz e, comparando a nova chave com as chaves do nó atual, seguem-se os ponteiros até chegar ao nó/“página” folha onde a chave deve ficar (respeitando a ordem).
- Inserir se houver espaço: se o nó folha tiver capacidade (não estiver cheio), insere-se a chave em ordem dentro desse nó e o processo termina.
- Dividir (split) se o nó estiver cheio: se o nó estiver cheio, ocorre a divisão do nó em dois nós (redistribuindo as chaves).
- Promover uma chave ao pai: uma chave (tipicamente a mediana, dependendo da implementação) é promovida (sobe) para o nó pai para separar as duas novas páginas.
- Propagação para cima, se necessário: se o pai também estiver cheio, o mesmo processo de divisão e promoção se repete recursivamente.
- Possível criação de nova raiz: se a divisão alcançar a raiz e ela precisar ser dividida, cria-se uma nova raiz, aumentando a altura da árvore em 1, mantendo o balanceamento.
A alternativa que descreve corretamente esse fluxo (localizar a página, inserir se couber, senão dividir e promover chave ao pai) é a B.
Alternativa correta: (B).
Travou em outra questão? A gente resolve.
Crie sua conta grátis e resolva 3 questões por dia com explicação passo a passo, por texto ou foto.