Arborescence B et structure de données d'arbre B + en C ++

b tree b tree data structure c

Ce didacticiel C ++ explique les structures de données de l'arborescence B et de l'arborescence B +. Ils sont utilisés pour stocker des données sur des disques lorsque toutes les données ne peuvent pas être stockées dans la mémoire principale:

B-tree est un arbre auto-équilibré ainsi qu'un arbre m-way spécialisé utilisé pour l'accès au disque.

Lorsque la quantité de données à stocker est très élevée, nous ne pouvons pas stocker toutes les données dans la mémoire principale. Par conséquent, nous stockons les données sur le disque. L'accès aux données à partir du disque prend plus de temps que l'accès à la mémoire principale.

Lorsque le nombre de clés des données stockées sur les disques est très élevé, les données sont généralement accessibles sous forme de blocs. Le temps d'accès à ces blocs est directement proportionnel à la hauteur de l'arbre.

=> Cliquez ici pour la série de formations Absolute C ++.

Ce que vous apprendrez:

• B-Tree en C ++
  • Opérations de base de B-Tree
    • # 1) Recherche
    • # 2) Insertion
    • # 3) Suppression
  • Applications des arbres B
• B + Tree en C ++
  • Avantages des arbres B +
• Différence entre l'arbre B et l'arbre B +
• Conclusion
  • lecture recommandée

B-Tree en C ++

L'arbre B est un arbre plat, c'est-à-dire que la hauteur de l'arbre B est réduite au minimum. Au lieu de cela, autant de clés sont placées dans chaque nœud de l'arbre B. En gardant la hauteur de l'arbre B au minimum, l'accès est plus rapide par rapport à d'autres arbres équilibrés comme les arbres AVL.

Un arbre B typique est illustré ci-dessous:

quelle est la clé de sécurité sur un routeur

En général, la taille du nœud dans B-tree est conservée la même que la taille du bloc.

Voici quelques-unes des propriétés de B-Tree.

• Toutes les feuilles de B-tree sont au même niveau.
• Un arbre B d'ordre m peut avoir au plus m-1 clés et m enfants.
• Chaque nœud de B-tree a au plus m enfants.
• Le nœud racine doit avoir au moins deux nœuds.
• Chaque nœud, à l'exception du nœud racine et du nœud feuille, contient m / 2 enfants.

Ensuite, nous discutons de certaines des opérations de base de B-tree.

Opérations de base de B-Tree

Vous trouverez ci-dessous certaines des opérations de base de B-Tree.

# 1) Recherche

La recherche dans l'arbre B est similaire à celle dans BST. Dans l'arborescence ci-dessus, si nous voulons rechercher l'élément 3, nous procéderons comme suit:

• Comparez 3 avec les éléments racine. Ici, 3<6 and 3 <15. So we proceed to the left subtree.
• Comparez 3 avec 4 dans le sous-arbre de gauche. Comme 3<4, we proceed to the left subtree of node 4.
• Le nœud suivant a deux clés, 2 et 3. 3> 2 tandis que 3 = 3. Nous avons donc trouvé la clé à ce nœud. Revenez à l'emplacement trouvé.

La recherche dans l'arbre B dépend de la hauteur de l'arbre. Il faut généralement un temps O (log n) pour rechercher un élément donné.

# 2) Insertion

L'insertion d'un nouvel élément dans l'arborescence B se fait au niveau des nœuds feuilles.

Voici la séquence d'étapes (algorithme) pour insérer un nouvel élément dans l'arborescence B.

• Parcourez l'arborescence B pour trouver un emplacement aux nœuds feuille pour insérer l'élément.
• Si le nœud feuille contient des clés
• Sinon, si les clés du nœud feuille = m-1, alors:
  • Insérez un nouvel élément dans un nombre croissant d'éléments.
  • Prenez la médiane des nœuds et divisez le nœud en deux nœuds.
  • Poussez la médiane vers son nœud parent.
  • Si clé du nœud parent = m-1, répétez également les étapes ci-dessus pour le nœud parent. Ceci est fait jusqu'à ce que nous trouvions le nœud feuille approprié.
• Enfin, insérez l'élément.

Nous avons démontré l'insertion dans l'arbre B comme suit.

Insérons l'élément 70 dans l'arborescence ci-dessous.

VPN pour netflix gratuit

L'arbre donné a un degré minimum «m» = 3. Par conséquent, chaque nœud peut accueillir 2 * m -1 = 5 clés à l'intérieur.

Maintenant, nous insérons l'élément 70. Comme nous pouvons avoir 5 clés dans un nœud, nous comparons l'élément 70 avec l'élément racine 30. Puisque 70> 30, nous insérerons l'élément 70 dans le sous-arbre de droite.

Dans le sous-arbre de droite, nous avons un nœud avec les clés 40, 50, 60. Comme chaque nœud peut contenir 5 clés, nous insérerons l'élément 70 dans ce nœud lui-même.

Après l'insertion, l'arbre B se présente comme suit.

# 3) Suppression

Tout comme l'insertion, la suppression de la clé s'effectue également au niveau des nœuds feuilles. Mais contrairement à l'insertion, la suppression est plus compliquée. La clé à supprimer peut être soit un nœud feuille, soit un nœud interne.

Pour supprimer une clé, nous suivons la séquence d'étapes ci-dessous (algorithme).

1. Localisez le nœud feuille.

deux. Dans le cas où le nombre de clés dans un nœud> m / 2, supprimez la clé donnée du nœud.

3. Dans le cas où le nœud feuille n'a pas m / 2 clés, alors nous devons compléter les clés en prenant les clés des sous-arbres droit ou gauche pour maintenir l'arbre B.

