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.