Βάθος-Πρώτη εναντίον εύρους-πρώτης αναζήτησης

Εάν έχετε πάρει το χρόνο για να μελετήσει κώδικα σε οποιοδήποτε σχήμα ή μορφή, πιθανότατα θα συναντήσετε δομές δεδομένων. Οι δομές δεδομένων αποτελούνται από πληθώρα δυνατοτήτων αποθήκευσης, οργάνωσης και χειρισμού δεδομένων. Ορισμένες από τις πιο δημοφιλείς περιλαμβάνουν συστοιχίες, συνδεδεμένες λίστες, στοίβες, ουρές και δυαδικά δέντρα αναζήτησης. Για χάρη αυτού του άρθρου, θα επικεντρωθούμε σε δύο διαφορετικούς τρόπους προσέγγισης του διαδρόμου: Βάθος-Πρώτη Αναζήτηση και Πλάτος-Πρώτη αναζήτηση.

Τι είναι ένα δέντρο;

Ένα δέντρο είναι μια δομή δεδομένων που αποτελείται από κόμβους, οι οποίοι περιέχουν δείκτες σε άλλους κόμβους. Σε αντίθεση με τα δέντρα στην πραγματική ζωή (ή ίσως υπάρχουν κάπου), ένα δέντρο δεδομένων είναι ανάποδα. Ουσιαστικά, η ρίζα είναι στην κορυφή και τα φύλλα βρίσκονται στο κάτω μέρος.

Ας σπάσουμε το διάγραμμα.

Κάθε δέντρο έχει έναν μοναδικό κόμβο ρίζας ο οποίος βρίσκεται στο ανώτερο επίπεδο (στην περίπτωση αυτή, επίπεδο 0). Στη συνέχεια, βλέπουμε ότι στο επόμενο επίπεδο, ο ρίζας Α έχει δείκτες στους κόμβους Β και C. Παρομοίως, οι κόμβοι Β και Γ έχουν δείκτες στον κόμβο Α. Στην περίπτωση αυτή, ο κόμβος Α είναι ο γονικός κόμβος και οι κόμβοι Β και Γ είναι τα παιδιά της. Επιπλέον, οι κόμβοι Β και Γ θεωρούνται αδέλφια.

Ίσως αναρωτιέστε αν είναι δυνατόν για έναν κόμβο να έχουν περισσότερα από 2 παιδιά. Η απάντηση είναι ναι! Αυτή η συγκεκριμένη απεικόνιση είναι ενός δυαδικού δέντρου το οποίο μπορεί να προσδιοριστεί από το μέγιστο δύο παιδικών κόμβων για κάθε γονέα.

Κωδικός δέντρου

Αποποίηση ευθυνών: Θα χρησιμοποιήσω Javascript για να δημιουργήσω ένα απλό δέντρο!

Πρώτον, πρέπει να δημιουργήσουμε μια κλάση κόμβου:

Όταν δημιουργούμε μια κλάση κόμβου, την περάσαμε μια τιμή ή δεδομένα, η οποία γίνεται η ιδιότητα δεδομένων του κόμβου. Έχουμε επίσης γονικές και παιδικές ιδιότητες οι οποίες είναι null και μια κενή σειρά, αντίστοιχα, για τώρα. Τελικά, η μητρική ιδιότητα θα δείχνει στον γονέα του συγκεκριμένου κόμβου και η ιδιότητα των παιδιών θα δείχνει στα παιδιά του κόμβου.

Στη συνέχεια, δημιουργούμε την κλάση δέντρων:

Η κλάση δέντρου περιέχει μια μοναδική ιδιότητα, ρίζα, η οποία αρχικά είναι μηδενική. Τα δέντρα περιλαμβάνουν πρωτότυπες μεθόδους όπως περιέχει (), insert () και αφαίρεση (), αλλά θα τις σώσουμε για μια βροχερή μέρα!

Ερευνητικός!

Οι αναζητήσεις βάθους-πρώτης και πρώτης ύλης είναι πρωτότυπες μέθοδοι της κλάσης δέντρων που χρησιμοποιούνται για να προσδιοριστεί αν ένας συγκεκριμένος κόμβος που περιέχει συγκεκριμένα δεδομένα υπάρχει μέσα σε ένα δέντρο. Η παρακάτω απεικόνιση δείχνει τις δύο διαφορετικές διαδικασίες αναζήτησης.

Βάθος-πρώτη προσέγγιση

