Para cada uma das 3 árvores abaixo indique se ela é uma árvore B válida. Caso não seja, descreva o motivo de não serem árvores B.

Para cada uma das 3 árvores abaixo indique se ela é uma árvore B válida. Caso não seja, descreva o motivo de não serem árvores B indicando as propriedades que foram violadas. Considere que todas elas possuem grau 3. Imagem sem legenda

Estrutura de Dados I

•

USP-SP

0

3

Juan Carlos Batista Leonel

09.04.2019

💡 3 Respostas

TADS 2016

11.04.2019

também quero essa resosta

1

Andre Smaira

24.05.2019

b>A ideia por trás das árvores B é que os nós internos devem ter um número variável de nós filhos dentro de um intervalo predefinido. Quando um dado é inserido ou excluído da estrutura, o número de nós filhos varia dentro de um nó.

Para manter o número de nós dentro do intervalo predefinido, os nós internos são unidos ou divididos. Como um intervalo variável de nós filhos é permitido, as árvores B não precisam ser rebalanceadas com a mesma frequência que as árvores de pesquisa binária de autoequilíbrio . Mas, por outro lado, eles podem desperdiçar memória, porque os nós não permanecem totalmente ocupados.

Os limites (um superior e um inferior) no número de nós filhos são definidos para cada implementação específica. Por exemplo, em uma árvore-B 2-3, cada nó pode ter apenas 2 ou 3 nós filhos. Uma árvore B é mantida equilibrada porque requer que todos os nós da folha estejam na mesma altura.

Assim , para a árvore binária dada, temos que:

tipo R = ref NO;

tipo NO = reg ( R : ESQ, tipot : X, R : DIR );

.....................................................

procedimento PERCURSO(R: RAIZ)

se RAIZ = nil então

imprima(“Nulo”);

senao

PERCURSO(RAIZ↑.DIR);

imprima(“Lado direito feito”);

PERCURSO(RAIZ↑.ESQ);

imprima(“Lado esquerdo feito”);