5 types d'arbres binaires expliqués [avec illustrations] | blog upGrad (2024)

En informatique, diversstructures de donnéesaider à organiser les données sous différentes formes. Parmi eux, les arbres sont des structures de données abstraites largement utilisées qui simulent une structure arborescente hiérarchique. Un arbre a généralement une valeur racine et des sous-arbres formés par les nœuds enfants de ses nœuds parents. Les arbres sont des structures de données non linéaires.

Une structure de données arborescente générale n’a aucune limitation quant au nombre de nœuds enfants qu’elle peut contenir. Or, ce n’est pas le cas d’un arbre binaire. Cet article découvrira une structure de données arborescente spécifique – arbre binaire ettypes d'arbre binaire.

Consultez notrecours gratuit node jschez upGrad

Qu’est-ce que la structure de données de l’arbre binaire ?

UNarbre binaireest une structure de données non linéaire de type arborescent avec un maximum de deux enfants pour chaque parent. Chaque nœud dans unarbre binairea une référence gauche et droite avec l'élément de données. Le nœud situé au sommet de la hiérarchie d’un arbre est appelé nœud racine. Les nœuds qui contiennent d'autres sous-nœuds sont les nœuds parents.

Un nœud parent a deux nœuds enfants : l’enfant gauche et l’enfant droit. Le hachage, le routage des données pour le trafic réseau, la compression des données, la préparation de tas binaires et les arbres de recherche binaires sont quelques-unes des applications qui utilisent un arbre binaire.

Terminologies associées aux arbres binaires et aux types d'arbres binaires

