Théorie des graphes | Introduction aux arbres
Théorie des graphes simplifiée
Arbres à l’état sauvage
Voyons quelques occasions où nous rencontrons les applications des arbres.
- Arbre généalogique
- Taxonomie
- Arbre de théorie des graphes
- Arbre d’analyse de texte
- Hierarchie sociale
- Arbre de probabilité
Stockage des arbres non dirigés
Nous devons commencer par attribuer des numéros à chaque nœud de l’arborescence à partir de 0 à n – 1, où n est le nombre total de nœuds.
Arbres enracinés
Les arbres enracinés auraient un nœud spécial désigné comme Noeud principal, d’où le nom des arbres enracinés.
Arbre binaire
Nous ne pouvons jamais quitter cette session sans mentionner les arbres binaires. Nous les appelons des arbres binaires ou simplement B – Arbre est parce que chaque nœud de l’arbre aurait au total 2 nœuds enfants au total.
Arbre de recherche binaire
Nous appelons un arbre, un arbre de recherche binaire si et seulement s’il satisfait à l’invariant BST qui est défini comme, pour chaque nœud x, les valeurs dans le sous-arbre gauche sont strictement inférieures à la valeur de x et les valeurs dans le sous-arbre droit sont supérieures que la valeur de x. Un arbre de recherche binaire est vraiment utile lorsqu’il s’agit d’un problème de recherche.
Stockage des arbres enracinés
Conclusion
Aujourd’hui, nous avons trouvé ce qu’est un arbre et ses différentes variétés. L’idée centrale de ce billet était de vous faire prendre conscience de la structure des données et de certaines de ses applications réelles. Nous discuterons plus des algorithmes dans le prochain article de cette série. Jusque-là, restez à l’écoute.
