b tree b tree data structure c
Este tutorial em C ++ explica as estruturas de dados das árvores B e B +. Eles são usados para armazenar dados em discos quando os dados inteiros não podem ser armazenados na memória principal:
B-tree é uma árvore auto-balanceada, bem como uma árvore m-way especializada que é usada para acesso ao disco.
Quando a quantidade de dados a serem armazenados é muito alta, não podemos armazenar todos os dados na memória principal. Portanto, armazenamos dados no disco. O acesso aos dados do disco leva mais tempo do que o acesso à memória principal.
Quando o número de chaves dos dados armazenados em discos é muito alto, os dados geralmente são acessados na forma de blocos. O tempo de acesso a esses blocos é diretamente proporcional à altura da árvore.
=> Clique aqui para ver a série de treinamento Absolute C ++.
O que você aprenderá:
B-Tree em C ++
A árvore B é uma árvore plana, ou seja, a altura da árvore B é mantida no mínimo. Em vez disso, quantas chaves são colocadas em cada nó da árvore B. Ao manter a altura da árvore B no mínimo, o acesso é mais rápido quando comparado a outras árvores balanceadas como árvores AVL.
Uma árvore B típica é mostrada abaixo:
como ler um arquivo .bin
Geralmente, o tamanho do nó na árvore B é mantido igual ao tamanho do bloco.
Listadas abaixo estão algumas das propriedades do B-Tree.
- Todas as folhas da árvore B estão no mesmo nível.
- Uma árvore B de ordem m pode ter no máximo m-1 chaves em filhos.
- Cada nó na árvore B tem no máximo m filhos.
- O nó raiz deve ter pelo menos dois nós.
- Cada nó, exceto o nó raiz e o nó folha, contém m / 2 filhos.
A seguir, discutimos algumas das operações básicas da árvore B.
Operações básicas da árvore B
A seguir estão algumas das operações básicas do B-Tree.
# 1) Pesquisando
A pesquisa na árvore B é semelhante à da BST. Na árvore acima, se quisermos procurar o item 3, procederemos da seguinte forma:
- Compare 3 com elementos raiz. Aqui, 3<6 and 3 <15. So we proceed to the left subtree.
- Compare 3 com 4 na subárvore esquerda. Como 3<4, we proceed to the left subtree of node 4.
- O próximo nó tem duas chaves, 2 e 3. 3> 2 enquanto 3 = 3. Portanto, encontramos a chave neste nó. Retorne ao local encontrado.
A pesquisa na árvore B depende da altura da árvore. Geralmente, leva O (log n) de tempo para pesquisar um determinado item.
# 2) Inserção
A inserção de um novo item na árvore B é feita no nível dos nós folha.
A seguir está a seqüência de etapas (algoritmo) para inserir um novo item na árvore B.
- Percorra a árvore B para encontrar um local nos nós folha para inserir o item.
- Se o nó folha contém chaves
- Caso contrário, se as chaves do nó folha = m-1, então:
- Insira um novo item em um número crescente de itens.
- Pegue a mediana dos nós e divida o nó em dois nós.
- Empurre a mediana para seu nó pai.
- Se a chave do nó pai = m-1, repita as etapas acima para o nó pai também. Isso é feito até encontrarmos o nó folha apropriado.
- Por fim, insira o elemento.
- Caso contrário, se as chaves do nó folha = m-1, então:
Demonstramos a inserção na árvore B como segue.
Vamos inserir o item 70 na árvore mostrada abaixo.
gateway padrão do windows 10 não disponível
A árvore dada é com grau mínimo 'm' = 3. Portanto, cada nó pode acomodar, 2 * m -1 = 5 chaves dentro dele.
Agora inseriremos o item 70. Como podemos ter 5 chaves em um nó, comparamos o elemento 70 com o elemento raiz 30. Como 70> 30, inseriremos o item 70 na subárvore direita.
Na subárvore direita, temos um nó com as chaves 40, 50, 60. Como cada nó pode ter 5 chaves, inseriremos o item 70 neste próprio nó.
Após a inserção, a B-Tree tem a seguinte aparência.
# 3) Exclusão
Assim como a inserção, a exclusão da chave também é realizada no nível dos nós de folha. Mas, ao contrário da inserção, a exclusão é mais complicada. A chave a ser excluída pode ser um nó folha ou um nó interno.
Para deletar uma chave, seguimos a seqüência de etapas (algoritmo) abaixo.
1 Localize o nó folha.
dois. No caso de o número de chaves em um nó> m / 2, exclua a chave fornecida do nó.
3 - No caso do nó folha não ter chaves m / 2, então precisamos completar as chaves pegando as chaves das subárvores direita ou esquerda para manter a árvore B.
Seguimos estas etapas:
- Se a subárvore esquerda contém m / 2 elementos, então colocamos seu maior elemento no nó pai e movemos o elemento intermediário para o local onde a chave foi excluída.
- Se a subárvore direita contém m / 2 elementos, então colocamos seu menor elemento no nó pai e movemos o elemento intermediário para o local onde a chave foi excluída.
Quatro. Se nenhum nó tiver m / 2 nós, os passos acima não podem ser realizados, portanto, criamos um novo nó folha juntando dois nós folha e o elemento intermediário do nó pai.
5 Se um pai não tem m / 2 nós, então repetimos as etapas acima para o nó pai em questão. Essas etapas são repetidas até obtermos uma árvore B equilibrada.
A seguir está uma ilustração para excluir um nó da árvore B.
Considere a seguinte árvore B mais uma vez.
Vamos supor que queremos excluir a chave 60 da árvore B. Se verificarmos a árvore B, podemos descobrir que a chave a ser excluída está presente no nó folha. Excluímos a chave 60 deste nó folha.
Agora a árvore terá a seguinte aparência:
Podemos notar que após deletar a chave 60, o nó folha da árvore B satisfaz as propriedades requeridas e não precisamos fazer mais modificações na árvore B.
No entanto, se tivéssemos que deletar a chave 20, apenas a chave 10 permaneceria no nó folha esquerdo. Nesse caso, teríamos que mudar a raiz 30 para o nó folha e mover a chave 40 para a raiz.
Portanto, ao excluir uma chave da árvore B, deve-se tomar cuidado e não violar as propriedades da árvore B.
Traversal na árvore B
A passagem na árvore B também é semelhante à passagem na ordem no BST. Começamos recursivamente da esquerda, em seguida, enraizamos e prosseguimos para a subárvore esquerda.
Aplicações de árvores B
- As árvores B são usadas para indexar os dados, especialmente em grandes bancos de dados, pois o acesso aos dados armazenados em grandes bancos de dados em discos consome muito tempo.
- A pesquisa de dados em conjuntos de dados maiores não classificados leva muito tempo, mas pode ser melhorada significativamente com a indexação usando a árvore B.
Árvore B + em C ++
A árvore B + é uma extensão da árvore B. A diferença na árvore B + e na árvore B é que na árvore B as chaves e os registros podem ser armazenados como nós internos e também como nós folha, enquanto nas árvores B + os registros são armazenados como nós folha e as chaves são armazenadas apenas em nós internos.
Os registros são vinculados entre si em uma forma de lista vinculada. Este arranjo torna as buscas em árvores B + mais rápidas e eficientes. Os nós internos da árvore B + são chamados de nós de índice.
As árvores B + têm duas ordens, ou seja, uma para nós internos e outra para nós folha ou externos.
Um exemplo de árvore B + é mostrado abaixo.
Como a árvore B + é uma extensão da árvore B, as operações básicas que discutimos no tópico árvore B ainda se mantêm.
Ao inserir e excluir, devemos manter as propriedades básicas das Árvores B + intactas. No entanto, a operação de exclusão na árvore B + é comparativamente mais fácil, pois os dados são armazenados apenas nos nós folha e sempre serão excluídos dos nós folha.
Vantagens das árvores B +
- Podemos buscar registros em um número igual de acessos ao disco.
- Em comparação com a árvore B, a altura da árvore B + é menor e permanece equilibrada.
- Usamos chaves para indexação.
- Os dados na árvore B + podem ser acessados sequencialmente ou diretamente, pois os nós folha são organizados em uma lista vinculada.
- A pesquisa é mais rápida, pois os dados são armazenados apenas nos nós folha e como uma lista vinculada.
Diferença entre árvore B e árvore B +
B-Tree | Árvore B + |
---|---|
Os dados são armazenados em nós folha, bem como em nós internos. | Os dados são armazenados apenas em nós folha. |
A pesquisa é um pouco mais lenta, pois os dados são armazenados em nós internos e também em nós folha. | A pesquisa é mais rápida, pois os dados são armazenados apenas nos nós folha. |
Nenhuma chave de pesquisa redundante está presente. | Chaves de pesquisa redundantes podem estar presentes. |
A operação de exclusão é complexa. | A operação de exclusão é fácil, pois os dados podem ser excluídos diretamente dos nós folha. |
Os nós de folha não podem ser vinculados. | Os nós de folha são vinculados para formar uma lista vinculada. |
Conclusão
Neste tutorial, discutimos a árvore B e a árvore B + em detalhes. Essas duas estruturas de dados são usadas quando há uma quantidade muito grande de dados e quando os dados inteiros não podem ser armazenados na memória principal. Assim, para armazenar dados em discos, usamos a árvore B e a árvore B +.
perguntas e respostas da entrevista do centro de qualidade
A pesquisa em árvore B é um pouco mais lenta, pois os dados são armazenados em nós internos e também em nós folha. A árvore B + é uma extensão da árvore B e os dados aqui são armazenados apenas nos nós folha. Devido a esse fator, a busca em uma árvore B + é mais rápida e eficiente.
=> Visite aqui para obter a lista completa de tutoriais em C ++.
Leitura recomendada
- Árvore AVL e estrutura de dados de heap em C ++
- Estrutura de dados de lista vinculada em C ++ com ilustração
- Estrutura de dados da fila em C ++ com ilustração
- Estrutura de pilha de dados em C ++ com ilustração
- Estrutura de dados de lista ligada circular em C ++ com ilustração
- Introdução às estruturas de dados em C ++
- Estrutura de dados da fila de prioridade em C ++ com ilustração
- Estrutura de dados de lista duplamente vinculada em C ++ com ilustração