Τι είναι ένα Δυαδικό Δέντρο Αναζήτησης;

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

Σε αυτό το άρθρο, θα ρίξουμε μια πιο προσεκτική ματιά στον τρόπο λειτουργίας του—μαζί με τις ιδιότητες και τις εφαρμογές του.

Τι είναι ένα Δυαδικό Δέντρο Αναζήτησης;

Μια Δυαδική Δενδρική Αναζήτηση είναι μια δομή δεδομένων που αποτελείται από κόμβους—όμοια με τις Συνδεδεμένες λίστες. Μπορεί να υπάρχουν δύο τύποι κόμβων: ένας γονέας και ένας παιδί. Ο ριζικός κόμβος είναι το σημείο έναρξης της δομής που διακλαδίζεται σε δύο θυγατρικούς κόμβους, που ονομάζονται αριστερός και δεξιός κόμβος.

Κάθε κόμβος μπορεί να αναφέρεται μόνο από τον γονέα του και μπορούμε να διασχίσουμε τους κόμβους του δέντρου ανάλογα με την κατεύθυνση. Το Δυαδικό Δέντρο Αναζήτησης έχει τρεις κύριες ιδιότητες:

1. Ο αριστερός κόμβος είναι μικρότερος από τον γονέα του.
instagram viewer
2. Ο δεξιός κόμβος είναι μεγαλύτερος από τον γονέα του.
3. Το αριστερό και το δεξί υποδέντρο πρέπει να είναι Δυαδικά Δέντρα αναζήτησης.

Ένα Τέλειο Δυαδικό Δέντρο Αναζήτησης επιτυγχάνεται όταν γεμίζονται όλα τα επίπεδα και κάθε κόμβος έχει έναν αριστερό και έναν δεξιό θυγατρικό κόμβο.

Σχετίζεται με: Βιβλιοθήκες Επιστήμης Δεδομένων για Python που πρέπει να χρησιμοποιεί κάθε επιστήμονας δεδομένων

Βασικές λειτουργίες ενός Δυαδικού Δέντρου Αναζήτησης

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

1. Λειτουργία αναζήτησης

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

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

2. Λειτουργία εισαγωγής

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

• Περίπτωση 1: Όταν δεν υπάρχει κόμβος. Ο κόμβος που θα εισαχθεί θα γίνει ο ριζικός κόμβος.

• Περίπτωση 2: Δεν υπάρχουν παιδιά. Σε αυτήν την περίπτωση, ο κόμβος θα συγκριθεί με τον ριζικό κόμβο. Αν είναι μεγαλύτερο, θα γίνει το σωστό παιδί. αλλιώς, θα γίνει το αριστερό παιδί.

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

3. Λειτουργία διαγραφής

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

• Περίπτωση 1: Διαγραφή κόμβου φύλλου. Ένας κόμβος φύλλων είναι ένας κόμβος χωρίς παιδιά. Αυτό είναι το πιο εύκολο να αφαιρεθεί, καθώς δεν επηρεάζει κανέναν άλλο κόμβο. απλά διασχίζουμε το δέντρο μέχρι να το φτάσουμε και να το διαγράψουμε.

• Περίπτωση 2: Διαγραφή κόμβου με ένα παιδί. Η διαγραφή ενός γονέα με έναν κόμβο θα έχει ως αποτέλεσμα το παιδί να πάρει τη θέση του και όλοι οι επόμενοι κόμβοι θα ανέβουν ένα επίπεδο. Δεν θα υπάρξει καμία αλλαγή στη δομή των υποδέντρων.

• Περίπτωση 3: Διαγραφή κόμβου με δύο παιδιά. Όταν πρέπει να αφαιρέσουμε έναν κόμβο με δύο παιδιά, πρέπει πρώτα να βρούμε έναν επόμενο κόμβο που μπορεί να πάρει τη θέση του. Δύο κόμβοι μπορούν να αντικαταστήσουν τον κόμβο που αφαιρέθηκε, τον διάδοχο ή τον προκάτοχο της σειράς. Ο διάδοχος της σειράς είναι το πιο αριστερό παιδί του δεξιού υποδέντρου και ο προκάτοχος της τάξης είναι το δεξιότερο παιδί του αριστερού υποδέντρου. Αντιγράφουμε τα περιεχόμενα του διαδόχου/προκατόχου στον κόμβο και διαγράφουμε τον κατά σειρά διάδοχο/προηγούμενο.

