Arbre binaire dans la structure de données : propriétés, types, représentation et avantages

Parmi les différents types de structures de données, il y a des arbres binaires qui ont plus d'utilisations que la plupart des autres types. Leurs applications les plus notables incluent la programmation peer-to-peer, la recherche, la cryptographie, les routeurs réseau avec une bande passante plus élevée que les autres et les jeux vidéo 3D. Nous allons maintenant discuter en détail de ce que sont les arbres binaires en science des données, quels sont leurs types et comment sont-ils représentés.

Que sont les arbres binaires ?

Si vous avez déjà travaillé sur des arbres normaux ou si vous connaissez même leurs bases, vous saurez qu'il n'y a aucune restriction en ce qui concerne le nombre d'enfants que différents nœuds sont autorisés à avoir dans ces arbres. Les arbres binaires sont un peu différents dans ce sens. Chaque parent ou nœud dans les arbres binaires ne peut avoir qu'un maximum de deux enfants.

Tous les nœuds d'un arbre binaire ont trois composants principaux -

• un élément de données
• une bonne référence
• une référence gauche

Le nœud qui se trouve au sommet de l'arborescence est appelé nœud racine. Les nœuds parents sont ceux qui ont des enfants. Les nœuds enfants et les nœuds parents sont connectés les uns aux autres par des références. Les nœuds qui n'ont pas d'enfants sont appelés nœuds feuille.

Il est clairement évident que les nœuds des arbres binaires peuvent avoir un enfant, deux enfants ou aucun enfant du tout. Les arbres binaires ne sont pas des structures de données linéaires comme les files d'attente, les tableaux, les piles et les listes chaînées. Ce sont plutôt des structures de données hiérarchiques.

Découvrez : Idées de projets de science des données pour les débutants

Propriétés importantes des nœuds dans les arbres binaires

Une meilleure compréhension de ces propriétés vous aidera à tirer le meilleur parti de cette discussion sur les arbres binaires. La profondeur des différents nœuds est définie comme le nombre de nœuds qui existent sur le chemin qui relie la racine à un nœud particulier. C'est pourquoi la profondeur du nœud racine est 0. D'autre part, la hauteur des différents nœuds dans un arbre binaire est le nombre de nœuds qui se trouvent dans le chemin qui relie un nœud particulier au nœud racine. C'est pourquoi la hauteur des nœuds feuilles est de 0.

Comme vous pouvez le voir clairement, la profondeur d'un nœud est mesurée en partant du nœud racine, puis en descendant pour atteindre ce nœud. D'autre part, lorsqu'il s'agit de calculer la hauteur, nous commençons au nœud en question, puis nous nous dirigeons vers le nœud racine. Les deux fois, nous commençons à 0. Il y a des gens qui mesurent aussi la hauteur et la profondeur à partir de 1 et non à partir de 0, ce qui n'est pas faux et c'est juste ce que différentes personnes préfèrent.

Maintenant, la profondeur maximale d'un nœud est définie comme la profondeur d'un arbre binaire. De même, la hauteur maximale d'un nœud est définie comme la hauteur d'un arbre binaire. Ainsi, la hauteur et la profondeur d'un arbre binaire sont toujours les mêmes.

En savoir plus : Structures de données et algorithme en Python

Qu'est-ce qu'un arbre de recherche binaire ?

Un arbre de recherche binaire est le plus courant de tous les autres types d'arbres binaires. Il s'agit d'un arbre binaire spécialisé doté de propriétés différentes et plus utiles que toute autre forme d'arbre binaire. Qu'est-ce qu'un arbre de recherche binaire ou BST ? Comme son nom l'indique, un arbre de recherche binaire est utilisé pour rechercher des données dans l'arbre.

Un BST est livré avec des propriétés qui lui permettent de faciliter des recherches efficaces. Un BST est un arbre binaire dont la clé du nœud est plus petite et plus grande que les nœuds du sous-arbre droit et les nœuds du sous-arbre gauche respectivement.

Représentation des arbres binaires