Η μέθοδος βάθους-πρώτου αρχίζει από τον κόμβο ρίζας και μετακινείται προς τον αριστερό κόμβο. Αφού πλησιάσει τον αριστερό κόμβο, διασχίζει το δέντρο πίσω στη ρίζα και στη συνέχεια στον κόμβο της δεξιάς. Αν πλησιάσει έναν κόμβο με παιδιά, θα διασχίσει τα παιδιά του κόμβου από αριστερά προς τα δεξιά και στη συνέχεια θα συνεχίσει δεξιά.

Ταξινόμηση αναζήτησης: [10, 4, 1, 9, 17, 12, 18]

Κώδικας

Η αναζήτηση βάθους κατά βάθος παίρνει μια τιμή ως ένα όρισμα που είναι η τιμή που ψάχνουμε στο δέντρο. Δεδομένου ότι θέλουμε να διασχίσουμε τους κόμβους από αριστερά προς τα δεξιά, ορίσαμε τη ρίζα ως στοίβα γιατί θέλουμε να ακολουθήσουμε μια τελευταία προσέγγιση. Στη συνέχεια, εκτελούμε ένα βρόχο ενώ συνεχίζουμε όσο η στοίβα περιέχει στοιχεία. Εντός του βρόχου while, αφαιρούμε το πρώτο στοιχείο της στοίβας ή καλούμε τη μέθοδο πίνακα shift () και το ορίζουμε ίσο με έναν κόμβο. Συγκρίνουμε τα δεδομένα του κόμβου με την τιμή του επιχειρήματος και αν ταιριάζουν, η συνάρτηση επιστρέφει true. Αν δεν συμβαίνει αυτό, προσθέτει τα παιδιά του κόμβου στο μπροστινό μέρος της στοίβας ή καλεί τη μέθοδο πίνακα μετατόπισης () και συνεχίζει την αναζήτηση στα νέα δεδομένα. Εάν η συγκεκριμένη τιμή δεν υπάρχει στο δέντρο, η συνάρτηση επιστρέφει ψευδής.

Πρώτη Προσέγγιση

Η προσέγγιση του πρώτου εύρους ξεκινά στον κόμβο ρίζας και διασχίζει κάθε διαδοχικό επίπεδο για να αναζητήσει τον επιθυμητό κόμβο. Παρόμοια με την προσέγγιση βάθους-πρώτου, οι κόμβοι διαβάζονται από αριστερά προς τα δεξιά σε κάθε επίπεδο.

Ταξινόμηση αναζήτησης: [10, 4, 17, 1, 9, 12, 18]

Κώδικας

Η αναζήτηση πρώτης λέξης είναι παρόμοια σε αναζήτηση σε κώδικα σε βάθος-πρώτη. Παίρνει αξία που πρέπει να βρεθεί ως επιχείρημα. Η διαφορά εδώ είναι ότι αντί να χρησιμοποιούμε μια στοίβα, θέλουμε να χρησιμοποιήσουμε μια ουρά για να μπορέσουμε να πάρουμε μια πρώτη σε πρώτη προσέγγιση. Στο βρόχο while, όπως και στην πρώτη αναζήτηση βάθους, θέλουμε να χρησιμοποιήσουμε τη μέθοδο array shift () για να αφαιρέσουμε το πρώτο στοιχείο της ουράς ως κόμβο. Ωστόσο, αν τα δεδομένα κόμβου δεν είναι ίδια με την επιθυμητή τιμή, αντί να στρέψουμε τα παιδιά του κόμβου, θα χρησιμοποιήσουμε τη μέθοδο array push () για να προσθέσουμε τα παιδιά στο τέλος της ουράς. Αυτό μας επιτρέπει να ελέγξουμε τον κάθε κόμβο σε ένα επίπεδο πριν διασχίσουμε τους κόμβους στο επόμενο επίπεδο. Τέλος, ακριβώς όπως η πρώτη αναζήτηση βάθους, εάν η τιμή δεν βρεθεί, η λειτουργία θα επιστρέψει ψευδής.

Το οποίο χρησιμοποιώ?

Παρόλο που οι αναζητήσεις βάθους-πρώτου (DFS) και εύρους-πρώτης (BFS) είναι νόμιμες προσεγγίσεις και μπορούν να φτάσουν στα ίδια συμπεράσματα, ο καθένας ευνοείται υπό ορισμένες συνθήκες. Ωστόσο, δεν είναι συχνά προφανές ποιο είναι το πιο αποτελεσματικό από τα δύο.

Αποποίηση ευθυνών: Αυτές είναι γενικές οδηγίες! Σίγουρα όχι πάντα οι βέλτιστες προσεγγίσεις.

DFS: Γενικά προτιμάται όταν το δέντρο είναι πολύ βαθιά και οι επιθυμητές τιμές ή δεδομένα εμφανίζονται σπάνια.