Nous suivons ces étapes:

• Si le sous-arbre de gauche contient m / 2 éléments, nous poussons son élément le plus grand vers le nœud parent, puis nous déplaçons l'élément intermédiaire à l'endroit où la clé a été supprimée.
• Si le sous-arbre de droite contient m / 2 éléments, nous poussons son plus petit élément vers le nœud parent, puis nous déplaçons l'élément intermédiaire vers l'endroit où la clé a été supprimée.

Quatre. Si aucun nœud n'a m / 2 nœuds, les étapes ci-dessus ne peuvent pas être effectuées, nous créons donc un nouveau nœud feuille en joignant deux nœuds feuille et l'élément intermédiaire du nœud parent.

5. Si un parent est sans nœuds m / 2, nous répétons les étapes ci-dessus pour le nœud parent en question. Ces étapes sont répétées jusqu'à ce que nous obtenions un arbre B équilibré.

Vous trouverez ci-dessous une illustration pour supprimer un nœud de l'arbre B.

Considérez à nouveau l'arbre B suivant.

Supposons que nous souhaitons supprimer la clé 60 de l’arbre B. Si nous vérifions l'arbre B, nous pouvons constater que la clé à supprimer est présente dans le nœud feuille. Nous supprimons la clé 60 de ce nœud feuille.

Maintenant, l'arbre ressemblera à celui ci-dessous:

Nous pouvons remarquer qu'après suppression de la clé 60, le nœud feuille de l'arbre B satisfait les propriétés requises et nous n'avons plus besoin de modifier l'arbre B.

Cependant, si nous devions supprimer la clé 20, alors seule la clé 10 serait restée dans le nœud feuille gauche. Dans ce cas, il faudrait déplacer la racine 30 vers le nœud feuille et déplacer la clé 40 vers la racine.

Ainsi, lors de la suppression d'une clé de l'arbre B, des précautions doivent être prises et les propriétés de l'arbre B ne doivent pas être violées.

Traversée dans l'arbre B

La traversée dans l'arbre B est également similaire à la traversée dans l'ordre dans BST. Nous partons récursivement de la gauche puis arrivons à la racine et procédons vers le sous-arbre de gauche.

Applications des arbres B

• Les arbres B sont utilisés pour indexer les données, en particulier dans les grandes bases de données, car l'accès aux données stockées dans de grandes bases de données sur des disques prend beaucoup de temps.
• La recherche de données dans des ensembles de données non triés plus volumineux prend beaucoup de temps, mais cela peut être considérablement amélioré grâce à l'indexation à l'aide de l'arbre B.

B + Tree en C ++

L'arbre B + est une extension de l'arbre B. La différence entre l'arbre B + et l'arbre B est que dans l'arbre B, les clés et les enregistrements peuvent être stockés en tant que nœuds internes et feuilles, tandis que dans les arbres B +, les enregistrements sont stockés en tant que nœuds feuilles et les clés ne sont stockées que dans des nœuds internes.

Les enregistrements sont liés les uns aux autres sous forme de liste chaînée. Cette disposition rend les recherches d'arbres B + plus rapides et plus efficaces. Les nœuds internes de l'arborescence B + sont appelés nœuds d'index.

Les arbres B + ont deux ordres, à savoir un pour les nœuds internes et l'autre pour les nœuds feuilles ou externes.

Un exemple d'arbre B + est présenté ci-dessous.

Comme B + tree est une extension de B-tree, les opérations de base dont nous avons discuté sous le sujet B-tree sont toujours valables.

Lors de l'insertion et de la suppression, nous devons conserver les propriétés de base des arbres B + intactes. Cependant, l'opération de suppression dans l'arborescence B + est comparativement plus facile car les données ne sont stockées que dans les nœuds feuilles et seront toujours supprimées des nœuds feuilles.

Avantages des arbres B +

• Nous pouvons récupérer des enregistrements dans un nombre égal d'accès au disque.
• Par rapport à l'arbre B, la hauteur de l'arbre B + est moindre et reste équilibrée.
• Nous utilisons des clés pour l'indexation.
• Les données de l'arborescence B + sont accessibles séquentiellement ou directement car les nœuds feuilles sont organisés dans une liste chaînée.
• La recherche est plus rapide car les données sont stockées dans les nœuds feuilles uniquement et sous forme de liste liée.

Différence entre l'arbre B et l'arbre B +

Conclusion

Dans ce didacticiel, nous avons discuté en détail des arbres B et B +. Ces deux structures de données sont utilisées lorsqu'il y a une très grande quantité de données et lorsque toutes les données ne peuvent pas être stockées dans la mémoire principale. Ainsi, pour stocker des données sur des disques, nous utilisons B-tree et B + tree.

comment ouvrir les fichiers .jar avec java windows 10

La recherche dans l'arbre B est légèrement plus lente car les données sont stockées dans les nœuds internes ainsi que dans les nœuds feuilles. B + tree est une extension de B-tree et les données ici sont stockées uniquement dans les nœuds feuilles. En raison de ce facteur, la recherche dans un arbre B + est plus rapide et efficace.

=> Visitez ici pour la liste complète des didacticiels C ++.

lecture recommandée

• Arborescence AVL et structure de données de tas en C ++
• Structure de données de liste liée en C ++ avec illustration
• Structure de données de file d'attente en C ++ avec illustration
• Empiler la structure de données en C ++ avec illustration
• Structure de données de liste liée circulaire en C ++ avec illustration
• Introduction aux structures de données en C ++
• Structure de données de file d'attente prioritaire en C ++ avec illustration
• Structure de données de liste doublement liée en C ++ avec illustration