5 types d'arbre binaire dans la structure de données expliqués

Un arbre binaire est une structure de données arborescente non linéaire qui contient chaque nœud avec un maximum de 2 enfants. Le nom binaire suggère le nombre 2, donc tout arbre binaire peut avoir un enfant gauche et droit.

Un pointeur représente un arbre binaire vers le nœud le plus élevé, généralement appelé racine de l'arbre. Chaque nœud d'un arbre binaire contient des données, un pointeur vers l'enfant gauche et un pointeur vers l'enfant droit. Les pointeurs sont utilisés pour implémenter un arbre binaire. Le pointeur racine désigne le premier nœud de l'arbre. Pour créer un arbre binaire, vous devez d'abord créer un nœud.

Après avoir été familiarisé avecce qu'est un arbre binaire dans la structure de données , vous devez également connaître les opérations de base effectuées sur un arbre binaire.Vous pouvez exécuter des fonctions telles que l'insertion d'un élément, la suppression d'un élément, la recherche d'un élément et la traversée de l'arbre binaire.

Toutarbre binaire dans la structure de données est utilisé de deux manières différentes en informatique.Premièrement, ils sont utilisés pour accéder aux nœuds en fonction d'étiquettes ou de valeurs spécifiques liées à chaque nœud. Deuxièmement, ils sont utilisés comme représentations de données avec une structure ramifiée pertinente.

Avant de parcourir les différentstypes d'arbres binaires , familiarisons-nous d'abord avec les terminologies utilisées dans un arbre binaire.

Nœud : il contient une valeur de données dans un arbre binaire.

Racine : le nœud le plus élevé de tout arbre binaire est appelé la racine d'un arbre.

Taille : Il indique le nombre de nœuds dans un arbre binaire.

Nœud parent : un nœud dans un arbre binaire avec un enfant.

Nœud enfant : C'est un nœud issu d'un nœud parent s'éloignant de la racine de l'arbre binaire.

Nœud interne : C'est un nœud avec au moins un enfant dans un arbre binaire.

Nœud feuille : C'est un nœud sans enfant.Il s'agit alternativement d'un nœud externe.

Profondeur d'un arbre de nœuds : elle est calculée dans le contexte d'un nœud particulier.Il est appelé le nombre d'arêtes d'un nœud particulier à la racine.

Longueur du chemin interne d'un arbre : elle fait référence à la somme des niveaux de chaque nœud interne dans un arbre binaire.

Longueur du chemin externe d'un arbre : elle est définie comme la somme des niveaux de chaque nœud externe dans un arbre binaire.

Hauteur de nœud dans un arbre : C'est le nombre d'arêtes d'un nœud spécifique au nœud feuille le plus profond de l'arbre binaire.La hauteur de la racine sera toujours supérieure à celle des autres nœuds de l'arbre binaire.

Voyons maintenant les détails de 5types d'arbre binaire.

Types d'arbre binaire

1. Arbre binaire complet

Cetarbre binaire dans la structure de données est également connu sous les noms d'arbre binaire propre et d'arbre binaire strict.C'est l'un destypes d'arbre binaire les plus fondamentaux dans la structure des données.Un arbre binaire complet est défini comme un arbre binaire où chaque nœud doit avoir deux ou aucun enfant du tout.

Il est alternativement caractérisé comme un arbre binaire dans lequel chaque nœud comprend deux enfants à l'exception des nœuds feuilles. Les nœuds dans lesquels l'adresse du nœud racine est stockée sont appelés nœuds enfants de la racine. Ces nœuds dépourvus d'enfants sont appelés nœuds feuilles.

Vous devez parcourir tous les nœuds pour vérifier si un arbre est un arbre binaire. Le code renverra "False" si un nœud a un enfant. Il renverra "True" si tous les nœuds ont 0 ou 2 enfants.

Voici les propriétés d'un arbre binaire complet :

• Le nombre de nœuds feuilles est égal au nombre de nœuds internes + 1. Par exemple, si le nombre de nœuds internes est de 4, le nombre de nœuds feuilles est égal à 5.
• Le nombre maximum de nœuds et le nombre de nœuds dans un arbre binaire sont égaux. Il est représenté par 2h+1 -1.
• Le nombre minimum de nœuds dans un arbre binaire complet est de 2h-1.
• La hauteur minimale d'un arbre binaire complet est log 2 (n+1) – 1.
• La hauteur maximale d'un arbre binaire complet est h = (n+1)/2.

2. Arbre binaire parfait

