Arvores Multidirecional

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

1. É

1.1. Balanceada

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

2. Deve

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

3. Possui

3.1. Inserção

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

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

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

3.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

3.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

3.2. Busca

3.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.

3.3. Remoção

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

3.3.2. Existe 4 casos de remoção

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

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

3.3.2.2.1. Buscando sempre pela esquerda

3.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

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

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

3.3.2.4.1. Deve se juntar duas paginas

4. Permite

4.1. Realizar busca semelhante a arvore binaria

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

5. Contem

5.1. Em cada nó uma ou mais chaves

5.2. N ou menos subarvores

5.3. uma chave a menos que sua subarvores

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