Σε αυτό το άρθρο, θα δούμε τη διαφορά μεταξύ του Δυαδικού Δέντρου και του Δυαδικού Δέντρου αναζήτησης. Θα εξετάσουμε επίσης τις βασικές λειτουργίες και την πολυπλοκότητα του χρόνου και του χώρου τους. Στη συνέχεια θα δούμε τις πραγματικές εφαρμογές που χρησιμοποιούν αυτές τις δύο δομές δεδομένων.
1. Τι είναι ένα Δυαδικό Δέντρο;
Ένα δυαδικό δέντρο είναι μια μη γραμμική (η μνήμη εκχωρείται τυχαία) δομή δεδομένων δέντρου και αναπαρίσταται με τρόπο από πάνω προς τα κάτω, όπου ο επάνω κόμβος ονομάζεται Ρίζα. Είναι μια συλλογή κόμβων και είναι μια μη διατεταγμένη δομή δεδομένων. Κάθε κόμβος σε ένα Δυαδικό δέντρο μπορεί να έχει το πολύ δύο (0,1 ή 2) παιδιά, που ονομάζονται Αριστερά και σωστά παιδί. Οι κόμβοι που έχουν θυγατρικούς κόμβους ονομάζονται α Μητρική εταιρεία κόμβος και ονομάζονται οι κόμβοι που δεν έχουν παιδιά Φύλλο node.Ακολουθούν οι 3 κύριες ιδιότητες:
- Δεδομένα – τα δεδομένα στον κόμβο, οποιοσδήποτε τύπος δεδομένων.
- Αριστερός δείκτης – που δείχνει στο Αριστερό παιδί.
- Δεξιός δείκτης – που δείχνει το Δεξί παιδί.
Οπτική αναπαράσταση
1.1. Λειτουργίες σε δυαδικό δέντρο με πολυπλοκότητες:
- Αναζήτηση: Δεδομένου ότι το Δυαδικό Δέντρο δεν είναι ταξινομημένο, για να αναζητήσουμε ένα στοιχείο πρέπει να διασχίσουμε όλους τους κόμβους του δέντρου. Η χρονική πολυπλοκότητα για την αναζήτηση θα είναι O(n).
- Εισάγετε: Εφόσον το ένθετο μπορεί να συμβεί και στον τελευταίο κόμβο του δέντρου, επομένως, πρέπει να διασχίσουμε όλους τους κόμβους του δέντρου. Άρα, η συνολική πολυπλοκότητα θα είναι O(n).
- Διαγράφω: Εφόσον η διαγραφή ενός κόμβου από ένα Δυαδικό Δέντρο απαιτεί πρώτα την αναζήτηση του κόμβου μεταξύ όλων των κόμβων του Δυαδικού Δέντρου, επομένως, η συνολική πολυπλοκότητα θα είναι O(n).
2. Τι είναι ένα Δυαδικό Δέντρο Αναζήτησης
Ένα Δυαδικό Δέντρο Αναζήτησης (BST) είναι ένας ειδικός τύπος Δυαδικού Δέντρου, ωστόσο, σε αντίθεση με το Δυαδικό Δέντρο, οι κόμβοι σε ένα Δυαδικό Δέντρο Αναζήτησης είναι διατεταγμένοι με προκαθορισμένη σειρά. Η δομή παραμένει όπως έχει παραγγελθεί. Οι ακόλουθες προϋποθέσεις πρέπει να ισχύουν για ένα BST:
- Τα δεδομένα του αριστερού κόμβου θα πρέπει να είναι μικρότερα από την τιμή του γονικού του κόμβου.
- Τα δεδομένα του δεξιού κόμβου πρέπει να είναι μεγαλύτερα από την τιμή του γονικού του κόμβου.
- Το αριστερό και το δεξί υποδέντρο είναι BST από μόνα τους.
- Δεν επιτρέπονται διπλότυπα κλειδιά ή τιμές.
Οπτική αναπαράσταση
2.1. Λειτουργίες σε Δυαδικό Δέντρο Αναζήτησης με Πολυπλοκότητες:
Η κύρια ιδέα πίσω από τη δομή δεδομένων BST είναι η βελτιστοποίηση των λειτουργιών αναζήτησης (αναζήτησης). Κατά την αναζήτηση ενός στοιχείου στο BST, αφαιρούμε το ένα μισό (αριστερά ή δεξιά) σε κάθε βήμα λόγω των ιδιοτήτων του. Σε κάθε βήμα, θα μειώσουμε τον χώρο αναζήτησης κατά n/2 (για ένα δέντρο με n κόμβους) και θα συνεχίσει μέχρι να βρεθεί ένα στοιχείο.
- Αναζήτηση: Σύμφωνα με την παραπάνω περιγραφή, η αναζήτηση ενός στοιχείου σε ένα Δυαδικό Δέντρο Αναζήτησης χρειάζεται γενικά
O(log n). Στην περίπτωση ενός Skewed BST, η χειρότερη χρονική πολυπλοκότητα θα ήτανO(n). - Εισάγετε: Για ένα λοξό δέντρο, η χειρότερη χρονική πολυπλοκότητα θα ήταν
O(n)για την εισαγωγή ενός στοιχείου. - Διαγράφω: Για ένα λοξό δέντρο, η χειρότερη χρονική πολυπλοκότητα θα ήταν
O(n)για τη διαγραφή ενός στοιχείου.
3. Διαφορά μεταξύ Binary Tree και Binary Search Tree
Εδώ υπάρχει μια διαφορά υψηλού επιπέδου μεταξύ του Δυαδικού Δέντρου και του Δυαδικού Δέντρου αναζήτησης.
| Δυαδικό δέντρο | Δυαδικό δέντρο αναζήτησης |
|---|---|
| Το δέντρο όπου κάθε κόμβος έχει έως δύο φύλλα, είναι μια δομή δεδομένων. | Δυαδικό δέντρο αναζήτησης: Χρησιμοποιείται για αναζήτηση. Είναι ένας αλγόριθμος για αναζήτηση στοιχείου. |
| Είναι μια μη γραμμική δομή δεδομένων δέντρου όπου ένας κόμβος μπορεί να έχει το πολύ 2 παιδιά. | Είναι διατεταγμένο δυαδικό δέντρο με κάθε κόμβο μπορεί να έχει το πολύ 2 παιδιά. |
| Δεν υπάρχει παραγγελία και οποιοσδήποτε κόμβος μπορεί να προστεθεί σε οποιονδήποτε γονικό κόμβο. | Στο BST, τα δεδομένα του αριστερού παιδιού θα έχουν πάντα τιμή μικρότερη από τα δεδομένα του γονέα και τα δεδομένα του δεξιού παιδιού θα έχουν πάντα την τιμή μεγαλύτερη από τα δεδομένα του γονέα |
| Επιτρέπονται κόμβοι με διπλότυπες τιμές. | Δεν επιτρέπονται κόμβοι με διπλότυπες τιμές. |
Η χρονική πολυπλοκότητα είναι συνήθως O(n) |
Η χρονική πολυπλοκότητα είναι συνήθως O(log n) |
| Χρησιμοποιείται για την υλοποίηση παραλλαγών του Binary Tree όπως BST, Perfect Binary Tree, κ.λπ. | Χρησιμοποιείται για την υλοποίηση παραλλαγών Balanced Binary Trees όπως AVL, Red-Black, κ.λπ. |
3.1. Ομοιότητες
Αν και υπάρχουν πολλές διαφορές μεταξύ του Δυαδικού Δέντρου και του Δυαδικού Δέντρου αναζήτησης, ωστόσο το δυαδικό δέντρο αναζήτησης βασίζεται στη δομή δεδομένων δυαδικού δέντρου και υπάρχουν πολλές ομοιότητες μεταξύ των δύο.
- Και τα δύο βασίζονται στη δομή δεδομένων Tree.
- Και οι δύο μπορούν να έχουν έως 2 θυγατρικούς κόμβους.
- Και τα δύο μπορούν να κρατούν διαφορετικούς τύπους δεδομένων.
- Και οι δύο έχουν τυχαία μνήμη που τους έχει εκχωρηθεί.
4. Εφαρμογές δυαδικού δέντρου:
4.1. Εφαρμογές Δυαδικής Δενδρικής Αναζήτησης:
- Σε σχεσιακές βάσεις δεδομένων, τα BST μπορούν να χρησιμοποιηθούν για ευρετηρίαση και ευρετηρίαση πολλαπλών επιπέδων.
- Υπάρχουν διάφοροι αλγόριθμοι αναζήτησης που βασίζονται στο BST.
- Είναι χρήσιμο για τη διατήρηση μιας ταξινομημένης ροής δεδομένων.
- TreeMap και TreeSet – χρησιμοποιεί το BST εσωτερικά.
- Ο αλγόριθμος κωδικοποίησης Huffman βασίζεται στο BST.
- Το BST χρησιμοποιείται σε πυρήνες UNIX για τη διαχείριση ενός συνόλου περιοχών εικονικής μνήμης (VMA).
- Δυαδικοί σωροί – χρησιμοποιείται για την υλοποίηση ουρών προτεραιότητας.
- Δέντρα απόφασης – χρησιμοποιείται στη μηχανική μάθηση για ταξινόμηση.
- Β+ δέντρα – χρησιμοποιείται σε ευρετήρια βάσεων δεδομένων
Περίληψη
- Σε αυτό το άρθρο, μάθαμε τι είναι ένα Δυαδικό δέντρο και τι είναι ένα Δυαδικό δέντρο αναζήτησης
- Σε αυτό το άρθρο, μάθαμε τις λειτουργίες ενός Δυαδικού δέντρου και ενός Δυαδικού δέντρου αναζήτησης
- Σε αυτό το άρθρο, μάθαμε τη διαφορά μεταξύ Binary Tree και Binary Search Tree
- Σε αυτό το άρθρο, μάθαμε τις ομοιότητες μεταξύ ενός Δυαδικού δέντρου και ενός Δυαδικού δέντρου αναζήτησης
- Σε αυτό το άρθρο, μάθαμε επίσης τις πραγματικές εφαρμογές ενός δυαδικού δέντρου και ενός δυαδικού δέντρου αναζήτησης
