Árvore de Pesquisa Memória Secundária Engenharia de Computação - UFG. - ppt carregar
PublicouFernanda Faria Alterado mais de 4 anos atrás
Apresentação em tema: "Árvore de Pesquisa Memória Secundária Engenharia de Computação - UFG."— Transcrição da apresentação:
1 Árvore de Pesquisa Memória Secundária Engenharia de Computação - UFG.
Estrutura de Dados 2 Alunos: Douglas França, Gabriel Maranhão, Matheus Queiroz, Railson Rodrigues. Goiânia, 05/12/2013
2 Árvore de pesquisa Eficiente para armazenamento de Informação;
Particularmente adequada quando existe necessidade de considerar todos ou alguma combinação de:   Acesso direto e sequencial eficientes;   Facilidade de inserção e retirada de registros;   Boa taxa de utilização de memória;   Utilização de memória primária e secundária.
3 Memória Secundária Arquivos podem armazenar mais registros;
Vantagens x Desvantagens; Transferência de Primária para Secundária; Serialização e Deserialização; Árvore inicialmente na memória secundária; Organização.
4 Páginas Todas na memória primária (após a inicialização); Contém:
Página(ap) Todas na memória primária (após a inicialização); Contém: Vetor de Itens(chave); Vetor de "ponteiros" para próximas páginas. Inteiro "n" como tamanho. Item (ap.r[2] ) Página( ap.p[0] ) 7
5 Árvore B Composta por páginas raiz, intermediárias e folhas;
Mais de um registro por página: Ordem da Árvore (m); Número de registros (2*m); Descendentes: Número de descendentes por página ((2*m)+1); Folhas todas no mesmo nível (sempre balanceado, na mesma profundidade); Registros: Ordem crescente, esquerda para direita.
6 Árvore B Nível 0: Raiz 123 423 Nível 1:Folhas 800 1231 4 12 144 356
7 Pesquisa Compara a chave digitada com o itens da raiz até encontrar o primeiro maior ou igual ou se i = n-1; Se o pesquisado for menor, vai pra página anterior, se não, página posterior; Repete o procedimento recursivamente, até encontrar, ou não o elemento desejado.
8 Árvore B Nível 0: Raiz 123 423 Nível 1:Folhas 800 1231 4 12 144 356
200 123 423 Nível 1:Folhas 800 1231 4 12 144 356 NULL
9 Inserção Inicialmente com a árvore vazia:
Página raiz será criada (NULL); Busca a posição correta da chave em uma página e insere a chave garantindo a ordenação e balanceamento; Página a ser inserida possui n < 4 elementos: Inserção normal de maneira ordenada. Página a ser inserida possui n = 4 elementos (overflow): Necessária operação de "split" (balanceamento da árvore); Verificar a chave intermediária entre as 5 chaves; Cria-se novas páginas (respeitando o balanceamento), valores menores que a chave para a esquerda e valores maiores para a direita.
10 Retira Garantir que as propriedades da árvore sejam mantida;
Número de elementos das páginas folha e intermediárias >1; Arvore continuar balanceada (níveis); Resolver o problema do "underflow"*; 5 possíveis formas de retirar um elemento. * Página com 1 ou nenhum elemento