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

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

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

Από όλες τις εργασίες που κάνουν οι εφαρμογές, η αναζήτηση είναι πιο χρονοβόρος και επίσης απαιτεί περισσότερο. Παρόλο που η προσθήκη δεδομένων (και η ταξινόμησή τους αργότερα) απαιτεί κάποιο χρονικό διάστημα, το όφελος στη δημιουργία και τη διατήρηση ενός συνόλου δεδομένων προέρχεται από τη χρήση του για την εκτέλεση χρήσιμης εργασίας, που σημαίνει ότι ψάχνει για σημαντικές πληροφορίες. Κατά συνέπεια, μπορείτε μερικές φορές να περάσετε με λιγότερο αποτελεσματική λειτουργικότητα CRUD και ακόμη και μια λιγότερο από βέλτιστη ρουτίνα ταξινόμησης, αλλά οι αναζητήσεις πρέπει να προχωρήσουν όσο πιο αποτελεσματικά γίνεται. Το μόνο πρόβλημα είναι ότι καμία αναζήτηση δεν εκτελεί κάθε εργασία με απόλυτη απόδοση, οπότε πρέπει να σταθμίσετε τις επιλογές σας με βάση αυτό που περιμένετε να κάνετε ως μέρος των ρουτινών αναζήτησης.

Δύο από τις αποδοτικότερες μεθόδους αναζήτησης περιλαμβάνουν τη χρήση του δυαδικού δέντρου αναζήτησης (BST) και του δυαδικού σωρού. Και οι δύο τεχνικές αναζήτησης βασίζονται σε μια δομή που μοιάζει με δέντρο για να κρατάει τα κλειδιά που χρησιμοποιούνται για την πρόσβαση στα στοιχεία δεδομένων. Ωστόσο, η διευθέτηση των δύο μεθόδων είναι διαφορετική, γι 'αυτό υπάρχει πλεονέκτημα έναντι του άλλου κατά την εκτέλεση ορισμένων καθηκόντων. Αυτό το σχήμα δείχνει τη διάταξη για ένα BST.

Η διάταξη πλήκτρων όταν χρησιμοποιείτε ένα BST.

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

Η διάταξη κλειδιών όταν χρησιμοποιείτε δυαδικό σωρό.

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

Η αναζήτηση ενός στοιχείου απαιτεί χρόνο O (log n), σε αντίθεση με τον χρόνο O (n) για ένα δυαδικό σωρό.

• Η εκτύπωση των στοιχείων σε σειρά απαιτεί μόνο χρόνο O (log n), σε αντίθεση με τον χρόνο O (n log n) για έναν δυαδικό σωρό.
• Η εύρεση του δαπέδου και της οροφής απαιτεί χρόνο O (log n).
• Η ανίχνευση του μικρότερου / μεγαλύτερου στοιχείου Kth απαιτεί χρόνο O (log n) όταν το δέντρο έχει διαμορφωθεί σωστά.
• Η σημασία αυτών των χρόνων εξαρτάται από την εφαρμογή σας. Το BST τείνει να λειτουργεί καλύτερα σε καταστάσεις όπου περνάτε περισσότερο χρόνο για αναζήτηση και λιγότερο χρόνο για την οικοδόμηση του δέντρου. Ένας δυαδικός σωρός τείνει να λειτουργεί καλύτερα σε δυναμικές καταστάσεις στις οποίες τα πλήκτρα αλλάζουν τακτικά. Ο δυαδικός σωρός προσφέρει επίσης πλεονεκτήματα όπως περιγράφεται στον παρακάτω κατάλογο:

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

• Η δημιουργία ενός δυαδικού σωρού απαιτεί O (n) χρόνο, σε αντίθεση με BST, που απαιτεί χρόνο O (n log n).
• Η χρήση των δεικτών για την υλοποίηση του δέντρου δεν είναι απαραίτητη.
• Με βάση τις δυαδικές παραλλαγές σωρού (για παράδειγμα, το Fibonacci Heap) προσφέρει πλεονεκτήματα όπως η αύξηση και η μείωση των βασικών χρόνων του χρόνου O (1).