Profondeur d'abord vs largeur-premier recherche

Si vous avez pris le temps d’étudier le code sous quelque forme que ce soit, vous avez probablement rencontré des structures de données. Les structures de données comprennent une multitude de possibilités pour stocker, organiser et manipuler des données. Parmi les plus populaires figurent les tableaux, les listes chaînées, les piles, les files d'attente et les arbres de recherche binaires. Dans l’intérêt de cet article, nous allons nous intéresser à deux manières différentes d’aborder la traversée d’arbres: la recherche avant tout en profondeur et la recherche avant tout en profondeur.

Qu'est ce qu'un arbre?

Une arborescence est une structure de données composée de nœuds, contenant des pointeurs vers d'autres nœuds. Contrairement aux arbres dans la vie réelle (ou peut-être existent-ils quelque part), un arbre de données est à l'envers. Essentiellement, la racine est en haut et les feuilles en bas.

Décomposons le diagramme.

Chaque arbre a un seul nœud racine qui se trouve au niveau supérieur (dans ce cas, le niveau 0). Ensuite, nous voyons qu'au niveau suivant, le nœud racine A a des pointeurs sur les nœuds B et C. De même, les nœuds B et C ont des pointeurs sur le nœud A. Dans cette situation, le nœud A est le nœud parent et les nœuds B et C sont: ses enfants. De plus, les nœuds B et C sont considérés comme des frères et soeurs.

Vous vous demandez peut-être s'il est possible qu'un nœud ait plus de 2 enfants. La réponse est oui! Cette représentation spécifique est un arbre binaire qui peut être déterminé par un maximum de deux nœuds enfants pour chaque parent.

Code de l'arbre

Avertissement: J'utiliserai Javascript pour créer un arbre simple!

Tout d'abord, nous devons créer une classe de nœud:

Lorsque nous créons une classe de nœuds, nous lui transmettons une valeur, ou data, qui devient la propriété data du nœud. Nous avons également des propriétés parent et children qui sont nulles et un tableau vide, pour le moment. Finalement, la propriété parent désignera le parent du nœud spécifique et la propriété enfants désignera les enfants du nœud.

Ensuite, nous créons la classe tree:

La classe tree contient une propriété unique, root, qui est initialement nulle. Les arbres incluent des méthodes prototypes telles que contains (), insert () et remove (), mais nous les conserverons pour un jour de pluie!

Recherche!

Les recherches en profondeur d'abord et en largeur d'abord sont des méthodes prototypes de la classe Tree utilisées pour déterminer si un nœud particulier contenant des données spécifiques existe dans une arborescence. La représentation ci-dessous montre les deux procédures de recherche différentes.

Approche profondeur-premier

La méthode de profondeur en premier commence au nœud racine et se déplace vers le nœud le plus à gauche. Une fois qu'il atteint le nœud le plus à gauche, il remonte dans l'arbre à la racine, puis au nœud le plus à droite. S'il frappe un nœud avec des enfants, il traversera les enfants de ce nœud de gauche à droite, puis continuera à droite.

Ordre de recherche: [10, 4, 1, 9, 17, 12, 18]

Code

La recherche en profondeur d'abord prend une valeur en tant qu'argument qui est la valeur que nous recherchons dans l'arborescence. Puisque nous voulons traverser les nœuds de gauche à droite, nous définissons la racine comme une pile car nous voulons adopter une approche dernier entré, premier sorti. Ensuite, nous effectuons une boucle while qui continue tant que la pile contient des éléments. Dans la boucle while, nous supprimons le premier élément de la pile ou appelons la méthode de tableau shift () et le fixons à un nœud. Nous comparons les données de ce nœud à la valeur de l’argument et, si elles correspondent, la fonction renvoie true. Si ce n’est pas le cas, il ajoute les enfants du nœud au premier plan de la pile ou appelle la méthode de tableau unshift () et poursuit la recherche dans les nouvelles données. Si la valeur particulière n'existe pas dans l'arborescence, la fonction renvoie false.

Approche largeur d'abord

L'approche en largeur d'abord commence au nœud racine et traverse chaque niveau successif pour rechercher le nœud souhaité. De manière similaire à l’approche en profondeur, les nœuds sont lus de gauche à droite à chaque niveau.

Ordre de recherche: [10, 4, 17, 1, 9, 12, 18]

Code

