4 types d'arbres dans la structure de données expliqués : propriétés et applications

Qu'est-ce qu'un arbre dans la structure de données ?

Un arbre est un type de structure de données représentant des données hiérarchiques. Il a une structure non linéaire constituée de nœuds reliés par des arêtes. Parmi les autres types de structures de données qui effectuent des opérations dans une structure de données linéaire, la complexité augmente avec une augmentation de la taille des données. Cependant, la structure de données arborescente permet un accès plus rapide aux données qui sont non linéaires. Disponibilité des différents types de structures de données et des algorithmes qui leur sont associés, l'exécution des tâches est devenue un moyen simple et efficace.

Quelques terminologies associées aux arbres dans la structure de données sont :

• Nœud : le nœud est une entité dans une structure de données arborescente qui contient une clé ou une valeur et des pointeurs vers ses nœuds enfants.
• Nœud enfant : Un nœud enfant est le descendant de n'importe quel nœud.
• Nœuds feuilles : les nœuds qui n'ont pas de nœuds enfants et qui sont le nœud le plus bas dans un arbre. Ils sont aussi appelés nœuds externes.
• Racine : C'est le point le plus haut d'un arbre.
• Nœud interne : Le nœud ayant au moins un nœud enfant.
• Bord : un bord fait référence à la connexion entre deux nœuds quelconques dans un arbre.
• Hauteur d'un nœud : Nombre d'arêtes du nœud à la feuille la plus profonde.
• Profondeur d'un nœud : Nombre d'arêtes de la racine au nœud.
• Hauteur d'un arbre : Hauteur du nœud racine.
• Degré d'un nœud : nombre total de branches vers ce nœud.
• Forêt : Une collection d'arbres disjoints.

Types d'arbre

1. Arbre binaire

L' arbre binaire est un type de structure de données arborescente où chaque nœud parent a un maximum de deux nœuds enfants. Comme son nom l'indique, binaire signifie deux, par conséquent, chaque nœud peut avoir 0, 1 ou 2 nœuds. Une structure de données arborescente binaire est illustrée à la figure 1. Le nœud 1 de l'arborescence contient deux pointeurs, un pour chaque nœud enfant. Le nœud 2 a à nouveau deux pointeurs chacun pour les deux nœuds enfants. Alors que les nœuds 3, 5 et 6 sont des nœuds feuilles et ont donc des pointeurs nuls sur les parties gauche et droite.

Figure 1 : Une représentation d'un arbre binaire ( https://www.javatpoint.com/binary-tree ).

Propriétés d'un arbre binaire

• Le nombre maximum de nœuds à chaque niveau de I est 2 i .
• La hauteur de l'arbre de la figure 1 est de 3, ce qui signifie que le nombre maximum de nœuds sera (1+2+4+8) =15.

• A la hauteur h, le nombre maximum de nœuds possible est (20 + 21 + 22+….2h) = 2h+1 -1.

• A la hauteur h, le nombre minimum de nœuds possibles est égal à h+1.

• Un nombre minimum de nœuds représentera un arbre avec une hauteur maximale et vice versa.

Même les arbres binaires peuvent être divisés en les types d'arbres suivants :

• Arbre binaire complet : il s'agit d'un type spécial d'arbre binaire. Dans cette structure de données arborescente, chaque nœud parent ou un nœud interne a soit deux enfants, soit aucun nœud enfant.
• Arbre binaire parfait : Dans ce type de structure de données arborescente , chaque nœud interne a exactement deux nœuds enfants et tous les nœuds feuilles sont au même niveau.
• Arbre binaire complet : Il ressemble à celui de l'arbre binaire complet avec quelques différences.
• Chaque niveau est complètement rempli.
• Les nœuds feuilles penchent vers la gauche de l'arbre.
• Il n'est pas nécessaire que le dernier nœud feuille ait le bon frère, c'est-à-dire qu'un arbre binaire complet n'a pas besoin d'être un arbre binaire complet.
• Arbre dégénéré ou pathologique : ces arbres ont un seul enfant à gauche ou à droite du nœud parent.
• Arbre binaire asymétrique: C'est un arbre pathologique ou dégénéré où l'arbre est dominé soit par les nœuds gauches, soit par les nœuds droits. Par conséquent, il existe deux types d'arbres binaires asymétriques, à savoir l'arbre binaire asymétrique à gauche ou l'arbre binaire asymétrique à droite.
• Arbre binaire équilibré : la différence entre la hauteur des sous-arbres gauche et droit pour chaque nœud est de 0 ou 1.

2. Arbre de recherche binaire

Ces arborescences sont non linéaires et un nœud est connecté à plusieurs nœuds. Le nœud peut être connecté à au plus deux nœuds enfants. C'est ce qu'on appelle un arbre de recherche binaire parce que :

• Chaque nœud a un maximum de deux nœuds enfants.
• Il peut être utilisé pour rechercher un élément en temps 0 (log (n)) et donc connu sous le nom d'arbre de recherche.

