Arvores Multidirecional

Começar. É Gratuito
ou inscrever-se com seu endereço de e-mail
Arvores Multidirecional por Mind Map: Arvores Multidirecional

1. Permite

1.1. Realizar busca semelhante a arvore binaria

1.2. Em cada nó(Pagina) colocar vários valores

2. Contem

2.1. Em cada nó uma ou mais chaves

2.2. N ou menos subarvores

2.3. uma chave a menos que sua subarvores

3. É

3.1. Balanceada

3.1.1. Quando Todas as semifolhas encontra se no mesmo nível

4. Deve

4.1. O numero de filhos exceto folha deve ser o numero de chave +1

5. Possui

5.1. Inserção

5.1.1. Inserção sempre para a raiz, quando as folhas estão no mesmo nível

5.1.2. Se o elemento couber na pagina basta incluir de forma ordenada

5.1.3. Se não couber, a pagina deve ser dividida em duas e o elemento do meio deve ser promovido

5.1.4. Para inserir, realiza novamente a comparação com a raiz e verificação se é menor ou maior, para então definir qual lado o elemento será incluído, esquerda ou direita

5.1.5. Verifica se está de forma ordenada Se não estiver, faz as comparações e inseri na folha, criando outra folha e promovendo a do meio para a raiz

5.2. Busca

5.2.1. Fazer o teste com a raiz, verificando se é igual, senão for e se o valor buscado for menor que o da raiz, vai para baixo a esquerda e verifica novamente e se tiver mais chaves, realiza outra verificação, e se o valor comparado for maior que o número da chave, a próxima busca é na chave ou folha a direita.

5.3. Remoção

5.3.1. Remoção quando as folhas estão no mesmo nível, é para cima, para a raiz

5.3.2. Existe 4 casos de remoção

5.3.2.1. Se o elemento estiver em folha e a folha mantiver 50% de ocupação, basta removê-lo

5.3.2.2. Se o elemento não estiver em folha, troca lo pelo seu antecessor

5.3.2.2.1. Buscando sempre pela esquerda

5.3.2.3. Se a folha ficar com menos de 50% de ocupação, e pagina irmã vizinha tiver elementos suficientes, podem ceder uma chave

5.3.2.3.1. Verificando se é maior que a chave pai ou menor, para fazer a troca

5.3.2.4. Se a folha ficar com menos de 50% de ocupação, mas a página não puder ceder uma chave

5.3.2.4.1. Deve se juntar duas paginas

6. Tem

6.1. Semifolhas

6.1.1. Nó com pelo menos uma subarvore

6.2. Folhas

6.2.1. Nó com todas as subarvores vazia