Un arbre binaire parfait est l'un de cestypes d'arbres binaires dans lesquels chaque nœud doit avoir 0 ou 2 enfants, et le niveau de chaque nœud feuille doit être le même.En d'autres termes, les arbres binaires parfaitsdans la structure de données sont définis comme les arbres où tous les nœuds intérieurs possèdent deux branches et les nœuds sans branches (nœuds feuilles) existent au même niveau.

Dans ce contexte, le niveau d'un nœud est la distance ou la hauteur du nœud racine. Vous pouvez considérer un arbre binaire parfait comme un arbre binaire complet dans lequel le dernier niveau est également complètement occupé.

Apprenezdes cours de science des donnéesen ligne dans les meilleures universités du monde.Gagnez des programmes Executive PG, des programmes de certificat avancés ou des programmes de maîtrise pour accélérer votre carrière.

3. Arbre binaire complet

Un arbre binaire complet est l'un de ces types d'arbre binaire dans la structure de données dans lequel tous les niveaux de l'arbre sont entièrement remplis.Le dernier niveau de l'arbre binaire peut ou non être complètement rempli. Cependant, chaque nœud doit être situé à la position la plus à gauche du dernier niveau du nœud. Les nœuds doivent être inclus à partir de la gauche.

Ils sont l'un destypes essentiels d'arbres binaires car ils offrent le meilleur rapport entre le nombre de nœuds et la hauteur d'un arbre.

Voici les principales propriétés d'un arbre binaire complet :

• Le nombre maximum de nœuds est de 2 h+1 – 1.
• Le nombre minimum de nœuds est de 2 h .
• La hauteur minimale est log 2 (n+1) – 1.

4. Arbre binaire équilibré

Dans les arbres binaires équilibrés, la hauteur d'un arbre est log 2 du nombre total de nœuds. Supposons que la hauteur de l'arbre est h et que le nombre total de nœuds de l'arbre est n. L'équation pour calculer la hauteur est h = log(n). La différence maximale de hauteur entre un sous-arbre droit et un sous-arbre gauche doit être de « 1 ».

La différence peut avoir d'autres valeurs comme 0 et -1. Ces types d'arbres binaires sont également appelés arbres AVL.L'un des exemples bien connus d'arbres binaires équilibrés est l'arbre rouge-noir.

Vous pouvez implémenter le code suivant pour exécuter un arbre binaire équilibré.

Nœud de classe privée {

valeur int privée ;

Nœud privé à gauche ;

droit de Nœud privé ;

}

public boolean isBalanced(Node n) {

si (balancedtreeHeight(n) > -1)

retourner vrai ;

retourner faux ;

}

public int BalancedtreeHeight(Nœud n) {

si (n == nul)

renvoie 0 ;

int h1 = balancedtreeHeight(n.right);

int h2 = balancingtreeHeight(n.left);

si (h1 == -1 || h2 == -1)

retour -1 ;

si (Math.abs(h1 – h2) > 1)

retour -1 ;

si (h1 > h2)

retourner h1 + 1 ;

retourner h2 + 1 ;

}

Consultez nos programmes US - Data Science

5. Arbre binaire dégénéré

Un arbre binaire dégénéré est l'un destypes d'arbre de recherche binaire les moins fréquemment utilisés .C'est un arbre binaire dans lequel chaque nœud n'a qu'un seul enfant, c'est-à-dire un enfant gauche ou droit. Aucun nœud ne doit avoir à la fois des enfants gauche et droit.

Lisez nos articles populaires sur les États-Unis et la science des données

Conclusion

Il est essentiel de comprendrece qu'est un arbre binaire dans la structure de données si vous souhaitez l'utiliser pour diverses applications.L'implémentation de différentes fonctions sur les arbres binaires peut vous aider à organiser et à stocker efficacement les données.

L'étude de plusieurs types d'arbres binaires vous aide à effectuer des opérations plus efficacement dans la complexité temporelle. Les principes fondamentaux de la science des données, y comprisla structure de données en arbre binaire, vous aident à démarrer facilement votre voyage en science des données.Par la suite, vous pouvez travailler sur des projets de science des données avancés pour améliorer vos compétences et votre portefeuille.

Commencez votre parcours d'apprentissage automatique sur upGrad

Si vous souhaitez apprendre la science des données, vous pouvez suivre le programme de maîtrise ès sciences en science des données d'upGrad . Ce cours de 24 mois transmet des compétences telles que Python, le déploiement de modèles ML, le traitement BD à l'aide de Spark, l'analyse prédictive et les statistiques, et les modèles ML supervisés et non supervisés. Le cours convient aux managers ambitieux, aux diplômés du MBA, aux ingénieurs et aux professionnels de divers domaines.

Suivre ce cours vous aidera à travailler en tant qu'ingénieur de données, analyste de Big Data, ingénieur en apprentissage automatique et scientifique de données.