Figure : Un exemple d'arborescence de recherche binaire ( https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm )

Les propriétés d'un arbre de recherche binaire sont :

• La valeur dans tous les nœuds d'un sous-arbre gauche doit être inférieure à la valeur dans le nœud racine.
• La valeur dans tous les nœuds d'un sous-arbre droit doit être supérieure à la valeur dans le nœud racine.

3. Arbre AVL

Les arbres AVL sont les types ou variantes d'un arbre binaire. Il se compose de propriétés à la fois du binaire et d'un arbre de recherche binaire. Inventés par Adelson Velsky Lindas, ces arbres sont auto-équilibrés, ce qui signifie que la hauteur du sous-arbre gauche et du sous-arbre droit est équilibrée. Cet équilibre est mesuré en termes de facteur d'équilibrage.

Facteur d'équilibrage :

• C'est la différence entre le sous-arbre gauche et le sous-arbre droit.
• La valeur d'un facteur d'équilibrage doit être 0, -1 ou 1. Par conséquent, chaque nœud d'un arbre AVL doit être constitué d'une valeur de facteur d'équilibrage, c'est-à-dire 0, -1 ou 1.
• Facteur d'équilibre = (Hauteur du sous-arbre gauche - Hauteur du sous-arbre droit)
• Un arbre AVL est dit équilibré si le facteur d'équilibre de chaque nœud est compris entre -1 et 1.

Les valeurs des nœuds autres que -1, à 1 dans un arbre AVL représenteront un arbre déséquilibré qui doit être équilibré.

• Si un nœud a un facteur d'équilibre de 1, cela signifie que le sous-arbre de gauche est supérieur d'un niveau au sous-arbre de droite.
• Si un nœud a un facteur d'équilibre de 0, cela signifie que la hauteur du sous-arbre gauche et du sous-arbre droit est égale.
• Si un nœud a un facteur d'équilibre de -1, cela signifie que le sous-arbre droit est d'un niveau supérieur au sous-arbre gauche ou que le sous-arbre gauche est d'un niveau inférieur au sous-arbre droit.

4. Arbre B

B Tree est une forme plus généralisée d'arbre de recherche binaire. Il est également connu sous le nom d'arbre m way équilibré en hauteur, où m est l'ordre de l'arbre. Chaque nœud de l'arborescence peut avoir plus d'une clé et plus de deux nœuds enfants. Dans le cas d'un arbre binaire, les nœuds feuilles peuvent ne pas être au même niveau. Cependant, dans le cas d'un arbre B, tous les nœuds feuilles doivent être au même niveau.

Propriétés d'un B-tree :

• Les clés sont stockées dans l'ordre croissant pour chaque nœud x.
• Une valeur booléenne « x.leaf » existe dans chaque nœud, ce qui est vrai si x est une feuille.
• Les nœuds internes doivent avoir au plus "n-1" clés, où n est l'ordre de l'arbre. Il devrait également avoir un pointeur pour chaque enfant.
• Tous les nœuds auront au plus n enfants et au moins n/2 enfants, sauf le nœud racine.
• Les nœuds feuilles de l'arbre ont la même profondeur.
• Le nœud racine aura au minimum 1 clé et au moins deux enfants.
• Si n ≥ 1, alors pour tout arbre B à n clés de hauteur h et de degré minimum t ≥ 2, h ≥ logt (n+1)/2.

Applications

• L'arbre de recherche binaire peut être appliqué pour rechercher un élément dans un ensemble d'éléments.
• Les arbres de tas sont utilisés pour le tri de tas.
• Les routeurs modernes utilisent un type d'arbre appelé Essais pour stocker les informations de routage.
• Les B-Trees et les T-Trees sont principalement utilisés par les bases de données populaires pour stocker leurs données.
• Un arbre de syntaxe est utilisé par les compilateurs pour valider la syntaxe de chaque programme écrit.

Conclusion

Les structures de données fournissent une manière organisée de stocker les données pour une gestion facile et une manipulation efficace. Différents types de structures de données existent pour différents types de données. En fonction du type de données à stocker, il est choisi par l'utilisateur.

Les arbres sont des types de telles structures de données où le type hiérarchique de données peut être stocké. Les données sont stockées dans les nœuds qui stockent parfois la référence pour d'autres nœuds appelés nœuds enfants.

En fonction du nombre de nœuds enfants, les arbres peuvent être classés en différents types, comme mentionné dans l'article. En fonction de l'agencement des nœuds dans les types d'arborescence, chaque structure arborescente a des propriétés associées. Avec les différents types d'opérations que peuvent effectuer les différentes classes d'arbres, ce type de structure de données a trouvé des applications dans les algorithmes de tri et le stockage de données.

Un programme exécutif PG en développement de logiciels - Spécialisation en développement Full Stack, organisé par upGrad & IIIT-Bangalore, peut vous aider à améliorer votre profil et à obtenir de meilleures opportunités d'emploi en tant que programmeur.