Structures de données Python: l'arbre des dons

Les arbres Python ressemblent beaucoup à des listes chaînées, mais avec un ordre hiérarchique. Les arbres sont composés de nœuds reliés à d'autres nœuds. Le nœud inférieur qui n'a pas de lien est appelé feuilles . Le nœud lié à un autre nœud est connu sous le nom de parent, et les nœuds liés sont les enfants.

Une arborescence est généralement construite avec une large gamme de nœuds ou une structure profonde en cascade. Vous pouvez donc dire qu'un arbre est large ou profond .

Une version efficace d'une structure arborescente est connue sous le nom d'arbre de recherche binaire. C'est là que vous autorisez uniquement un nœud parent à avoir deux nœuds enfants. Le nœud à gauche a une valeur plus petite que le nœud à droite. Construire un arbre comme celui-ci rend très efficace la traversée et la recherche d'une valeur particulière.

Dans l'exemple ci-dessus, si je voulais trouver la valeur de 98 à partir de 39, je me déplacerais à droite comme 98> 39 - de 70 à nouveau à droite - à partir de 97, à droite, et en trois coups, j'ai trouvé le nœud souhaité.

Construisons donc un nœud d'arbre en python et voyons-en un en action. Tout ce dont nous aurons besoin pour lancer un nœud d'arbre est un nom. Nous lui attribuerons automatiquement une liste vide pour contenir tous les nœuds enfants à venir.

Si vous aviez lu mes articles précédents sur la structure de données python, cela devrait vous sembler familier.

Maintenant, comme pour toute structure de données, nous devons garder à l'esprit les fonctionnalités pratiques que nous voulons que notre arbre ait. L'ajout d'un nœud et la suppression d'un nœud sont des choix évidents et faciles à mettre en œuvre.

Pour ajouter, j'utiliserai la méthode append () , et pour supprimer je vais simplement parcourir la liste self.children et ajouter à nouveau tous les nœuds à l'exception du nœud que je veux supprimer.

Ensuite, nous voudrons parcourir l'arborescence pour trouver les informations souhaitées. Pour créer cette méthode, nous allons commencer avec une liste vide à remplir avec chaque nœud à visiter. Tant que ce nœud a des nœuds enfants, nous le sortirons et l'ajouterons à la liste des nœuds à visiter.

Selon vous, où une structure de données comme celle-ci serait-elle le mieux utilisée? Peut-être que si nous ajoutions une logique pour accéder aux nœuds, nous pourrions compartimenter un grand nombre de privilèges qu'un utilisateur pourrait avoir.

Les arbres de données sont un outil formidable et largement utilisé dans le monde du codage. J'espère que cette brève introduction vous a au moins donné un aperçu des raisons pour lesquelles vous voudriez connaître ces structures.