Τι είναι το Δυαδικό Δέντρο Αναζήτησης;
Το δέντρο δυαδικής αναζήτησης είναι ένας προηγμένος αλγόριθμος που χρησιμοποιείται για την ανάλυση του κόμβου, των αριστερών και δεξιών κλάδων του, οι οποίοι μοντελοποιούνται σε μια δομή δέντρου και επιστρέφουν την τιμή. Το BST έχει σχεδιαστεί για την αρχιτεκτονική ενός βασικού αλγορίθμου δυαδικής αναζήτησης. Επομένως επιτρέπει ταχύτερες αναζητήσεις, παρεμβολές και αφαιρέσεις κόμβων. Αυτό καθιστά το πρόγραμμα πολύ γρήγορο και ακριβές.
Σε αυτό το σεμινάριο δομής δεδομένων, θα μάθετε:
- Τι είναι το Δυαδικό Δέντρο Αναζήτησης;
- Χαρακτηριστικά του Δυαδικού Δέντρου Αναζήτησης
- Γιατί χρειαζόμαστε ένα Δυαδικό Δέντρο Αναζήτησης;
- Τύποι δυαδικών δέντρων
- Πώς λειτουργεί το Δυαδικό Δέντρο Αναζήτησης;
- Σημαντικοί όροι
Χαρακτηριστικά του Δυαδικού Δέντρου Αναζήτησης
Το BST αποτελείται από πολλούς κόμβους και αποτελείται από τα ακόλουθα χαρακτηριστικά:
- Οι κόμβοι του δέντρου παρουσιάζονται σε σχέση γονέα-παιδιού
- Κάθε γονικός κόμβος μπορεί να έχει μηδενικούς θυγατρικούς κόμβους ή το πολύ δύο δευτερεύοντες κόμβους ή υποδέντρα στην αριστερή και τη δεξιά πλευρά.
- Κάθε δευτερεύον δέντρο, επίσης γνωστό ως δυαδικό δέντρο αναζήτησης, έχει υποκαταστήματα στα δεξιά και αριστερά του εαυτού τους.
- Όλοι οι κόμβοι συνδέονται με ζεύγη τιμών-κλειδιών.
- Τα πλήκτρα των κόμβων που υπάρχουν στο αριστερό υποδένδρο είναι μικρότερα από τα πλήκτρα του γονικού κόμβου τους
- Ομοίως, τα κλειδιά των κόμβων του αριστερού υποδέντρου έχουν μικρότερες τιμές από τα κλειδιά του γονικού κόμβου τους.
- Υπάρχει ο κύριος κόμβος ή το γονικό επίπεδο 11. Κάτω από αυτό, υπάρχουν αριστερά και δεξιά κόμβοι / κλάδοι με τις δικές τους βασικές τιμές
- Το σωστό δευτερεύον δέντρο έχει τιμές κλειδί μεγαλύτερες από τον γονικό κόμβο
- Το αριστερό δευτερεύον δέντρο έχει τιμές από τον γονικό κόμβο
Γιατί χρειαζόμαστε ένα Δυαδικό Δέντρο Αναζήτησης;
- Οι δύο κύριοι παράγοντες που καθιστούν το δέντρο δυαδικής αναζήτησης μια βέλτιστη λύση σε οποιοδήποτε πραγματικό πρόβλημα είναι η ταχύτητα και η ακρίβεια.
- Λόγω του γεγονότος ότι η δυαδική αναζήτηση είναι σε μορφή κλάδου με σχέσεις γονέα-παιδιού, ο αλγόριθμος γνωρίζει σε ποια θέση του δέντρου πρέπει να αναζητηθούν τα στοιχεία. Αυτό μειώνει τον αριθμό συγκρίσεων κλειδιού-τιμής που πρέπει να κάνει το πρόγραμμα για να εντοπίσει το επιθυμητό στοιχείο.
- Επιπλέον, σε περίπτωση που το προς αναζήτηση στοιχείο είναι μεγαλύτερο ή μικρότερο από τον γονικό κόμβο, ο κόμβος γνωρίζει ποια πλευρά δέντρου θα αναζητήσει. Ο λόγος είναι ότι, το αριστερό δευτερεύον δέντρο είναι πάντα μικρότερο από τον γονικό κόμβο και το δεξιό δευτερεύον δέντρο έχει τιμές πάντα ίσες ή μεγαλύτερες από τον γονικό κόμβο.
- Το BST χρησιμοποιείται συνήθως για την εφαρμογή σύνθετων αναζητήσεων, ισχυρών λογικών παιχνιδιών, αυτόματων ολοκληρωμένων δραστηριοτήτων και γραφικών.
- Ο αλγόριθμος υποστηρίζει αποτελεσματικά λειτουργίες όπως αναζήτηση, εισαγωγή και διαγραφή.
Τύποι δυαδικών δέντρων
Τρία είδη δυαδικών δέντρων είναι:
- Πλήρες δυαδικό δέντρο: Όλα τα επίπεδα στα δέντρα είναι γεμάτα από τις πιθανές εξαιρέσεις του τελευταίου επιπέδου. Παρομοίως, όλοι οι κόμβοι είναι γεμάτοι, κατευθύνοντας την αριστερά.
- Πλήρες δυαδικό δέντρο: Όλοι οι κόμβοι έχουν 2 θυγατρικούς κόμβους εκτός από το φύλλο.
- Ισορροπημένο ή τέλειο δυαδικό δέντρο: Στο δέντρο, όλοι οι κόμβοι έχουν δύο παιδιά. Εκτός αυτού, υπάρχει το ίδιο επίπεδο κάθε υπο-κόμβου.
Πώς λειτουργεί το Δυαδικό Δέντρο Αναζήτησης;
Το δέντρο έχει πάντα έναν ριζικό κόμβο και περαιτέρω θυγατρικούς κόμβους, είτε στα αριστερά είτε στα δεξιά. Ο αλγόριθμος εκτελεί όλες τις λειτουργίες συγκρίνοντας τιμές με τη ρίζα και τους επιπλέον θυγατρικούς κόμβους του στο αριστερό ή το δεξιό υποδένδρο ανάλογα.
Εξαρτάται από το στοιχείο που πρόκειται να εισαχθεί, αναζήτηση ή διαγραφή, μετά τη σύγκριση, ο αλγόριθμος μπορεί εύκολα να ρίξει το αριστερό ή το δεξιό υπόστρωμα του ριζικού κόμβου.
Η BST προσφέρει κυρίως τους ακόλουθους τρεις τύπους λειτουργιών για τη χρήση σας:
- Αναζήτηση: αναζητά το στοιχείο από το δυαδικό δέντρο
- Εισαγωγή: προσθέτει ένα στοιχείο στο δυαδικό δέντρο
- Διαγραφή: διαγράψτε το στοιχείο από ένα δυαδικό δέντρο
Κάθε λειτουργία έχει τη δική της δομή και τη μέθοδο εκτέλεσης / ανάλυσης, αλλά το πιο σύνθετο από όλα είναι η λειτουργία Διαγραφή.
Λειτουργία αναζήτησης
Πάντα να ξεκινάτε την ανάλυση του δέντρου στον ριζικό κόμβο και στη συνέχεια να προχωράτε περισσότερο προς το δεξί ή το αριστερό υπόστρωμα του ριζικού κόμβου, ανάλογα με το στοιχείο που θα βρίσκεται είτε λιγότερο ή μεγαλύτερο από τη ρίζα.
- Το στοιχείο προς αναζήτηση είναι 10
- Συγκρίνετε το στοιχείο με τον ριζικό κόμβο 12, 10 <12, επομένως μετακινείτε προς το αριστερό υποδένδρο. Δεν χρειάζεται να αναλύσετε το δεξιό υπόφυτο
- Τώρα συγκρίνετε το 10 με τον κόμβο 7, 10> 7, οπότε μεταβείτε στο δεξιό υπόφυτο
- Στη συνέχεια, συγκρίνετε το 10 με τον επόμενο κόμβο, που είναι 9, 10> 9, κοιτάξτε στο παιδί του δευτερεύοντος δέντρου
- 10 ταιριάζει με την τιμή στον κόμβο, 10 = 10, επιστρέφει την τιμή στον χρήστη.
Εισαγωγή λειτουργίας
Αυτή είναι μια πολύ ευθεία κίνηση. Πρώτα, εισάγεται ο ριζικός κόμβος και μετά η επόμενη τιμή συγκρίνεται με τον ριζικό κόμβο. Εάν η τιμή είναι μεγαλύτερη από τη ρίζα, προστίθεται στο δεξιό υποδένδρο και εάν είναι μικρότερη από τη ρίζα, προστίθεται στο αριστερό υποδένδρο.
- Υπάρχει μια λίστα με 6 στοιχεία που πρέπει να εισαχθούν σε BST με σειρά από αριστερά προς τα δεξιά
- Εισαγάγετε το 12 ως τον ριζικό κόμβο και συγκρίνετε τις επόμενες τιμές 7 και 9 για την αντίστοιχη εισαγωγή στο δεξί και το αριστερό υποδένδρο
- Συγκρίνετε τις υπόλοιπες τιμές 19, 5 και 10 με τον ριζικό κόμβο 12 και τοποθετήστε τις ανάλογα. 19> 12 τοποθετήστε το ως το δεξί παιδί των 12, 5 <12 & 5 <7, επομένως τοποθετήστε το ως αριστερό παιδί των 7 ετών.
- Τώρα συγκρίνετε 10, 10 είναι <12 & 10 είναι> 7 & 10 είναι> 9, τοποθετήστε το 10 ως δεξιό υπόστρωμα του 9.
Διαγραφή λειτουργιών
Το Delete είναι το πιο προηγμένο και πολύπλοκο μεταξύ όλων των άλλων λειτουργιών. Υπάρχουν πολλές περιπτώσεις που αντιμετωπίζονται για διαγραφή στο BST.
- Περίπτωση 1- Κόμβος με μηδενικά παιδιά: αυτή είναι η ευκολότερη κατάσταση, απλά πρέπει να διαγράψετε τον κόμβο που δεν έχει άλλα παιδιά στα δεξιά ή τα αριστερά.
- Περίπτωση 2 - Κόμβος με ένα παιδί: μόλις διαγράψετε τον κόμβο, απλώς συνδέστε τον θυγατρικό κόμβο του με τον γονικό κόμβο της διαγραμμένης τιμής.
- Περίπτωση 3 Κόμβος με δύο παιδιά: αυτή είναι η πιο δύσκολη κατάσταση και λειτουργεί με τους ακόλουθους δύο κανόνες
- 3a - Προηγούμενος κατά σειρά: πρέπει να διαγράψετε τον κόμβο με δύο παιδιά και να τον αντικαταστήσετε με τη μεγαλύτερη τιμή στο αριστερό υποδένδρο του διαγραμμένου κόμβου
- 3b - Σε διάδοχο διάδοξης: πρέπει να διαγράψετε τον κόμβο με δύο παιδιά και να τον αντικαταστήσετε με τη μεγαλύτερη τιμή στο δεξιό υπόφυλλο του διαγραμμένου κόμβου
- Αυτή είναι η πρώτη περίπτωση διαγραφής στην οποία διαγράφετε έναν κόμβο που δεν έχει παιδιά. Όπως μπορείτε να δείτε στο διάγραμμα ότι τα 19, 10 και 5 δεν έχουν παιδιά. Αλλά θα διαγράψουμε το 19.
- Διαγράψτε την τιμή 19 και αφαιρέστε τον σύνδεσμο από τον κόμβο.
- Δείτε τη νέα δομή του BST χωρίς 19
- Αυτή είναι η δεύτερη περίπτωση διαγραφής στην οποία διαγράφετε έναν κόμβο που έχει 1 θυγατρικό, όπως μπορείτε να δείτε στο διάγραμμα ότι το 9 έχει ένα παιδί.
- Διαγράψτε τον κόμβο 9 και αντικαταστήστε τον με το θυγατρικό του 10 και προσθέστε έναν σύνδεσμο από 7 έως 10
- Δείτε τη νέα δομή του BST χωρίς 9
- Εδώ θα διαγράψετε τον κόμβο 12 που έχει δύο παιδιά
- Η διαγραφή του κόμβου θα πραγματοποιηθεί με βάση τον κανόνα του προκάτοχου σειράς, που σημαίνει ότι το μεγαλύτερο στοιχείο στο αριστερό υποδένδρο του 12 θα το αντικαταστήσει.
- Διαγράψτε τον κόμβο 12 και αντικαταστήστε τον με 10, καθώς είναι η μεγαλύτερη τιμή στο αριστερό υποδένδρο
- Δείτε τη νέα δομή του BST μετά τη διαγραφή 12
- 1 Διαγράψτε έναν κόμβο 12 που έχει δύο παιδιά
- 2 Η διαγραφή του κόμβου θα πραγματοποιηθεί με βάση τον κανόνα του Διαδοχέα Εντολής, που σημαίνει ότι το μεγαλύτερο στοιχείο στο δεξιό υπότιτλο του 12 θα το αντικαταστήσει
- 3 Διαγράψτε τον κόμβο 12 και αντικαταστήστε τον με 19, καθώς είναι η μεγαλύτερη τιμή στο δεξιό υπόφυτο
- 4 Δείτε τη νέα δομή του BST μετά τη διαγραφή 12
Σημαντικοί όροι
- Εισαγωγή - Εισάγει ένα στοιχείο σε ένα δέντρο / δημιουργήστε ένα δέντρο.
- Αναζήτηση - Αναζητά ένα στοιχείο σε ένα δέντρο.
- Preorder Traversal - Διασχίζει ένα δέντρο με τρόπο προπαραγγελίας.
- Inorder Traversal - Διασχίζει ένα δέντρο με τρόπο κατά σειρά.
- Postorder Traversal - Διασχίζει ένα δέντρο με τρόπο μετά την παραγγελία.
Περίληψη
- Το BST είναι ένας προηγμένος αλγόριθμος επιπέδου που εκτελεί διάφορες λειτουργίες με βάση τη σύγκριση των τιμών κόμβων με τον ριζικό κόμβο.
- Οποιοδήποτε από τα σημεία της ιεραρχίας γονέα-παιδιού αντιπροσωπεύει τον κόμβο. Τουλάχιστον ένας γονέας ή ένας ριζικός κόμβος παραμένει παρών συνεχώς.
- Υπάρχει ένα αριστερό υποδένδρο και ένα δεξιό υποδένδρο. Το αριστερό δευτερεύον δέντρο περιέχει τιμές που είναι μικρότερες από τον ριζικό κόμβο. Ωστόσο, το δεξιό δευτερεύον δέντρο περιέχει μια τιμή που είναι μεγαλύτερη από τον ριζικό κόμβο.
- Κάθε κόμβος μπορεί να έχει είτε μηδέν, ένα ή δύο παιδιά.
- Ένα δέντρο δυαδικής αναζήτησης διευκολύνει πρωτογενείς λειτουργίες όπως αναζήτηση, εισαγωγή και διαγραφή.
- Η διαγραφή του πιο περίπλοκου έχει πολλές περιπτώσεις, για παράδειγμα, έναν κόμβο χωρίς παιδί, κόμβο με ένα παιδί και κόμβο με δύο παιδιά.
- Ο αλγόριθμος χρησιμοποιείται σε πραγματικές λύσεις όπως παιχνίδια, δεδομένα αυτόματης συμπλήρωσης και γραφικά.