Dans ce didacticiel, vous découvrirez la structure des données arborescentes. En outre, vous découvrirez les différents types d'arbres et les terminologies utilisées dans tree.
Un arbre est une structure de données hiérarchique non linéaire composée de nœuds connectés par des arêtes.
Un arbre
Pourquoi une arborescence de données?
Les autres structures de données telles que les tableaux, la liste liée, la pile et la file d'attente sont des structures de données linéaires qui stockent les données de manière séquentielle. Afin d'effectuer toute opération dans une structure de données linéaire, la complexité temporelle augmente avec l'augmentation de la taille des données. Mais, ce n'est pas acceptable dans le monde informatique d'aujourd'hui.
Différentes structures de données arborescentes permettent un accès plus rapide et plus facile aux données car il s'agit d'une structure de données non linéaire.
Terminologies de l'arborescence
Nœud
Un nœud est une entité qui contient une clé ou une valeur et des pointeurs vers ses nœuds enfants.
Les derniers nœuds de chaque chemin sont appelés nœuds feuilles ou nœuds externes qui ne contiennent pas de lien / pointeur vers les nœuds enfants.
Le nœud ayant au moins un nœud enfant est appelé nœud interne .
Bord
C'est le lien entre deux nœuds.
Nœuds et arêtes d'un arbre
Racine
C'est le nœud le plus haut d'un arbre.
Hauteur d'un nœud
La hauteur d'un nœud est le nombre d'arêtes du nœud à la feuille la plus profonde (c'est-à-dire le chemin le plus long du nœud à un nœud feuille).
Profondeur d'un nœud
La profondeur d'un nœud est le nombre d'arêtes de la racine au nœud.
Hauteur d'un arbre
La hauteur d'un arbre est la hauteur du nœud racine ou la profondeur du nœud le plus profond.
Hauteur et profondeur de chaque nœud dans un arbre
Degré d'un nœud
Le degré d'un nœud est le nombre total de branches de ce nœud.
Forêt
Une collection d'arbres disjoints s'appelle une forêt.
Créer une forêt à partir d'un arbre
Vous pouvez créer une forêt en coupant la racine d'un arbre.
Types d'arbres
- Arbre binaire
- Arbre de recherche binaire
- Arborescence AVL
- Arbre B
Traversée d'arbres
Pour effectuer toute opération sur une arborescence, vous devez atteindre le nœud spécifique. L'algorithme de traversée d'arbre aide à visiter un nœud requis dans l'arborescence.
Pour en savoir plus, veuillez visiter la traversée des arbres.
Applications d'arbre
- Les arbres de recherche binaires (BST) sont utilisés pour vérifier rapidement si un élément est présent dans un ensemble ou non.
- Heap est une sorte d'arbre utilisé pour le tri de tas.
- Une version modifiée d'une arborescence appelée Tries est utilisée dans les routeurs modernes pour stocker les informations de routage.
- Les bases de données les plus populaires utilisent des B-Trees et T-Trees, qui sont des variantes de l'arborescence que nous avons apprise ci-dessus pour stocker leurs données
- Les compilateurs utilisent une arborescence de syntaxe pour valider la syntaxe de chaque programme que vous écrivez.