1. Représentation liée

Les arbres binaires en représentation liée sont stockés dans la mémoire sous forme de listes liées. Ces listes ont des nœuds qui ne sont pas stockés dans des emplacements de mémoire adjacents ou voisins et sont liés les uns aux autres par la relation parent-enfant associée aux arbres.

Dans cette représentation, chaque nœud a trois parties différentes -

• pointeur qui pointe vers le nœud droit,
• pointeur qui pointe vers le nœud gauche,
• élément de données.

C'est la représentation la plus courante. Tous les arbres binaires consistent en un pointeur racine qui pointe dans la direction du nœud racine. Lorsque vous voyez un nœud racine pointant vers null ou 0, vous devez savoir que vous avez affaire à un arbre binaire vide. Les pointeurs droit et gauche stockent l'adresse des enfants droit et gauche de l'arbre.

2. Représentation séquentielle

Bien qu'elle soit plus simple que la représentation liée, son inefficacité en fait une représentation d'arbre binaire moins préférée des deux. L'inefficacité réside dans la quantité d'espace nécessaire pour le stockage des différents éléments de l'arbre. La représentation séquentielle utilise un tableau pour le stockage des éléments de l'arbre.

Le nombre de nœuds d'un arbre binaire définit la taille du tableau utilisé. Le nœud racine de l'arbre binaire se trouve au premier index du tableau. L'index auquel un nœud particulier est stocké définira les index auxquels les enfants droit et gauche du nœud seront stockés. Un arbre vide a null ou 0 comme premier index.

Types d'arbres binaires

1. Arbres binaires complets : Les arbres binaires complets sont les arbres binaires dont les nœuds ont soit deux enfants, soit aucun. En d'autres termes, un arbre binaire devient un arbre binaire complet lorsque, à part les feuilles, tous ses autres nœuds ont deux enfants.
2. Arbres binaires complets : Les arbres binaires complets sont ceux dont tous les différents niveaux sont complètement remplis. La seule exception à cela pourrait être leur dernier niveau, dont les touches sont majoritairement à gauche. Un tas binaire est souvent pris comme exemple d'arbre binaire complet.
3. Arbres binaires parfaits : Les arbres binaires parfaits sont des arbres binaires dont les feuilles sont présentes au même niveau et dont les nœuds internes portent deux enfants. Un exemple courant d'arbre binaire parfait est un arbre généalogique ancestral.
4. Arbres binaires dégénérés pathologiques : Les arbres dégénérés sont les arbres binaires dont les nœuds internes ont un enfant. Leurs niveaux de performance sont similaires aux listes chaînées. En savoir plus sur les types d'arbre binaire.

Lire : Les six structures de données les plus couramment utilisées dans R

Avantages des arbres binaires

1. Une façon idéale d'aller avec la méthode hiérarchique de stockage des données
2. Refléter les relations structurelles qui existent dans l'ensemble de données donné
3. Rendre l'insertion et la suppression plus rapides que les listes liées et les tableaux
4. Une manière flexible de conserver et de déplacer des données
5. Sont utilisés pour stocker autant de nœuds que possible
6. Sont plus rapides que les listes chaînées et plus lents que les tableaux lorsqu'il s'agit d'accéder aux éléments

Conclusion

Dans ce blog, nous avons discuté de ce que sont les arbres binaires dans les structures de données ainsi que de leurs types, de leurs représentations et de leurs avantages. Les deux principales utilisations des arbres sont la recherche et le stockage de données, et font donc partie intégrante de l'étude de la science des données et de ses domaines connexes.

Si vous êtes curieux d'en savoir plus sur les arbres binaires dans les structures de données, la science des données, consultez le programme exécutif PG de IIIT-B & upGrad en science des données qui est créé pour les professionnels en activité et propose plus de 10 études de cas et projets, des ateliers pratiques pratiques, mentorat avec des experts de l'industrie, 1-on-1 avec des mentors de l'industrie, plus de 400 heures d'apprentissage et d'aide à l'emploi avec les meilleures entreprises.