AEDs III 27/06/2011

// O ultimo algoritimo visto foi o quick sort externo.
// Agora veremos algoritimos de pesquisa, e estruturas de dados para memoria secundária.

CONCEITO:
Acesso Sequencial Indexado é uma pesquisa de dados ordenados em um arranjo, porem voce adiciona a cada N números um indice.
Cada indice fica armazenado em memória, juntamente com o menor número de seu sub-arranjo.

Ao pesquisar voce simplismente realiza uma pesquisa binária no indice em memória uma vez encontrada o sub-arranjo desejado, voce realisa outra pesuqisa binária nele.

HDs são formados por vários cilindros. Para se aproveitar isso deve manter também em memoria um indice dos cilindros, e distribuir o arranjo entre eles.

Essa estrutura não é boa para uso dinâmico, adições e exclusões são pouco eficientes.

Para adições é N-1 acessos a memória.
E também é necessário mover os inteiros.

CONCEITO:
Arvore B é uma arvore binária cuja chave é um arranjo ordenado de chaves.

Entre cada par de chaves de um nó, há um ponteiro que aponta para um outro nó com dados entre a chave a direita e à esquerda
nos extremos direita e esquerda do arranjo também há um ponteiro que leva a um nó contendo chaves maiores ou menores respectivamente que todas as chaves deste nó.
Note portanto que a arvore não é necessáriamente binária ela pode ter K filhos por nó, sendo k um número arbitrário do programador.

-------------------------------------------------------------------------------------------

Busca:
É uma busca recursiva, voce encontra em cada nó o ponteiro que aponta para o nó com a chave mais próxima da sua chave, e então reinicia a recursão no novo nó.
Até encontrar a chave ou não.

-------------------------------------------------------------------------------------------

Inserção:
Melhor Caso:
Encontre a pagina onde o número deve ser inserido,
Se a pagina estiver com espaço sobrando, insira nela mesma e retorne.

Caso Médio:
Caso contrário, divida o nó em 2 sem aumentar a profundidade da arvore, e insira no espaço vazio de um deles.
Ou seja, crie um novo filho para o pai desse nó, e divida as chaves entre estes dois nós gemeos.

Agora que voce duplicou os nós, voce deve ter espaço para adicionar.

Pior Caso:
Caso voce queira criar o irmão gemeo do seu nó, mas o pai desse nó já está com o limite de filhos, agora complica.

Faça então o irmão gemeo normalmente. porem após realizar a inserção, promova o número médio para o nó de cima ( que é o nó pai que estava lotado )

Como fazer agora para inserir esse cara no nó pai?

Bem insira de novo que nem voce fez antes, se o pai dele tiver lotado também repita o processo recursivamente.

Note que esse pai que sera duplicado, ele precisa ser duplicado porque tem N+1 filhos, divida bem esses filhos.

PS: Sempre que voce cria um novo nó, crie também um número ou arranjo de números para dividi-los, ou seja, pegue o máximo do à eskerda ou o minimo do à direita.

-------------------------------------------------------------------------------------------

Remoção:

Retira o registro assim que encontra-lo.

Melhor Caso:
O nó tem mais que N/2 registros.

Caso médio folha:
Se o nó for folha e não houver sobra de chaves:
Veja os irmãos da direita e esquerda, se um deles estiver com sobra de chaves, pegue uma chave emprestada.

Caso médio não-folha:
Se não tiver chave de sobra e
Se tiver filhos tire emprestado um nó do filho.
Se virar nó folha, puxe dos irmãos juntamente com os filhos associados.
Se não tiver irmãos, puxe do nó pai uma chave, se o pai não tiver o suficiente, faça o mesmo processo de busca de chave para o pai, e assim por diante,
Repare que não vale roubar chave dos filhos!

Se voce tiver tirando de um nó não folha encontre o sucessor imediato ou o predecessor imediato, ( ou seja o número de toda a arvore mais próximo do que voce vai tirar)

Necessáriamente esse cara agora é uma folha.

Vai roubando chaves recursivametne até chegar na raiz, se a raiz ficar sem chaves, funda os filhos dela, e faça deles a nova raiz, apagando a raiz antiga.

Nota: Isso é sempre uma arvore balanceada!

Quando voce sumir com uma raiz, pode ser preciso reordenar toda a arvore,
ai voce pode precisar de puxar a chave de um filho decer com a de um pai, e assim recursivamente até voce conseguir uma coisa ordenada.


--------------------------------------------------------------------------------