Une structure de données non linéaire consiste en un ensemble d'éléments distribués sur un plan, ce qui signifie qu'il n'y a pas de séquence entre les éléments telle qu'elle existe dans une structure de données linéaire.
Tableau de comparaison
| Base de comparaison | Arbre | Graphique |
|---|---|---|
| Chemin | Un seul entre deux sommets. | Plus d'un chemin est autorisé. |
| Noeud principal | Il a exactement un nœud racine. | Le graphique n'a pas de nœud racine. |
| Boucles | Aucune boucle n'est autorisée. | Le graphique peut avoir des boucles. |
| Complexité | Moins complexe | Plus complexe comparativement |
| Techniques de traversée | Pré-commande, en commande et post-commande. | Recherche en profondeur et recherche en profondeur. |
| Nombre d'arêtes | n-1 (où n est le nombre de nœuds) | Non défini |
| Type de modèle | Hiérarchique | Réseau |
Définition de l'arbre
Un arbre est une collection finie d'éléments de données, généralement appelés nœuds. Comme il est mentionné ci-dessus, une arborescence est une structure de données non linéaire qui organise les éléments de données dans un ordre trié. Il est utilisé pour afficher une structure hiérarchique entre les différents éléments de données et pour organiser les données en branches reliant les informations. L'ajout d'un nouveau bord dans un arbre entraîne la formation de la boucle ou du circuit.
Il existe plusieurs types d’arbres, tels que l’arbre binaire, l’arbre de recherche binaire, l’arbre AVL, l’arbre binaire fileté, l’arbre B, etc. La compression des données, le stockage de fichiers, la manipulation de l’expression arithmétique et les arbres de jeu sont quelques-unes des applications de l’arbre Structure de données.
Propriétés de l'arbre:
- Il y a un nœud désigné en haut de l’arbre appelé racine de l’arbre.
- Les éléments de données restants sont divisés en sous-ensembles disjoints appelés sous-arbres.
- L'arbre est élargi en hauteur vers le bas.
- Un arbre doit être connecté, ce qui signifie qu’il doit exister un chemin d’une racine à tous les autres nœuds.
- Il ne contient aucune boucle.
- Un arbre a n-1 arêtes.
Il existe divers termes associés aux arbres tels que nœud terminal, arête, niveau, degré, profondeur, forêt, etc. Parmi ces termes, certains d'entre eux sont décrits ci-dessous.
- Edge - Une ligne qui connecte deux nœuds.
- Niveau - Un arbre est partitionné en niveaux de telle sorte que le nœud racine soit au niveau 0. Ensuite, ses enfants immédiats sont au niveau 1 et ses enfants immédiats sont au niveau 2 et ainsi de suite jusqu'au nœud terminal ou terminal.
- Degré - Il s'agit du nombre de sous-arbres d'un nœud dans un arbre donné.
- Profondeur - Il s'agit du niveau maximal de tout nœud dans un arbre donné, également appelé hauteur .
- Noeud terminal - Le noeud de niveau le plus élevé est le noeud terminal, tandis que les autres noeuds, à l'exception des noeuds terminal et racine, sont appelés noeuds non terminaux.
Définition du graphique
Un graphique est également une structure de données mathématique non linéaire pouvant représenter divers types de structures physiques. Il se compose d'un groupe de sommets (ou nœuds) et d'un ensemble d'arêtes reliant les deux sommets. Les sommets du graphique sont représentés sous forme de points ou de cercles et les arêtes sous forme d'arcs ou de segments. Une arête est représentée par E (v, w) où v et w sont les paires de sommets. La suppression d'une arête d'un circuit ou d'un graphe connecté crée un sous-graphe qui est une arborescence.
Les graphiques sont classés en différentes catégories telles que dirigé, non dirigé, connecté, non connecté, simple et multi-graphique. Réseau informatique, système de transport, graphe de réseau social, circuits électriques et planification de projet sont quelques-unes des applications de la structure de données graphiques. Il est également utilisé dans les techniques de gestion nommées PERT ( technique d’ évaluation et d’évaluation de programme) et CPM (méthode du chemin critique) dans lesquelles la structure du graphe est analysée.
Propriétés d'un graphe:
- Un sommet dans un graphique peut être connecté à un nombre quelconque de sommets à l'aide d'arêtes.
- Un bord peut être dirigé ou dirigé.
- Un bord peut être pondéré.
Dans le graphique, nous utilisons également divers termes tels que sommets adjacents, trajet, cycle, degré, graphe connecté, graphe complet, graphe pondéré, etc. Comprenons certains de ces termes.
- Sommets adjacents - Un sommet a est adjacent au sommet b s'il existe une arête (a, b) ou (b, a).
- Chemin - Un chemin issu d'un sommet aléatoire w est une séquence adjacente de sommets.
- Cycle - C'est un chemin où les premier et dernier sommets sont les mêmes.
- Degré - Il s'agit d'un nombre d'arêtes incidentes sur un sommet.
- Graphique connecté - S'il existe un chemin d'un sommet aléatoire à un autre sommet, ce graphique est appelé graphique connecté.
Principales différences entre l'arbre et le graphique
- Dans un arbre, il n’existe qu’un seul chemin entre deux sommets, alors qu’un graphe peut avoir des chemins unidirectionnels et bidirectionnels entre les nœuds.
- Dans l'arborescence, il existe exactement un nœud racine et chaque enfant ne peut avoir qu'un seul parent. Par contre, dans un graphique, il n’existe pas de concept de nœud racine.
- Un arbre ne peut pas avoir de boucles et auto-boucles tandis qu'un graphique peut avoir des boucles et auto-boucles.
- Les graphes sont plus compliqués car ils peuvent avoir des boucles et des boucles auto. En revanche, les arbres sont simples par rapport au graphique.
- L'arbre est parcouru à l'aide de techniques de pré-commande, de commande et de post-commande. Par contre, pour parcourir le graphe, nous utilisons BFS (Breadth First Search) et DFS (Depth First Search).
- Un arbre peut avoir n-1 arêtes. Au contraire, dans le graphique, il n'y a pas de nombre d'arêtes prédéfini, cela dépend du graphique.
- Une arborescence a une structure hiérarchique alors que graph a un modèle de réseau.
Conclusion
Le graphique et l'arborescence sont la structure de données non linéaire utilisée pour résoudre divers problèmes complexes. Un graphique est un groupe de sommets et d'arêtes où une arête connecte une paire de sommets, tandis qu'un arbre est considéré comme un graphe peu connecté, qui doit être connecté et exempt de boucles.
