Introduction aux arbres dans la structure des données
Avant de comprendre les types d'arbres dans la structure de données, nous allons d'abord étudier les arbres dans la structure de données. L'arbre dans le domaine informatique est également appelé arbre du monde réel, mais la différence entre le monde réel et l'arbre de champ informatique est qu'il est visualisé à l'envers et enraciné au-dessus et se ramifie de la racine aux feuilles des arbres. Parmi diverses applications du monde réel, la structure de données arborescente est utilisée car elle peut démontrer les relations entre différents nœuds avec la hiérarchie parent-enfant. Il est également appelé une structure de données hiérarchique à cause de cela. Il est le plus populaire pour simplifier et accélérer la recherche et le tri. Il est considéré comme l'une des structures de données les plus solides et les plus avancées. Un arbre est une représentation de la structure de données non linéaire. Un arbre peut être affiché à l'aide de différents types de données définis par l'utilisateur ou primitifs. Nous pouvons utiliser des tableaux, des listes de classes connectées ou d'autres types de structures de données pour implémenter l'arborescence. Il s'agit d'un groupe de nœuds interdépendants. Des nœuds sont attachés aux bords pour illustrer la relation.
Relations dans un arbre: dans le diagramme ci-dessus, P est la racine de l'arbre également P est parent de Q, R et S. Q est l'enfant de P. Par conséquent, Q, R et S sont frères et sœurs. Alors que P est le grand-parent de A, B, C, D et E.
Que sont les arbres?
Un arbre est une structure de données hiérarchique qui stocke naturellement les informations de manière hiérarchique. La structure de données Tree est l'une des plus efficaces et des plus matures. Les nœuds reliés par les bords sont représentés.
Propriétés de l'arbre: chaque arbre a un nœud racine spécifique. Chaque nœud d'arbre peut être traversé par un nœud racine. Il est appelé racine, car l'arbre était la seule racine. Chaque enfant n'a qu'un seul parent, mais le parent peut avoir plusieurs enfants.
Types d'arbres dans la structure de données
Voici les types d'arbres dans une structure de données:
1. Arbre général
Si aucune contrainte n'est placée sur la hiérarchie de l'arbre, un arbre est appelé arbre général. Chaque nœud peut avoir un nombre infini d'enfants dans l'arbre général. L'arbre est le super-ensemble de tous les autres arbres.
2. Arbre binaire
L'arbre binaire est le type d'arbre dans lequel la plupart des deux enfants peuvent être trouvés pour chaque parent. Les enfants sont connus comme les enfants de gauche et de droite. C'est plus populaire que la plupart des autres arbres. Lorsque certaines contraintes et caractéristiques sont appliquées dans un arbre binaire, un certain nombre d'autres telles que l'arbre AVL, BST (arbre de recherche binaire), l'arbre RBT, etc. sont également utilisées. Lorsque nous irons de l'avant, nous expliquerons tous ces styles en détail.
3. Arbre de recherche binaire
Binary Search Tree (BST) est une extension d'arbre binaire avec plusieurs restrictions facultatives. La valeur enfant gauche d'un nœud doit dans BST être inférieure ou égale à la valeur parent et la valeur enfant droite doit toujours être supérieure ou égale à la valeur parent. Cette propriété d'arbre de recherche binaire la rend idéale pour les opérations de recherche car nous pouvons déterminer avec précision à chaque nœud si la valeur est dans le sous-arbre gauche ou droit. C'est pourquoi l'arbre de recherche est nommé.
4. Arbre AVL
L'arbre AVL est un arbre de recherche binaire auto-équilibré. Au nom des inventeurs Adelson-Velshi et Landis, le nom AVL est donné. Ce fut le premier arbre à s'équilibrer dynamiquement. Un facteur d'équilibrage est alloué pour chaque nœud dans l'arborescence AVL, selon que l'arborescence est équilibrée ou non. La hauteur des nœuds enfants est au maximum de 1. AVL cep. Dans l'arborescence AVL, le facteur d'équilibre correct est 1, 0 et -1. Si l'arbre a un nouveau nœud, il sera alors tourné pour s'assurer que l'arbre est équilibré. Il sera ensuite tourné. Les opérations courantes telles que l'affichage, l'insertion et la suppression prennent du temps O (log n) dans l'arborescence AVL. Il est principalement appliqué lors de l'utilisation des opérations de recherche.
5. Arbre rouge-noir
Un autre type d'arbre à équilibrage automatique est rouge-noir. Le nom rouge-noir est donné parce que l'arbre rouge-noir a du rouge ou du noir peint sur chaque nœud en fonction des propriétés de l'arbre rouge-noir. Il maintient l'équilibre de la forêt. Même si cet arbre n'est pas un arbre entièrement équilibré, l'opération de recherche ne prend que O (log n). Lorsque les nouveaux nœuds sont ajoutés dans l'arbre rouge-noir, les nœuds seront à nouveau pivotés pour conserver les propriétés de l'arbre rouge-noir.
6. Arbre N-aire
Le nombre maximal d'enfants dans ce type d'arbre pouvant avoir un nœud est N. Un arbre binaire est un arbre de deux ans, comme au plus 2 enfants dans chaque nœud d'arbre binaire. Un arbre N-aire complet est un arbre où les enfants d'un nœud valent 0 ou N.
Avantages de l'arbre
Nous allons maintenant comprendre les avantages de Tree:
- L'arbre se reflète dans les connexions structurelles des données.
- L'arbre est utilisé pour la hiérarchie.
- Il offre une procédure de recherche et d'insertion efficace.
- Les arbres sont flexibles. Cela permet de déplacer les sous-arbres avec un minimum d'effort.
Conclusion - Types d'arbres dans la structure des données
Donc, ici dans cet article, nous avons vu ce qu'est la structure arborescente, quels sont les différents types d'arbres dans la structure des données et ses avantages. J'espère que vous avez une idée de certains des arbres communs dans la structure des données.
Articles recommandés
Ceci est un guide sur les types d'arbres dans la structure de données. Nous discutons ici de ce que sont les arbres, 6 types d'arbres dans la structure de données, avec des avantages. Vous pouvez également consulter nos autres articles connexes pour en savoir plus -
- Pipeline de données AWS
- Oracle Data Warehousing
- Base de données multidimensionnelle
- Questions d'entretiens chez Data Structure Java