Une autre différence entre l'arbre B-tree et l'arborescence binaire est que B-tree doit avoir tous ses nœuds enfants au même niveau alors que l'arborescence binaire n'a pas une telle contrainte. Un arbre binaire peut avoir un maximum de 2 sous-arbres ou nœuds alors que dans B-tree peut avoir M no de sous-arbres ou de nœuds où M est l'ordre de l'arborescence.
Tableau de comparaison
| Base de comparaison | Arbre b | Arbre binaire |
|---|---|---|
| Contrainte essentielle | Un nœud peut avoir au maximum M nombre de nœuds enfants (où M est l'ordre de l'arbre). | Un nœud peut avoir au maximum 2 nombre de sous-arbres. |
| Utilisé | Il est utilisé lorsque les données sont stockées sur le disque. | Il est utilisé lorsque les enregistrements et les données sont stockés dans la RAM. |
| Hauteur de l'arbre | log M N (où m est l'ordre de l'arbre M-way) | log 2 N |
| Application | Code structure de données d'indexation dans de nombreux SGBD. | Optimisation du code, codage de Huffman, etc. |
Définition de l'arbre B
Un arbre B est l'arbre M-way équilibré, également appelé arbre de tri équilibré. C'est semblable à l'arbre de recherche binaire où les noeuds sont organisés sur la base d'un parcours en ordre. La complexité spatiale de B-tree est O (n). La complexité du temps d'insertion et de suppression est O (log n).
Certaines conditions doivent être remplies pour un arbre B:
- La hauteur de l'arbre doit être aussi minime que possible.
- Au-dessus des feuilles de l'arbre, il ne devrait pas y avoir de sous-arbres vides.
- Les feuilles de l'arbre doivent venir au même niveau.
- Tous les nœuds doivent avoir le moins d'enfants, sauf les nœuds de départ.
Propriétés du B-arbre d'ordre M
- Chaque nœud peut avoir un nombre maximal d'enfants M et un nombre minimal d'enfants M / 2 ou un nombre quelconque de 2 au maximum.
- Chaque nœud a une clé de moins que les enfants avec un maximum de clés M-1.
- La disposition des clés est dans un ordre spécifique au sein des nœuds. Toutes les clés du sous-arbre présent dans la gauche de la clé sont des prédécesseurs de la clé, et celles présentes dans la droite de la clé sont appelées successeurs.
- Au moment de l'insertion d'un nœud complet, l'arborescence est scindée en deux parties et la clé avec la valeur médiane est insérée dans le nœud parent.
- L'opération de fusion a lieu lorsque les nœuds sont supprimés.
Définition de l'arbre binaire
Une arborescence binaire est une structure arborescente pouvant avoir au plus deux pointeurs pour ses nœuds enfants. Cela signifie que le degré le plus élevé qu'un nœud puisse avoir est 2 et qu'il peut également y avoir un nœud à un degré.
Il existe certaines variantes d'un arbre binaire, telles que l'arbre strictement binaire, l'arbre binaire complet, l'arbre binaire étendu, etc.
- L'arbre strictement binaire est un arbre où chaque nœud non terminal doit avoir un sous-arbre gauche et un sous-arbre droit.
- Un arbre est appelé un arbre binaire complet lorsqu'il satisfait à la condition d'avoir 2 i nœuds à chaque niveau, où i est le niveau.
- Le binaire fileté est un arbre binaire composé de 0 nombre de nœuds ou de 2 nombre de nœuds.
Techniques de traversée
La traversée d’arbres est l’une des opérations les plus fréquentes sur la structure de données arborescentes, dans laquelle chaque nœud a été visité une fois de manière systématique.
- Inorder- Dans cette traversée d'arbres, le sous-arbre de gauche est visité de manière récursive, puis le nœud racine est visité et le dernier sous-arbre de droite est visité.
- Preorer: dans cette arborescence, le nœud racine est visité en premier, puis sous-arbre de gauche et enfin sous-arbre de droite.
- Postorder - Cette technique visite les sous-arborescences gauche, puis droite et au dernier nœud racine.
Principales différences entre l'arbre binaire et l'arbre binaire
- Dans l'arborescence B, le nombre maximal de nœuds enfants qu'un nœud non terminal peut avoir est M, M étant l'ordre de l'arborescence. D'autre part, un arbre binaire peut avoir au plus deux sous-arbres ou nœuds enfants.
- B-tree est utilisé lorsque les données sont stockées sur le disque alors que binary tree est utilisé lorsque les données sont stockées dans la mémoire rapide comme la RAM.
- Un autre domaine d’application pour B-tree est la structure de données d’indexation de code dans les SGBD. En revanche, l’arbre binaire est utilisé pour l’optimisation du code, le codage de Huffman, etc.
- La hauteur maximale d'un arbre B est log M N (M étant l'ordre de l'arbre). Par contre, la hauteur maximale de l’arbre binaire est log 2 N (N est le nombre de nœuds et base est 2 car c’est pour binaire).
Conclusion
L'arbre B est utilisé sur les arbres de recherche binaire et binaire. La raison principale est la hiérarchie de la mémoire où la CPU est connectée au cache avec les canaux à bande passante élevée, tandis que la CPU est connectée au disque par le canal à bande passante réduite. Une arborescence binaire est utilisée lorsque les enregistrements sont stockés dans la RAM (petite et rapide) et B-tree est utilisée lorsque des enregistrements sont stockés sur le disque (grande et lente). L'utilisation de l'arborescence à la place de l'arborescence binaire réduit donc considérablement le temps d'accès en raison du facteur de ramification élevé et de la hauteur réduite de l'arborescence.
