Slide Árvores B semibalanceadas -2022 1

Exemplo (ordem t = 2) 0001 0004 0007 0010 0013 0016 0019 0022 0025 0028 0033 0036 0039 0042 0045 0048 0051 0054 0057 0060 Exemplo (ordem t = 3) 0001 0004 0007 0010 0013 0016 0019 0022 0025 0028 0033 0036 0039 0042 0045 0048 0051 0054 0057 0060 Exemplo (ordem t = 1) 0001 0004 0007 0010 0013 0016 0019 0022 0025 0028 0033 0036 0039 0042 0045 0048 0051 0054 0057 0060 Histórico • Árvores B foram desenvolvidas em 1970 por Rudolf Bayer: – Estudou matemática em Munique e fez doutorado também em Matemática na Universidade de Illinois, em 1966. – Foi pesquisador nos Boeing Research Labs: Árvore-B é Árvore-Boeing e não Árvore-Bayer Publicação Original: Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Informatica 1: 173-189 (1972) Exemplo Simples (ordem t=3) E K P B D F G H M N Q T W Exemplo (ordem t = 6) 0001 0004 0007 0010 0013 0016 0022 0025 0028 0033 0036 0039 0045 0048 0051 0054 0057 0060 0019 0042 Definição (interpretação de Alan Tharp) Uma árvore B de ordem mínima t >= 1 é uma árvore com as seguintes propriedades: • Cada nodo possui os seguintes campos: <NChaves, Folha, P0, <K1,Info1>, P1, <K2,Info2>,...,<Kq,Infoq>, Pq> • Descrição dos campos: • NChaves – número de chaves armazenadas no nodo; • Folha – flag indicando se o nodo é folha ou não; • Pi – ponteiro para o nodo filho i; • K – chaves; • Infoi – ponteiro para o elemento de dados na memória ou para um registro em disco onde se encontra a chave Ki; • Nº de chaves t <= q <= 2t + 1. – A situação q = 2t + 1 é instável e provoca a explosão do nodo no ajuste subseqüente da árvore. – A situação 0 < q < t é estável somente na raiz. Quando é forçada por uma deleção fora da raiz, provoca a imediata rotação de uma chave ou fusão do nodo com um irmão. Árvores Semibalanceadas 6.7. Árvores B • Exemplos de inserção e deleção segundo a interpretação de Alan Tharp do algoritmo de Bayer INE 5408 Estruturas de Dados Inserção em uma árvore B (Alan Tharp) Algoritmo de inserção em uma árvore B: • desça a árvore em busca da chave; • a inserção é sempre feita nas folhas; • ao retornar da inserção: • verifique se o nodo está cheio (se contém 2t+1 chaves); • se o nodo estiver cheio: – dividir o nodo ao meio; – colocar a chave do meio no nodo pai (se este também encher, repetir o processo recursivamente). Inserção em uma árvore B (Alan Tharp) Algoritmo de inserção em uma árvore B: • desça a árvore em busca da chave; • a inserção é sempre feita nas folhas; • ao retornar da inserção: • verifique se o nodo está cheio (se contém 2t+1 chaves); • se o nodo estiver cheio: – dividir o nodo ao meio; – colocar a chave do meio no nodo pai (se este também encher, repetir o processo recursivamente). Inserção em uma árvore B (Alan Tharp) Algoritmo de inserção em uma árvore B: • desça a árvore em busca da chave; • a inserção é sempre feita nas folhas; • ao retornar da inserção: • verifique se o nodo está cheio (se contém 2t+1 chaves); • se o nodo estiver cheio: – dividir o nodo ao meio; – colocar a chave do meio no nodo pai (se este também encher, repetir o processo recursivamente). Inserção em uma árvore B (Alan Tharp) Algoritmo de inserção em uma árvore B: • desça a árvore em busca da chave; • a inserção é sempre feita nas folhas; • ao retornar da inserção: • verifique se o nodo está cheio (se contém 2t+1 chaves); • se o nodo estiver cheio: – dividir o nodo ao meio; – colocar a chave do meio no nodo pai (se este também encher, repetir o processo recursivamente). Inserção em uma árvore B (Alan Tharp) insere_B_tharp(nodoB raiz, infoB dado) variaveis nodoB filho = nulo; /* inicializa p/folha */ inicio SE raiz->folha ENTÃO /* insira na folha */ insere_folha_B(raiz, dado); SENÃO /* continua descendo */ filho <- selecionaRamoDescida_B(raiz, dado); insere_B(filho, dado); FIM SE /* retorna ajustando */ SE nodo_cheio_B(filho) ENTÃO /* se nodo possuir 2t+1 chaves, divida, lembrando de passar a raiz que se altera */ divide_nodo_B (raiz, filho); FIM SE fim Exemplo: Criação de uma árvore-B de Ordem t=2 e inserção do 80 k2t+1 . Neste modelo você tem de prever uma área no nodo para a chave k2t+1 e o ponteiro p2t+1 para armazenar o dado de overflow. Esta posição não é mostrada na animação. Inserção do 50: 80 move-se uma posição Inserção do 95: inserção no fim 50 80 95 Inserção do 90: 95 move-se uma posição Inserção do 60: Overflow. Valor central é 80 e dois novos nodos são gerados . 50 . 60 . 80 . 90 . 95 . Área de Overflow do Nodo: q = 2t + 1 Inserção do 65 50 60 65 80 90 95 Inserção do 70 Inserção do 75: Overflow. Nodo dividido. Valor central é 65: sobe e desloca 80 uma posição. Inserção do 55 e do 64: Só provocam reposicionamentos dentro da folha. Inserção do 51: Overflow. Nodo dividido: 50 e 55 permanecem, 60 e 64 vão para o nodo novo. Valor central é 55: sobe e desloca 65 e 80 uma posição. Inserção do 76 e 77. Inserção do 78: Overflow. Nodo dividido: 70 e 75 permanecem, 77 e 78 vão para o nodo novo. Valor central é 76: sobe e desloca 80 uma posição Raiz finalmente está completa. Inserção do 98 e 99. Inserção do 96: Overflow. Nodo dividido: 90 e 95 permanecem, 98 e 99 vão para o nodo novo. Valor central é 96: sobe e provoca novo Overflow na raiz. Nodo-raiz dividido: 55 e 65 permanecem. 80 e 96 vão para o novo nodo. 76 sobre para nova raiz que é criada. Deleções na mesma árvore (c/base na interpretação de Alan Tharp) Deleção em uma árvore B (Alan Tharp) Regra 1at: se a chave k está no nodo X e X é folha, então remova. Deleção em uma árvore B (Alan Tharp) Regra 2at: se a chave k está no nodo X e X é um nodo interno: a) se a subárvore Y predecessora inordem de X possui pelo menos t + 1 chaves: – determine a chave predecessora inordem k' em Y – substitua k por k' – recursivamente exclua k' da subárvore Y b) senão se a subárvore Z sucessora inordem de X possui pelo menos t + 1 chaves: – determine a chave sucessora inordem k' em Z – substitua k por k' – recursivamente exclua k' da subárvore Z c) senão se as subárvores Y e Z possuem apenas t chaves: – funda k e todo o nodo Z em Y – retire k e o apontador para Z de X – libere o nodo Z – recursivamente exclua k da subárvore Y Deleção em uma árvore B (Alan Tharp) Regra 2at: se a chave k está no nodo X e X é um nodo interno: a) se a subárvore Y predecessora inordem de X possui pelo menos t + 1 chaves: – determine a chave predecessora inordem k' em Y – substitua k por k' – recursivamente exclua k' da subárvore Y b) senão se a subárvore Z sucessora inordem de X possui pelo menos t + 1 chaves: – determine a chave sucessora inordem k' em Z – substitua k por k' – recursivamente exclua k' da subárvore Z c) senão se as subárvores Y e Z possuem apenas t chaves: – funda k e todo o nodo Z em Y – retire k e o apontador para Z de X – libere o nodo Z – recursivamente exclua k da subárvore Y Deleção em uma árvore B (Alan Tharp) Regra 2at: se a chave k está no nodo X e X é um nodo interno: a) se a subárvore Y predecessora inordem de X possui pelo menos t + 1 chaves: – determine a chave predecessora inordem k' em Y – substitua k por k' – recursivamente exclua k' da subárvore Y b) senão se a subárvore Z sucessora inordem de X possui pelo menos t + 1 chaves: – determine a chave sucessora inordem k' em Z – substitua k por k' – recursivamente exclua k' da subárvore Z c) senão se as subárvores Y e Z possuem apenas t chaves: – funda k e todo o nodo Z em Y – retire k e o apontador para Z de X – libere o nodo Z – recursivamente exclua k da subárvore Y Deleção em uma árvore B (Alan Tharp) Regra 2at: se a chave k está no nodo X e X é um nodo interno: a) se a subárvore Y predecessora inordem de X possui pelo menos t + 1 chaves: – determine a chave predecessora inordem k' em Y – substitua k por k' – recursivamente exclua k' da subárvore Y b) senão se a subárvore Z sucessora inordem de X possui pelo menos t + 1 chaves: – determine a chave sucessora inordem k' em Z – substitua k por k' – recursivamente exclua k' da subárvore Z c) senão se as subárvores Y e Z possuem apenas t chaves: – funda k e todo o nodo Z em Y – retire k e o apontador para Z de X – libere o nodo Z – recursivamente exclua k da subárvore Y Deleção em uma árvore B (Alan Tharp) Regra 3at: se a chave k não está em X e X é um nodo interno. 1. determine a raiz Pi[X] da subárvore onde K deve estar 2. exclua recursivamente k de Pi[X] 3. SE Pi[X] tem apenas t-1 chaves: a) Rotação de chaves - se um dos vizinhos de Pi[X] tem pelo menos t + 1 chaves : • mova uma chave de X descendo para Pi[X] • mova uma chave do vizinho de Pi[X] subindo para X • mova o apontador apropriado do vizinho para Pi[X] b) Fusão de nodos: se Pi[X] e seus vizinhos têm apenas t chaves: • funda Pi[X] com um dos seus vizinhos e com a chave ki de X • remova o par ki e pi de X • libere o nodo apontado por Infoi Deleção em uma árvore B (Alan Tharp) Regra 3at: se a chave k não está em X e X é um nodo interno. 1. determine a raiz Pi[X] da subárvore onde K deve estar 2. exclua recursivamente k de Pi[X] 3. SE Pi[X] tem apenas t-1 chaves: a) Rotação de chaves - se um dos vizinhos de Pi[X] tem pelo menos t + 1 chaves : • mova uma chave de X descendo para Pi[X] • mova uma chave do vizinho de Pi[X] subindo para X • mova o apontador apropriado do vizinho para Pi[X] b) Fusão de nodos: se Pi[X] e seus vizinhos têm apenas t chaves: • funda Pi[X] com um dos seus vizinhos e com a chave ki de X • remova o par ki e pi de X • libere o nodo apontado por Infoi Deleção em uma árvore B (Alan Tharp) Regra 3at: se a chave k não está em X e X é um nodo interno. 1. determine a raiz Pi[X] da subárvore onde K deve estar 2. exclua recursivamente k de Pi[X] 3. SE Pi[X] tem apenas t-1 chaves: a) Rotação de chaves - se um dos vizinhos de Pi[X] tem pelo menos t + 1 chaves : • mova uma chave de X descendo para Pi[X] • mova uma chave do vizinho de Pi[X] subindo para X • mova o apontador apropriado do vizinho para Pi[X] b) Fusão de nodos: se Pi[X] e seus vizinhos têm apenas t chaves: • funda Pi[X] com um dos seus vizinhos e com a chave ki de X • remova o par ki e pi de X • libere o nodo apontado por Infoi Algoritmo de Deleção em Árvore B (o ajuste de nodo é que é diferente) deleta_B(nodoB pai, nodoB nodo, infoB dado) variaveis nodoB filho; inicio SE contem_chave_B(nodo, dado) ENTÃO SE raiz->folha ENTÃO /* caso 1 */ deleta_folha_B(nodo, dado); SENÃO /* caso 2 */ deleta_interno_B(pai, nodo, dado); FIM SE SENÃO /* desce recursivamente */ filho <- selecionaRamoDescida_B(nodo, dado); deleta_B(nodo, filho, dado); /* caso 3 depois de fazer tudo */ ajusta_nodo_B(nodo, filho, dado); FIM SE fim Algoritmo de Deleção em Árvore B (o ajuste de nodo é que é diferente) deleta_B(nodoB pai, nodoB nodo, infoB dado) variaveis nodoB filho; inicio SE contem_chave_B(nodo, dado) ENTÃO SE raiz->folha ENTÃO /* caso 1 */ deleta_folha_B(nodo, dado); SENÃO /* caso 2 */ deleta_interno_B(pai, nodo, dado); FIM SE SENÃO /* desce recursivamente */ filho <- selecionaRamoDescida_B(nodo, dado); deleta_B(nodo, filho, dado); /* caso 3 depois de fazer tudo */ ajusta_nodo_B(nodo, filho, dado); FIM SE fim Algoritmo de Deleção em Árvore B (o ajuste de nodo é que é diferente) deleta_B(nodoB pai, nodoB nodo, infoB dado) variaveis nodoB filho; inicio SE contem_chave_B(nodo, dado) ENTÃO SE raiz->folha ENTÃO /* caso 1 */ deleta_folha_B(nodo, dado); SENÃO /* caso 2 */ deleta_interno_B(pai, nodo, dado); FIM SE SENÃO /* desce recursivamente */ filho <- selecionaRamoDescida_B(nodo, dado); deleta_B(nodo, filho, dado); /* caso 3 depois de fazer tudo */ ajusta_nodo_B(nodo, filho, dado); FIM SE fim Inserção de 62, 79, 91, 93 e 97 são realizadas nas folhas com apenas deslocamentos intra-nodais de posição de chaves. Deleção do 90: deletamos de um nodo folha que não viola a condição de capacidade mínima (underflow). Deleção do 76: Seu sucessor inordem (77) sobe da folha para ocupar seu lugar raiz sem causar underflow na folha. Deleção do 79: deletamos de um nodo-folha: underflow. Rearranjamos: descendo seu sucessor inordem (80) do nodo-pai e subindo o sucessor inordem do pai (90) de seu nodo-irmão da direita. Recursivamente deletamos 90 do nodo-irmão da direita. Deleção do 77: underflow provoca seqüência de junções de nodos. Ao deletar 77 seu, sucessor inordem 78 sobe da folha para a raiz: underflow nessa folha. Desce o sucessor inordem da folha (80): 91. Como a subida do sucessor inordem de 91 para repô-lo provoca underflow na folha-irmã, temos de fundir essa folha com o 91 (que desce) e a folha com (93,95). Isso provoca underflow no nodo interno (96), de onde o 91 saiu. Temos de fundir com a raiz e seu irmão da esquerda (55,65). Atribuição-Uso Não-Comercial-Compartilhamento pela Licença 2.5 Brasil Você pode: - copiar, distribuir, exibir e executar a obra - criar obras derivadas Sob as seguintes condições: Atribuição — Você deve dar crédito ao autor original, da forma especificada pelo autor ou licenciante. Uso Não-Comercial — Você não pode utilizar esta obra com finalidades comerciais. Compartilhamento pela mesma Licença — Se você alterar, transformar, ou criar outra obra com base nesta, você somente poderá distribuir a obra resultante sob uma licença idêntica a esta. Para ver uma cópia desta licença, visite http://creativecommons.org/licenses/by-nc-sa/2.5/br/ ou mande uma carta para Creative Commons, 171 Second Street, Suite 300, San Francisco, California, 94105, USA. ARS ET SCIENTIA UNIVERSIDADE FEDERAL DE SANTA CATARINA UFSC