Σχετίζεται με: Πώς να δημιουργήσετε δομές δεδομένων με κλάσεις JavaScript ES6

Πώς να διασχίσετε ένα δυαδικό δέντρο αναζήτησης

Η διέλευση είναι η διαδικασία μέσω της οποίας πλοηγούμαστε σε ένα Δυαδικό Δέντρο αναζήτησης. Γίνεται για τον εντοπισμό ενός συγκεκριμένου στοιχείου ή για την εκτύπωση ενός περιγράμματος του δέντρου. Ξεκινάμε πάντα από τον ριζικό κόμβο και πρέπει να ακολουθήσουμε τις άκρες για να φτάσουμε στους άλλους κόμβους. Κάθε κόμβος θα πρέπει να θεωρείται υποδέντρο και η διαδικασία επαναλαμβάνεται μέχρι να γίνει επίσκεψη σε όλους τους κόμβους.

• Διαδρομή κατά σειρά: Η διέλευση κατά σειρά θα δημιουργήσει έναν χάρτη με αύξουσα σειρά. Με αυτή τη μέθοδο, ξεκινάμε από το αριστερό υποδέντρο και συνεχίζουμε στη ρίζα και στο δεξί υποδέντρο.

• Διέλευση προπαραγγελίας: Σε αυτή τη μέθοδο, επισκέπτεται πρώτα τον ριζικό κόμβο, ακολουθούμενο από το αριστερό υποδέντρο και το δεξί υποδέντρο.

• Διέλευση μετά την παραγγελία: Αυτή η διέλευση περιλαμβάνει την τελευταία επίσκεψη στον ριζικό κόμβο. Ξεκινάμε από το αριστερό υποδέντρο, μετά το δεξί υποδέντρο και μετά τον ριζικό κόμβο.

Εφαρμογές πραγματικού κόσμου

Λοιπόν, πώς χρησιμοποιούμε αλγόριθμους δυαδικού δέντρου αναζήτησης; Όπως μπορεί να υποτεθεί, είναι εξαιρετικά αποτελεσματικά στην αναζήτηση και την ταξινόμηση. Η μεγαλύτερη δύναμη των δυαδικών δέντρων είναι η οργανωμένη δομή τους. Επιτρέπει την αναζήτηση να γίνεται με αξιοσημείωτες ταχύτητες μειώνοντας την ποσότητα των δεδομένων που πρέπει να αναλύσουμε κατά το ήμισυ ανά πάσα.

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

Ίσως εκπλαγείτε αν μάθετε ότι ο κώδικας Μορς χρησιμοποιεί ένα δυαδικό δέντρο αναζήτησης για την κωδικοποίηση δεδομένων. Ένας άλλος σημαντικός λόγος που τα Δυαδικά Δέντρα Αναζήτησης είναι τόσο χρήσιμα είναι οι πολλαπλές παραλλαγές τους. Η ευελιξία τους έχει οδηγήσει στη δημιουργία πολλών παραλλαγών για την επίλυση όλων των ειδών των προβλημάτων. Όταν χρησιμοποιούνται σωστά, τα Δυαδικά Δέντρα Αναζήτησης είναι ένα μεγάλο πλεονέκτημα.

Δυαδικά δέντρα αναζήτησης: Το τέλειο σημείο εκκίνησης

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

15 μέθοδοι συστοιχίας JavaScript που πρέπει να κατακτήσετε σήμερα

Θέλετε να κατανοήσετε τους πίνακες JavaScript αλλά δεν μπορείτε να τους χειριστείτε; Ελέγξτε τα παραδείγματα πίνακα JavaScript για καθοδήγηση.

Διαβάστε Επόμενο

Σχετικά με τον Συγγραφέα