Lista Árvores Multiway e B

Prévia do material em texto

LISTA Árvores Multiway / B
Estruturas de Dados II
Prof. Murilo Ybanez
Suponha que uma árvore multiway de ordem k tem n nós. Qual a maior e a menor altura possíveis?
Qual a principal motivação para o uso de árvores multiway? Justifique a sua resposta.
Considerando a árvore multiway abaixo, de ordem 3, desenhe a árvore resultante das seguintes operações, usando os algoritmos mostrados em sala.
Inserção das chaves 11 e 22.
Partindo da árvore obtida no item (a), remoção das chaves 12, 25, 8, 11 e 5.
Idem ao item (b), porém garantindo que árvore continue top-down
Insira a seqüência de chaves a, b, f, g, k, d, h, m, j, e, s, i, r, x, c, l, n, t, u, p em uma árvore B de ordem 5, desenhando a árvore resultante.
Repita o exercício anterior para árvores B de ordem 4 e 7.
Considere a afirmação: uma árvore B não pode crescer em profundidade até que esteja com todos os nós cheios. Ela é correta? Explique sua resposta.
Considerando a árvore B de ordem 4 resultante da inserção das chaves 45, 80, 90, 95, 70, 15, 25, 30, 33, e 8, realize as operações de remoção das chaves 90, 95 e 80, fornecendo a árvore B após cada remoção.