La recherche en largeur d'abord est similaire dans le code à la recherche en profondeur d'abord. Il faut qu'une valeur soit trouvée comme argument. La différence ici est qu’au lieu d’utiliser une pile, nous souhaitons utiliser une file d’attente pour pouvoir adopter une approche premier entré, premier sorti. Dans la boucle while, de la même manière que la recherche en profondeur d'abord, nous souhaitons utiliser la méthode de tableau shift () pour supprimer le premier élément de la file d'attente en tant que nœud. Toutefois, si les données du nœud ne correspondent pas à la valeur souhaitée, au lieu de décocher les enfants du nœud, nous utiliserons la méthode de tableau push () pour ajouter les enfants à la fin de la file. Cela nous permet de vérifier chaque nœud d'un niveau avant de traverser les nœuds du niveau suivant. Enfin, comme pour la recherche en profondeur, si la valeur n’est pas trouvée, la fonction retournera false.

Le quel j'utilise?

Bien que les recherches en profondeur d'abord (DFS) et en largeur d'abord (BFS) soient des approches légitimes et puissent aboutir aux mêmes conclusions, chacune est privilégiée dans certaines circonstances. Cependant, il n'est pas souvent évident de savoir lequel des deux est le plus efficace.

Avertissement: Ce sont des directives générales! Ce ne sont certainement pas toujours les approches les plus optimales.

DFS: généralement préféré lorsque l'arborescence est très profonde et que les valeurs ou données souhaitées sont peu fréquentes.

BFS: généralement préféré dans les arbres peu profonds qui ne sont pas trop larges. Également utilisé s'il est connu que le nœud souhaité est plus proche du niveau racine.

Même s'il existe des préférences générales pour décider de la méthode à utiliser, en cas de doute, il est probablement préférable d'essayer les deux méthodes et de voir laquelle est la plus efficace.

Supposons, par exemple, que vous utilisiez l’arborescence ci-dessus et que vous recherchiez le nœud contenant 8. L’arborescence n’est pas aussi profonde; vous pouvez donc penser qu’il serait préférable d’utiliser un système de fichiers BFS. Cependant, il serait en fait plus efficace d’utiliser un DFS.

Comparons les deux méthodes et quels nœuds ont été traversés:

DSF: 1, 2, 4, 8

BFS: 1, 2, 3, 4, 5, 6, 7, 8

Nous pouvons déjà constater qu’une première recherche approfondie traverse plus de nœuds et nécessite par conséquent un accès à plus de mémoire.

De plus, une fois que nous aurons localisé le noeud 8, la pile DFS serait [8, 9, 5, 3], tandis que la file d'attente BFS serait [8, 9, 10, 11, 13, 14]. La file d’attente BFS contient 2 nœuds supplémentaires, ce qui ne semble pas équivaloir à beaucoup dans cet exemple, mais en termes de mémoire, elle en utilise toujours plus. Par conséquent, dans cette situation particulière, un DFS serait plus efficace qu'un BFS.

Bien que cet exemple soit simple et direct, dans les situations où les arbres sont plus profonds et plus larges, il est nettement plus difficile de déterminer lequel est le plus optimal. La meilleure façon de dicter la meilleure méthode consiste à essayer les deux.

Complexité

La complexité temporelle et spatiale de DFS et de BFS est assez simple. Puisque nous parlons de traversée d’arbre, pour déterminer si une valeur ou des données existent dans l’arbre, nous devons visiter chaque nœud. Visiter chaque nœud une seule fois signifie que la complexité temporelle de DFS et de BFS est O (n) ou linéaire. Si nous considérons les arbres comme des tableaux triés, il suffirait d’un seul test pour déterminer si une valeur correspond ou non à la valeur recherchée. De même, en termes de complexité d'espace, DFS est O (h) et BFS est O (w). Pour DFS, "h" représente la hauteur car la quantité d’espace nécessaire à la fonction dépend du nombre de nœuds de l’arbre. De même, pour BFS, «w» représente la largeur, car l’espace dépend de la largeur de l’arbre. Bien entendu, ces grandes notations O changent en fonction de la structure des données, mais dans l’intérêt des arbres, les complexités temporelles et spatiales seront les mêmes.

Merci d'avoir pris le temps de lire cet article! Si vous avez des commentaires ou des questions, faites le moi savoir! J'espere que tu passes une bonne journée!