BFS: Γενικά προτιμάται σε ρηχά δέντρα που δεν είναι πολύ φαρδιά. Χρησιμοποιείται επίσης εάν είναι γνωστό ότι ο επιθυμητός κόμβος είναι πιο κοντά στο επίπεδο της ρίζας.

Παρόλο που υπάρχουν γενικές προτιμήσεις όταν αποφασίζετε ποια μέθοδο θα χρησιμοποιήσετε, αν δεν είστε σίγουροι, ίσως είναι καλύτερο να δοκιμάσετε και τις δύο μεθόδους και να δείτε ποια είναι πιο αποτελεσματική.

Για παράδειγμα, ας πούμε ότι χρησιμοποιείτε το παραπάνω δέντρο και ψάχνετε τον κόμβο που περιέχει το 8. Το δέντρο δεν είναι τόσο βαθιά ώστε ίσως να νομίζετε ότι θα ήταν καλύτερο να χρησιμοποιήσετε ένα BFS. Ωστόσο, θα ήταν στην πραγματικότητα πιο αποτελεσματική η χρήση ενός DFS.

Ας συγκρίνουμε τις δύο μεθόδους και ποιοι κόμβοι έχουν περάσει:

DFS: 1, 2, 4, 8

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

Ήδη μπορούμε να διαπιστώσουμε ότι μια πρώτη αναζήτηση ευρέως διαπερνά περισσότερους κόμβους και ως εκ τούτου χρειάζεται πρόσβαση σε περισσότερη μνήμη.

Επιπλέον, αφού εντοπίσουμε τον κόμβο 8, η στοίβα DFS θα είναι [8, 9, 5, 3] ενώ η ουρά BFS θα είναι [8, 9, 10, 11, 13, 14]. Η ουρά BFS περιέχει 2 ακόμη κόμβους, που δεν φαίνονται να εξισώνουν πολύ σε αυτό το παράδειγμα, αλλά από την άποψη της μνήμης, χρησιμοποιεί ακόμα μεγαλύτερο ποσό. Επομένως, σε αυτή τη συγκεκριμένη περίπτωση, ένα DFS θα ήταν πιο αποτελεσματικό από ένα BFS.

Αν και αυτό το παράδειγμα είναι απλό και απλό, σε καταστάσεις όπου τα δέντρα είναι βαθύτερα και ευρύτερα, είναι σίγουρα πολύ πιο δύσκολο να προσδιοριστεί ποια είναι η βέλτιστη. Ο καλύτερος τρόπος για να υπαγορεύσετε την καλύτερη μέθοδο είναι να επιχειρήσετε και τα δύο.

Περίπλοκο

Η πολυπλοκότητα του χρόνου και του χώρου τόσο για το DFS όσο και για το BFS είναι αρκετά απλή. Εφόσον μιλάμε για διασταύρωση δένδρων, για να προσδιορίσουμε εάν υπάρχει μια τιμή ή δεδομένα μέσα στο δέντρο, πρέπει να επισκεφτούμε κάθε κόμβο. Η επίσκεψη σε κάθε κόμβο μία φορά σημαίνει ότι η πολυπλοκότητα του χρόνου τόσο για το DFS όσο και για το BFS είναι O (n) ή γραμμικό. Εάν σκεφτόμαστε τα δέντρα ως ταξινομημένα συστοιχίες, θα έπρεπε μόνο να περάσουμε μόνο μία φορά για να προσδιορίσουμε αν μια τιμή ταιριάζει ή όχι με την τιμή που αναζητούμε. Ομοίως, όσον αφορά την πολυπλοκότητα του χώρου, το DFS είναι O (h) και το BFS είναι O (w). Για το DFS, το 'h' αντιπροσωπεύει το ύψος από το πόσο διάστημα θα πάρει η λειτουργία εξαρτάται από τον αριθμό των κόμβων που είναι βαθιά στο δέντρο. Ομοίως, για το BFS, το 'w' σημαίνει πλάτος, αφού το διάστημα εξαρτάται από το πόσο πλάτος είναι το δέντρο. Φυσικά, αυτές οι μεγάλες σημειώσεις O αλλάζουν ανάλογα με τη δομή των δεδομένων, αλλά για χάρη των δέντρων, οι χρονικές και διαστημικές πολυπλοκότητες θα είναι οι ίδιες.

Σας ευχαριστώ που αφιερώσατε το χρόνο για να διαβάσετε αυτό το άρθρο! Εάν έχετε οποιαδήποτε σχόλια ή ερωτήσεις, ενημερώστε μας! Ελπίζω να έχεις μια υπέροχη μέρα!