• Nœud:Il représente un point de terminaison dans un arbre.
• Racine:Le nœud le plus élevé d’un arbre.
• Parent:Chaque nœud (à l'exception de la racine) dans une arborescence qui possède au moins un sous-nœud qui lui est propre est appelé nœud parent.
• Enfant:Un nœud qui provient directement d'un nœud parent en s'éloignant de la racine est le nœud enfant.
• Noeud feuille:Ce sont des nœuds externes. Ce sont les nœuds qui n'ont pas d'enfant.
• Nœud interne :Comme son nom l’indique, ce sont des nœuds internes avec au moins un enfant.
• Profondeur d'un arbre :Le nombre d’arêtes depuis le nœud de l’arbre jusqu’à la racine est.
• Hauteur d'un arbre :C'est le nombre d'arêtes depuis le nœud jusqu'à la feuille la plus profonde. La hauteur de l’arbre est également considérée comme la hauteur des racines.

Nos apprenants lisent aussi:Cours Excel en ligne gratuit!

Comme vous êtes maintenant familier avec les terminologies associées à l'arbre binaire et aux types d'arbre binaire, il est temps de comprendre lecomposants de l'arbre binaire. Consultez notrecours de science des donnéespour en savoir plus sur la structure et les composants binaires.

Nos apprenants lisent également :Structures de données et algorithmes gratuits!

Comprendre les propriétés deArbre binaire ou qu'est-ce que l'arbre binaire ?

À chaque niveau, le nombre maximum autorisé de nœuds est de 2i.

La hauteur d'unarbre binaireest défini comme le chemin le plus long émanant d’un nœud racine jusqu’au nœud feuille de l’arbre.

Qu'est-ce que l'arbre binaire– Plus que leDéfinition de l'arbre binaire

Dis unarbre binaireplacé à une hauteur égale à 3. Dans ce cas, le plus grand nombre de nœuds pour cette hauteur 3 est égal à 15, soit (1+2+4+8) = 15. En termes simples, le nombre maximum de nœuds possible pour cette hauteur h est (20 + 21 + 22+….2h) = 2h+1 -1.

Or, pour le nombre de nœuds minimum possible à cette hauteur h, il est égal à h+1.

S'il y a un nombre minimum de nœuds, alors la hauteur d'un arbre binaire serait maximale. En revanche, lorsqu'il y a un nombre de nœuds à son maximum, alors la hauteur de l'arbre binaire m sera minimale. S’il existe environ « n » nœuds numériques dans un arbre binaire, voici un calcul pour clarifier ledéfinition de l'arbre binaire.

La hauteur minimale de l’arbre est calculée comme suit :

n = 2h+1 -1

n+1 = 2h+1

Je prends le journal des deux côtés maintenant,

log2(n+1) = log2(2h+1)

log2(n+1) = h+1

h = log2(n+1) – 1

La hauteur la plus élevée sera calculée comme suit :

n = h+1

h = n-1

Composants de l'arbre binaire

Il ya troiscomposants de l'arbre binaire. Chaquearbre binaireLe nœud est associé à ces trois composants. Cela devient un concept essentiel pour les programmeurs de comprendre ces troisComposants de l'arbre binaire :

1. Élément de données
2. Pointeur vers le sous-arbre gauche
3. Pointeur vers le sous-arbre droit

Source

Ces troiscomposants de l'arbre binairereprésente un nœud. Les données résident au milieu. Le pointeur gauche pointe vers le nœud enfant, formant le sous-arbre gauche. Le pointeur droit pointe vers le nœud enfant à sa droite, créant ainsi le sous-arbre droit.

Lire:

Découvrez nos cours populaires de science des données

Définition de l'arbre binaire: Une analyse approfondie

Dans le cas où il existe un nombre n de nœuds dans un arbre binaire, la hauteur est donnée par log n logn. Cela est dû à la simple raison que pour tout nœud donné dans n’importe quel arbre binaire, il y aura au maximum deux nœuds enfants. Cela nous amène à une explicationdéfinir un arbre binaire: pour chaque niveau ou chaque hauteur de tout arbre binaire, le numéro de nœud doit être le même qu'environ la moitié des numéros de nœuds présents au niveau suivant.

Sous forme de réponse àdéfinir un arbre binaire, le nombre de nœuds à chaque niveau est proche du double du nombre de nœuds à son niveau précédent. Nous espérons que cela clarifie la réponse àqu'est-ce que l'arbre binaire!

Cela signifie que lorsqu'un arbre binaire a une hauteur h, le nombre de nœuds pourdéfinir un arbre binaireest n = (2 ^ 0) + (2 ^ 1) + (2 ^ 2) + (2 ^ 3) + ….. + (2 ^ (h-1))(20)+(21)+(22 )+(23)+…..+(2(h−1))

Du point d’induction mathématique pourqu'est-ce qu'un arbre binaire, c'est ce que nous savons-

(2 ^ 0) + (2 ^ 1) + (2 ^ 2) + (2 ^ 3) + ….. + (2 ^ {(h-1)}) = (2 ^ h)-1(20) +(21)+(22)+(23)+…..+(2(h−1))=(2h)−1

Ainsi,

(2 ^ h)-1 = n => 2 ^ h = n + 1 => h = log2(n+1)(2h)−1=n=>2h=n+1=>h=log2(n+ 1)

Par conséquent, la hauteur minimale d’un arbre binaire est à peu près égale à log(n). Cela vous aide à mieux comprendrequ'est-ce qu'un arbre binaire.

De plus, le nombre minimum de nœuds possibles à la hauteur h de l'arbre binaire peut être connu par h+1.

Si l'arbre binaire est livré avec un numéro L pour les nœuds feuilles, la hauteur est représentée par L + 1.

Types d'arbres binaires

Il y a plusieurstypes d'arbres binaires, et chacun d'euxtypes d'arbres binairespossède des caractéristiques uniques. Voici chacun destypes d'arbres binairesen détail:

1. Arbre binaire complet

Il s’agit d’un type particulier d’arbre binaire qui a soit zéro enfant, soit deux enfants. Cela signifie que tous les nœuds de cet arbre binaire doivent avoir deux nœuds enfants de leur nœud parent ou que le nœud parent est lui-même le nœud feuille ou le nœud externe.

En d’autres termes, un arbre binaire complet est un arbre binaire unique dans lequel chaque nœud, à l’exception du nœud externe, a deux enfants. Lorsqu’il contient un seul enfant, un tel arbre binaire ne sera pas un arbre binaire complet.Ici, la quantité de nœuds feuilles est égale au nombre de nœuds internes plus un. L'équation est commeL=I+1, où L est le nombre de nœuds feuilles et I est le nombre de nœuds internes.

Nos apprenants lisent aussi:Cours gratuits Python!

Voici la structure d’un arbre binaire complet :

Principales compétences en science des données à acquérir

2. Arbre binaire complet

Un arbre binaire complet est un autre type spécifique d'arbre binaire où tous les niveaux de l'arbre sont entièrement remplis de nœuds, à l'exception du niveau le plus bas de l'arbre. De plus, au dernier ou au niveau le plus bas de cet arbre binaire, chaque nœud devrait éventuellement résider sur le côté gauche. Voici la structure d’un arbre binaire complet :

Webinaire exclusif sur la science des données d'upGrad pour vous -

Transformation et opportunités en matière d'analyse et d'informations

3. Arbre binaire parfait

Un arbre binaire est dit « parfait » si tous les nœuds internes ont strictement deux enfants et si chaque nœud externe ou feuille est au même niveau ou à la même profondeur dans un arbre. Un parfaitarbre binaireayant une hauteur « h » a 2h – 1 nœud. Voici la structure d’un arbre binaire parfait :

4. Arbre binaire équilibré

Un arbre binaire est dit « équilibré » si la hauteur de l’arbre est O(logN), où « N » est le nombre de nœuds. Dans un arbre binaire équilibré, la hauteur des sous-arbres gauche et droit de chaque nœud doit varier d'au plus un. Un arbre AVL et un arbre rouge-noir sont quelques exemples courants de structure de données pouvant générer un arbre de recherche binaire équilibré. Voici un exemple d’arbre binaire équilibré :

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

Un arbre binaire est dit arbre binaire dégénéré ou arbre binaire pathologique si chaque nœud interne n’a qu’un seul enfant. De tels arbres sont similaires à une liste chaînée en termes de performances. Voici un exemple d'arbre binaire dégénéré :

Avantages d'un arbre binaire

• L'opération de recherche dans un arbre binaire est plus rapide que dans d'autres arbres
• Seulement deux parcours suffisent pour fournir les éléments dans l'ordre trié
• Il est facile de récupérer les éléments maximum et minimum
• Le parcours graphique utilise également des arbres binaires
• La conversion de différentes expressions de suffixe et de préfixe est possible à l'aide d'arbres binaires

Lire aussi :

Conclusion

L'arbre binaire est l'un des arbres les plus utilisés dans la structure de données. Chacun detypes d'arbres binairesa ses caractéristiques uniques. Ces structures de données ont des exigences spécifiques en informatique appliquée. Nous espérons que cet article sur les types d’arbres binaires vous a été utile. upGrad propose divers cours sur la science des données, l'apprentissage automatique, le big data, etc.

Lisez nos articles populaires sur la science des données

Si vous êtes curieux d'en savoir plus sur la science des données, consultez IIIT-B & upGrad'sProgramme exécutif PG en science des donnéesqui est créé pour les professionnels en activité et propose plus de 10 études de cas et projets, des ateliers pratiques, un mentorat avec des experts de l'industrie, des rencontres individuelles avec des mentors de l'industrie, plus de 400 heures d'apprentissage et une aide à l'emploi auprès des meilleures entreprises.