No tutorial a seguir, aprenderemos sobre a estrutura de dados da Árvore B e consideraremos sua visualização.
Então vamos começar.
O que é uma árvore B?
O Árvore B é um tipo especial de árvore de pesquisa multidirecional , comumente conhecido como Via M árvore, que se equilibra. Devido à sua estrutura equilibrada, essas árvores são comumente utilizadas para operar e gerenciar imensos bancos de dados e simplificar pesquisas. Em uma árvore B, cada nó pode ter no máximo n nós filhos. B Tree é um exemplo de indexação multinível em um sistema de gerenciamento de banco de dados (SGBD). Os nós folha e interno terão referências de registro. A árvore B é conhecida como árvore armazenada balanceada porque todos os nós folha estão no mesmo nível.
O diagrama a seguir é um exemplo de árvore B:
Figura 1. Árvore AB com ordem 3
Compreendendo as regras da árvore B
A seguir estão as propriedades importantes de uma árvore B:
- Todos os nós folha estão no mesmo nível.
- A estrutura de dados da Árvore B é definida pelo termo grau mínimo 'd'. O valor de 'd' depende do tamanho do bloco do disco.
- Cada nó, excluindo a raiz, deve consistir em pelo menos d-1 chaves. O nó raiz pode consistir em no mínimo 1 chave.
- Todos os nós (incluindo o nó raiz) podem consistir no máximo (2d-1) chaves.
- O número de filhos de um nó é igual ao adição do número de chaves presentes nele e .
- Todas as chaves de um nó são classificadas em ordem crescente. O filho entre duas chaves, k1 e k2, consiste em todas as chaves variando entre k1 e k2, respectivamente.
- Ao contrário da árvore de pesquisa binária, a estrutura de dados da árvore B cresce e diminui a partir da raiz. Enquanto a árvore de pesquisa binária cresce e diminui.
- Semelhante a outras árvores de pesquisa binária autobalanceadas, a complexidade de tempo da estrutura de dados da árvore B para operações como pesquisa, inserção e exclusão é O(log?n) .
- A Inserção de um Nó na Árvore B acontece apenas no Nó Folha.
Consideremos o seguinte exemplo de uma árvore B de ordem mínima 5.
Figura 2. Árvore AB de ordem 5
Nota: O valor do pedido mínimo é muito superior a 5 em uma prática Árvore B.
No diagrama acima, podemos observar que todos os nós folha estão no mesmo nível, e todos os nós não folha não possuem subárvore vazia e consistem em chaves um a menos que o número de seus filhos.
A formulação definida das regras da Árvore B:
Cada árvore B depende de um inteiro positivo constante conhecido como MÍNIMO , que é utilizado para determinar o número de elementos de dados que podem ser mantidos em um único nó.
Regra 1: A raiz pode ter apenas um elemento de dados (ou mesmo nenhum elemento de dados se também não houver filhos); todos os outros nós têm pelo menos MÍNIMO elementos de dados.
Regra 2: O número máximo de elementos de dados armazenados em um nó é duas vezes o valor de MÍNIMO .
Regra 3: Os elementos de dados de cada nó da Árvore B são armazenados em um array parcialmente preenchido, classificado a partir do menor elemento de dados (no índice 0 ) para o maior elemento de dados (na posição final utilizada da matriz).
Regra 4: O número total de subárvores abaixo de um nó não folha é sempre um a mais que o número de elementos de dados nesse nó.
- subárvore 0, subárvore 1,...
Regra 5: Com relação a qualquer nó não folha:
- Um elemento de dados no índice é maior que todos os elementos de dados no número da subárvore eu do nó e
- Um elemento de dados no índice é menor que todos os elementos de dados no número da subárvore eu+1 do nó.
Regra 6: Cada folha de uma árvore B tem a mesma profundidade. Assim, garante que uma Árvore B evite o problema de uma árvore desequilibrada.
Operações em uma estrutura de dados de árvore B
Para garantir que nenhuma das propriedades de uma estrutura de dados da Árvore B seja violada durante as operações, a Árvore B pode ser dividida ou unida. A seguir estão algumas operações que podemos realizar em uma árvore B:
- Pesquisando um elemento de dados na árvore B
- Inserção de um elemento de dados na Árvore B
- Exclusão de um elemento de dados na Árvore B
Pesquisando operação em uma árvore B
A pesquisa de um elemento em uma árvore B é semelhante à pesquisa em uma árvore de pesquisa binária. Mas em vez de tomar uma decisão bidirecional (esquerda ou direita) como uma árvore de pesquisa binária, uma árvore B toma uma decisão bidirecional em cada nó, onde m é o número de filhos do nó.
Etapas para pesquisar um elemento de dados em uma árvore B:
Passo 1: A pesquisa começa no nó raiz. Compare o elemento de pesquisa, k, com a raiz.
Etapa 1.1: Se o nó raiz consistir no elemento k, a pesquisa será concluída.
int em string
Etapa 1.2: Se o elemento k for menor que o primeiro valor na raiz, passaremos para o filho mais à esquerda e pesquisaremos o filho recursivamente.
Etapa 1.3.1: Se a raiz tiver apenas dois filhos, passaremos para o filho mais à direita e pesquisaremos recursivamente os nós filhos.
Etapa 1.3.2: Se a raiz tiver mais de duas chaves, procuraremos o restante.
Passo 2: Se o elemento k não for encontrado após percorrer toda a árvore, então o elemento de pesquisa não está presente na árvore B.
Vamos visualizar as etapas acima com a ajuda de um exemplo. Suponha que queiramos procurar uma chave k=34 na seguinte árvore B:
Figura 3.1. Uma determinada árvore B
- Primeiramente, verificaremos se a chave k = 34 está no nó raiz. Como a chave não está na raiz, passaremos para seus nós filhos. Também podemos observar que o nó raiz possui dois filhos; portanto, compararemos o valor necessário entre as duas chaves.
Figura 3.2. A chave k não está presente na raiz - Agora que podemos notar que a chave k é maior que o nó raiz, ou seja, 30, prosseguiremos com o filho direito da raiz.
Figura 3.3. A chave k> 30, vá para o filho direito - Vamos agora comparar a chave k com os valores presentes no nó, ou seja, 40 e 50, respectivamente. Como a chave k é menor que a chave esquerda, ou seja, 40, passaremos para o filho esquerdo do nó.
Figura 3.4. A chave k<40, move to left child< li> - Como o valor no filho esquerdo de 40 é 34, que é o valor necessário, podemos concluir que a chave foi encontrada e a operação de pesquisa foi concluída.
Figura 3.4. A chave k = 34, o filho esquerdo de 40
Comparamos a chave com quatro valores diferentes no exemplo acima até encontrá-la. Assim, a complexidade de tempo necessária para a operação de busca em uma árvore B é O(log?n) .
Inserindo operação em uma árvore B
Ao inserir um elemento de dados em uma árvore B, devemos primeiro verificar se esse elemento já está presente na árvore ou não. Se o elemento de dados for encontrado na Árvore B, a operação de inserção não ocorre. Porém, se não for o caso, prosseguiremos com a inserção. Existem dois cenários que precisam ser atendidos durante a inserção de um elemento no nó folha:
Etapas para inserir um elemento de dados em uma árvore B:
Passo 1: Começaremos calculando o número máximo de chaves no nó com base na ordem da Árvore B.
Passo 2: Se a árvore estiver vazia, um nó raiz será alocado e inseriremos a chave que atua como nó raiz.
Etapa 3: Iremos agora pesquisar o nó aplicável para inserção.
Passo 4: Se o nó estiver cheio:
Etapa 4.1: Iremos inserir os elementos de dados em ordem crescente.
Etapa 4.2: Se os elementos de dados forem maiores que o número máximo de chaves, dividiremos o nó completo pela mediana.
Etapa 4.3: Empurraremos a tecla mediana para cima e dividiremos as teclas esquerda e direita como filhas esquerda e direita.
Etapa 5: Se o nó não estiver cheio, iremos inseri-lo em ordem crescente.
Vamos visualizar as etapas acima com a ajuda de um exemplo. Suponha que seja necessário criar uma árvore B de ordem 4. Os elementos de dados necessários para serem inseridos na árvore B são 5,3,21,11,1,16,8,13,4 e 9 .
- Como m é igual a 3, o número máximo de chaves para um nó = m-1 = 3-1 = 2 .
- Começaremos inserindo 5 na árvore vazia.
Figura 4.1. Inserindo 5 - Vamos agora inserir 3 na árvore. Como 3 é menor que 5, inseriremos 3 à esquerda de 5 no mesmo nó.
Figura 4.2. Inserindo 3 - Vamos agora inserir 21 na árvore, e como 21 é maior que 5, ele será inserido à direita de 5 no mesmo nó. Porém, como sabemos que o número máximo de chaves no nó é 2, uma dessas chaves será movida para um nó acima para dividi-lo. Assim, 5, o elemento de dados do meio, subirá e 3 e 21 se tornarão seus nós esquerdo e direito, respectivamente.
Figura 4.3. Inserindo 21 - Agora é hora de inserir o próximo elemento de dados, ou seja, 11, que é maior que 5, mas menor que 21. Portanto, 11 será inserido como chave à esquerda do nó que consiste em 21 como chave.
Figura 4.4. Inserindo 11 - Da mesma forma, inseriremos o próximo elemento de dados 1 na árvore e, como podemos observar, 1 é menor que 3; portanto, será inserido como chave à esquerda do nó composto por 3 como chave.
Figura 4.5. Inserindo 1 - Agora, inseriremos o elemento de dados 16 na árvore, que é maior que 11, mas menor que 21. No entanto, o número de chaves nesse nó excede o número máximo de chaves. Portanto, o nó será dividido, movendo a chave do meio para a raiz. Conseqüentemente, 16 será inserido à direita de 5, dividindo 11 e 21 em dois nós separados.
Figura 4.6. Inserindo 16 - O elemento de dados 8 será inserido como uma chave à esquerda de 11.
Figura 4.7. Inserindo 8 - Inseriremos 13 na árvore, que é menor que 16 e maior que 11. Portanto, o elemento de dados 13 deve ser inserido à direita do nó que consiste em 8 e 11. Porém, como o número máximo de chaves na árvore pode for apenas 2, ocorrerá uma divisão, movendo o elemento de dados intermediário 11 para o nó acima e 8 e 13 para dois nós separados. Agora, o nó acima consistirá em 5, 11 e 16, o que novamente excede a contagem máxima de chaves. Portanto, haverá outra divisão, tornando o elemento de dados 11 o nó raiz com 5 e 16 como filhos.
Figura 4.8. Inserindo 13 - Como o elemento de dados 4 é menor que 5, mas maior que 3, ele será inserido à direita do nó que consiste em 1 e 3, o que excederá novamente a contagem máxima de chaves em um nó. Portanto, um derramamento ocorrerá novamente, movendo o 3 para o nó superior ao lado do 5.
Figura 4.9. Inserindo 4 - Por fim, o elemento de dados 9, que é maior que 8, mas menor que 11, será inserido à direita do nó composto por 8 como chave.
Figura 4.10. Inserindo 9
No exemplo acima, realizamos diferentes comparações. O primeiro valor foi inserido diretamente na árvore; depois disso, cada valor teve que ser comparado com os nós disponíveis naquela árvore. A complexidade de tempo para a Operação de Inserção em uma Árvore B depende do número de nós e.
Excluindo operação em uma árvore B
A exclusão de um elemento de dados em uma árvore B contém três eventos principais:
- Pesquisando o nó onde existe a chave a ser excluída,
- Excluindo a chave e
- Equilibrar a árvore, se necessário.
Ao excluir um elemento da árvore, pode ocorrer uma condição conhecida como Underflow. Underflow ocorre quando um nó consiste em menos que o número mínimo de chaves; deveria aguentar.
A seguir estão alguns termos que devem ser entendidos antes de visualizar a operação de exclusão/remoção:
A seguir estão três casos proeminentes da operação de exclusão em uma árvore B:
Caso 1: A exclusão/remoção da chave está no nó Folha - Este caso é ainda dividido em dois casos diferentes:
1. A exclusão/remoção da chave não viola a propriedade do número mínimo de chaves que um nó deve conter.
índice de string java
Vamos visualizar este caso usando um exemplo onde excluiremos a chave 32 da seguinte Árvore B.
Figura 4.1: Excluindo uma chave de nó folha (32) da Árvore B
Como podemos observar, excluir 32 desta árvore não viola a propriedade acima.
2. A exclusão/remoção da chave viola a propriedade do número mínimo de chaves que um nó deve conter. Nesse caso, devemos pegar emprestada uma chave de seu nó irmão mais próximo na ordem da esquerda para a direita.
Em primeiro lugar, visitaremos o irmão esquerdo mais próximo. Se o nó irmão esquerdo tiver mais do que um número mínimo de chaves, ele pegará emprestada uma chave desse nó.
Caso contrário, verificaremos se há empréstimo do nó irmão direito mais próximo.
Vamos agora visualizar este caso com a ajuda de um exemplo onde iremos deletar 31 da Árvore B acima. Neste caso, pegaremos emprestada uma chave do nó irmão esquerdo.
Figura 4.2: Excluindo uma chave de nó folha (31) da Árvore B
Se ambos os nós irmãos próximos já consistirem em um número mínimo de chaves, então mesclaremos o nó com o nó irmão esquerdo ou com o nó direito. Este processo de fusão é feito através do nó pai.
Vamos visualizar novamente excluindo a chave 30 da Árvore B acima.
Figura 4.3: Excluindo uma chave de nó folha (30) da Árvore B
Caso 2: A exclusão/remoção da chave está no nó não Folha - Este caso é ainda dividido em diferentes casos:
1. O nó não Folha/Interno, que é removido, é substituído por um predecessor em ordem se o nó filho Esquerdo tiver mais do que o número mínimo de chaves.
Vamos visualizar este caso usando um exemplo onde iremos deletar a chave 33 da Árvore B.
Figura 4.4: Excluindo uma chave de nó folha (33) da Árvore B
2. O nó não Folha/Interno, que é removido, é substituído por um sucessor em ordem se o nó filho Direito tiver mais do que o número mínimo de chaves.
Se algum dos filhos tiver um número mínimo de chaves, mesclaremos os nós filhos Esquerdo e Direito.
Vamos visualizar este caso excluindo a chave 30 da Árvore B.
quantas cidades existem nos estados unidos da américa
Figura 4.5: Excluindo uma chave de nó folha (30) da Árvore B
Após a fusão, se o nó pai tiver menos que o número mínimo de chaves, pode-se procurar pelos irmãos, como em Caso 1 .
Caso 3: No caso a seguir, a altura da árvore diminui. Se a chave de destino estiver em um nó interno e a remoção da chave levar a menos chaves no nó (que é menor que o mínimo necessário), procure o predecessor em ordem e o sucessor em ordem. Se ambos os filhos tiverem um número mínimo de chaves, o empréstimo não poderá ocorrer. Isto leva a Caso 2(3) , ou seja, mesclando os nós filhos.
Procuraremos novamente o irmão para pegar uma chave emprestada. No entanto, se o irmão também consistir em um número mínimo de chaves, então mesclaremos o nó com o irmão junto com o nó pai e organizaremos os nós filhos de acordo com os requisitos (ordem crescente).
Vamos visualizar este caso com a ajuda de um exemplo onde excluiremos o elemento de dados 10 da Árvore B fornecida.
Figura 4.6: Excluindo uma chave de nó folha (10) da Árvore B
A complexidade de tempo nos exemplos acima varia dependendo do local de onde a chave precisa ser excluída. Assim, a complexidade de tempo para a operação de exclusão em uma árvore B é O(log?n) .
A conclusão
Neste tutorial, aprendemos sobre a Árvore B e visualizamos suas diferentes operações com diversos exemplos. Também entendemos algumas propriedades e regras fundamentais da Árvore B.