Arbre B vs Arbre Binaire

Contenu

Contenu: Différence entre l'arbre B et l'arbre binaire
Tableau de comparaison
Arbre b
Arbre binaire
Différences Clés
Conclusion
Vidéo explicative

La différence entre B-tree et une arborescence binaire est que B-tree est une arborescence triée dans laquelle les nœuds sont triés par ordre de passage, tandis que l'arborescence binaire est une arborescence ordonnée comportant un pointeur sur chaque nœud.

Les structures de données sont les concepts les plus importants dans la programmation informatique, et dans les structures de données, les deux concepts les plus importants sont B-tree et Binary tree. Les deux sont différents l'un de l'autre. B-tree est une arborescence triée où les nœuds sont triés par ordre de passage, tandis que binary tree est une arborescence ordonnée comportant un pointeur sur chaque nœud. B-tree et binary tree sont des structures de données non linéaires. Par leur nom, les deux termes semblent être les mêmes, mais ils ne sont pas identiques car ils sont différents. Un code d'arborescence binaire est stocké dans la RAM alors qu'un code d'arborescence B est stocké sur le disque.

B-tree est un arbre M-way équilibré. B-tree est appelé arbre de tri équilibré. Il y a une traversée en ordre dans le B-tree. La complexité spatiale de B-tree est O (n). La complexité du temps d'insertion et de suppression est O (log n). Dans B-tree, la hauteur de l'arbre doit être aussi basse que possible. Dans B-tree, il ne devrait pas y avoir de sous-arbre vide. Toutes les feuilles de l'arbre doivent être au même niveau. Chaque nœud peut avoir un nombre maximal d'enfants M et un nombre minimal d'enfants M / 2. Chaque nœud de l'arborescence B-arbre devrait avoir moins de clé que de clé enfant. Dans l'arborescence B, les clés de la sous-arborescence présente à gauche de la clé sont des prédécesseurs. Lorsqu'un nœud est plein et que vous essayez d'insérer un nouveau nœud, l'arborescence est divisée en deux parties. Vous pouvez fusionner des noeuds dans l'arborescence jusqu'à ce que des noeuds soient supprimés.

Une arborescence binaire comporte deux pointeurs contenant l'adresse de ses nœuds enfants. Il existe différents types d’arbres binaires tels qu’arborescence strictement binaire, arborescence binaire complète, arborescence binaire étendue, etc. Dans l’arborescence strictement binaire, il doit y avoir un sous-arbre gauche et un sous-arbre droit, dans un arbre binaire complet, il doit y avoir deux nœuds à chaque niveau, et dans l’arbre binaire threadé, il devrait y avoir 0 à 2 nombre de nœuds. Si nous parlons de techniques transversales, trois techniques transversales sont dans l’ordre transversal, pré-transversal et post-transversal.

Contenu: Différence entre l'arbre B et l'arbre binaire

Tableau de comparaison
Arbre b
Arbre binaire
Différences Clés
Conclusion
Vidéo explicative

Tableau de comparaison

Base	Arbre b	Arbre binaire
Base	B-tree est une arborescence triée où les nœuds sont triés en ordre croisé.	Une arborescence binaire est une arborescence ordonnée comportant un pointeur sur chaque nœud.
le magasin	Le code B-tree est stocké sur le disque.	Le code de l'arbre binaire est stocké dans la RAM
la taille	La hauteur de l'arbre B sera log N	La hauteur de l'arbre binaire sera log₂ N
Application	Le SGBD est l'application de B-tree.	Le codage de Huffman est une application de l’arbre binaire.

Arbre b

Dans B-tree, il ne devrait pas y avoir de sous-arbre vide. Toutes les feuilles de l'arbre doivent être au même niveau. Chaque nœud peut avoir un nombre M maximal d'enfants et un nombre minimal M / 2 d'enfants. Chaque nœud de l'arborescence B-arbre devrait avoir moins de clé que de clé enfant. Dans l'arborescence B, les clés de la sous-arborescence présente à gauche de la clé sont des prédécesseurs. Lorsqu'un nœud est plein et que vous essayez d'insérer un nouveau nœud, l'arborescence est divisée en deux parties. Vous pouvez fusionner des noeuds dans l'arborescence jusqu'à ce que des noeuds soient supprimés.

Arbre binaire

Une arborescence binaire comporte deux pointeurs contenant l'adresse de ses nœuds enfants. Il existe des types d'arbres binaires tels qu'un arbre strictement binaire, un arbre binaire complet, un arbre binaire étendu, etc.

Dans l'arborescence strictement binaire, il doit y avoir les sous-arborescences gauche et droite, dans un arborescence binaire complète, il doit y avoir deux nœuds à chaque niveau et dans l'arbre binaire à threads, il doit y avoir un nombre de nœuds compris entre 0 et 2. Si nous parlons de techniques transversales, il existe trois techniques transversales qui sont dans l’ordre transversal, pré-transversal et post-transversal.

Différences Clés

B-tree est une arborescence triée où les nœuds sont triés en ordre croisé, tandis que Binary tree est une arborescence ordonnée comportant un pointeur sur chaque nœud.
Le code B-Tree est stocké sur le disque alors que le code Binary Tree est stocké dans la RAM.
La hauteur de l'arbre B sera logN alors que la hauteur de l'arbre binaire sera log₂ N
Le SGBD est l'application de B-tree alors que le codage de Huffman est une application de Binary Tree.