B Δομή Δέντρων και Δ + Δέντρων Δεδομένων σε C ++

b tree b tree data structure c

Αυτό το εκπαιδευτικό πρόγραμμα C ++ εξηγεί τις δομές δεδομένων δέντρων B Tree & B +. Χρησιμοποιούνται για την αποθήκευση δεδομένων σε δίσκους όταν δεν είναι δυνατή η αποθήκευση ολόκληρων δεδομένων στην κύρια μνήμη:

Το B-tree είναι ένα αυτόνομο δέντρο καθώς και ένα εξειδικευμένο δέντρο m-way που χρησιμοποιείται για πρόσβαση στο δίσκο.

Όταν η ποσότητα δεδομένων που θα αποθηκευτεί είναι πολύ υψηλή, δεν μπορούμε να αποθηκεύσουμε ολόκληρα τα δεδομένα στην κύρια μνήμη. Εξ ου και αποθηκεύουμε δεδομένα στο δίσκο. Η πρόσβαση στα δεδομένα από το δίσκο απαιτεί περισσότερο χρόνο σε σύγκριση με την κύρια πρόσβαση στη μνήμη.

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

=> Κάντε κλικ εδώ για την σειρά απόλυτης προπόνησης C ++.

Τι θα μάθετε:

• Β-δέντρο σε C ++
  • Βασικές λειτουργίες του B-Tree
    • # 1) Αναζήτηση
    • # 2) Εισαγωγή
    • # 3) Διαγραφή
  • Εφαρμογές των δέντρων Β
• B + Δέντρο σε C ++
  • Πλεονεκτήματα των δέντρων B +
• Διαφορά μεταξύ B-Tree και B + Tree
• συμπέρασμα
  • Συνιστώμενη ανάγνωση

Β-δέντρο σε C ++

Το B-Tree είναι ένα επίπεδο δέντρο, δηλαδή το ύψος του δέντρου B διατηρείται στο ελάχιστο. Αντ 'αυτού, τόσα πλήκτρα τοποθετούνται σε κάθε κόμβο του δέντρου Β. Διατηρώντας το ύψος του δέντρου Β στο ελάχιστο, η πρόσβαση είναι ταχύτερη σε σύγκριση με άλλα ισορροπημένα δέντρα όπως τα δέντρα AVL.

Ένα τυπικό δέντρο B φαίνεται παρακάτω:

πώς να διαβάσετε ένα αρχείο .bin

Γενικά, το μέγεθος κόμβου στο δέντρο B διατηρείται το ίδιο με το μέγεθος μπλοκ.

Παρακάτω αναφέρονται μερικές από τις ιδιότητες του B-Tree.

• Όλα τα φύλλα του B-tree είναι στο ίδιο επίπεδο.
• Ένα B-δέντρο της τάξης m μπορεί να έχει το πολύ m-1 κλειδιά και m παιδιά.
• Κάθε κόμβος στο B-tree έχει το πολύ m παιδιά.
• Ο ριζικός κόμβος πρέπει να έχει τουλάχιστον δύο κόμβους.
• Κάθε κόμβος εκτός του ριζικού κόμβου και του κόμβου φύλλων περιέχει m / 2 παιδιά.

Στη συνέχεια, συζητάμε μερικές από τις βασικές λειτουργίες του B-tree.

Βασικές λειτουργίες του B-Tree

Παρακάτω δίνονται μερικές από τις Βασικές λειτουργίες του B-Tree.

# 1) Αναζήτηση

Η αναζήτηση στο δέντρο B είναι παρόμοια με αυτήν στο BST. Στο παραπάνω δέντρο αν θέλουμε να αναζητήσουμε το στοιχείο 3, τότε θα προχωρήσουμε ως εξής:

• Συγκρίνετε 3 με ριζικά στοιχεία. Εδώ, 3<6 and 3 <15. So we proceed to the left subtree.
• Συγκρίνετε 3 με 4 στο αριστερό υποδένδρο. Ως 3<4, we proceed to the left subtree of node 4.
• Ο επόμενος κόμβος έχει δύο πλήκτρα, 2 και 3. 3> 2 ενώ 3 = 3. Βρήκαμε λοιπόν το κλειδί σε αυτόν τον κόμβο. Επιστροφή στην τοποθεσία που βρέθηκε.

Η αναζήτηση στο δέντρο B εξαρτάται από το ύψος του δέντρου. Χρειάζεται συνήθως O (log n) χρόνος για την αναζήτηση ενός δεδομένου αντικειμένου.

# 2) Εισαγωγή

Η εισαγωγή ενός νέου αντικειμένου στο δέντρο Β γίνεται στο επίπεδο των κόμβων των φύλλων.

Ακολουθεί η ακολουθία των βημάτων (αλγόριθμος) για την εισαγωγή ενός νέου αντικειμένου στο δέντρο B.

• Περάστε το δέντρο Β για να βρείτε μια θέση στους κόμβους των φύλλων για να εισαγάγετε το αντικείμενο.
• Εάν ο κόμβος φύλλων περιέχει κλειδιά
• Διαφορετικά, εάν τα πλήκτρα κόμβου φύλλου = m-1, τότε:
  • Εισαγάγετε ένα νέο αντικείμενο σε έναν αυξανόμενο αριθμό αντικειμένων.
  • Πάρτε τη μέση τιμή των κόμβων και χωρίστε τον κόμβο σε δύο κόμβους.
  • Σπρώξτε τη διάμεση στον γονικό κόμβο.
  • Εάν το κλειδί γονικού κόμβου = m-1, επαναλάβετε τα παραπάνω βήματα και για τον γονικό κόμβο. Αυτό γίνεται μέχρι να βρούμε τον κατάλληλο κόμβο φύλλων.
• Τέλος, εισαγάγετε το στοιχείο.

Έχουμε δείξει την εισαγωγή στο δέντρο Β ως εξής.

Ας εισαγάγουμε το στοιχείο 70 στο δέντρο που φαίνεται παρακάτω.

Η προεπιλεγμένη πύλη των Windows 10 δεν είναι διαθέσιμη

Το δεδομένο δέντρο είναι με ελάχιστο βαθμό «m» = 3. Επομένως, κάθε κόμβος μπορεί να φιλοξενήσει, 2 * m -1 = 5 πλήκτρα μέσα σε αυτό.

Τώρα εισάγουμε το στοιχείο 70. Καθώς μπορούμε να έχουμε 5 κλειδιά σε έναν κόμβο, συγκρίνουμε το στοιχείο 70 με το ριζικό στοιχείο 30. Από το 70> 30, θα εισαγάγουμε το στοιχείο 70 στο δεξιό υπόφυτο.

Στο δεξιό υποδένδρο, έχουμε έναν κόμβο με τα πλήκτρα 40, 50, 60. Καθώς κάθε κόμβος μπορεί να έχει 5 πλήκτρα σε αυτό, θα εισαγάγουμε το ίδιο το στοιχείο 70 σε αυτόν τον κόμβο.

Μετά την εισαγωγή, το B-Tree φαίνεται ως εξής.

# 3) Διαγραφή

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

Για να διαγράψουμε ένα κλειδί, ακολουθούμε την παρακάτω ακολουθία βημάτων (αλγόριθμος).

1. Εντοπίστε τον κόμβο των φύλλων.

δύο. Σε περίπτωση που ο αριθμός των κλειδιών σε έναν κόμβο> m / 2, τότε διαγράψτε το δεδομένο κλειδί από τον κόμβο.

3. Σε περίπτωση που ο κόμβος των φύλλων δεν έχει πλήκτρα m / 2, τότε πρέπει να ολοκληρώσουμε τα πλήκτρα λαμβάνοντας κλειδιά από τα δεξιά ή αριστερά υποδέντρα για να διατηρήσουμε το δέντρο Β.

Ακολουθούμε αυτά τα βήματα:

• Εάν το αριστερό δευτερεύον δέντρο περιέχει στοιχεία m / 2 τότε πιέζουμε το μεγαλύτερο στοιχείο του στον γονικό κόμβο και μετά μεταφέρουμε το παρεμβαλλόμενο στοιχείο στο σημείο όπου διαγράφηκε το κλειδί.
• Εάν το δεξιό υπόστρωμα περιέχει στοιχεία m / 2, τότε σπρώχνουμε το μικρότερο στοιχείο του στον γονικό κόμβο και μετά μεταφέρουμε το παρεμβαλλόμενο στοιχείο στο σημείο όπου διαγράφηκε το κλειδί.

Τέσσερις. Εάν κανένας κόμβος δεν έχει κόμβους m / 2, τότε τα παραπάνω βήματα δεν μπορούν να εκτελεστούν, επομένως δημιουργούμε έναν νέο κόμβο φύλλων συνδέοντας δύο κόμβους φύλλων και το παρεμβαλλόμενο στοιχείο του γονικού κόμβου.

5. Εάν ένας γονέας δεν έχει κόμβους m / 2, τότε επαναλαμβάνουμε τα παραπάνω βήματα για τον εν λόγω κόμβο γονέα. Αυτά τα βήματα επαναλαμβάνονται μέχρι να πάρουμε ένα ισορροπημένο δέντρο Β.

Δίνεται παρακάτω μια απεικόνιση για τη διαγραφή ενός κόμβου από το δέντρο B.

Εξετάστε ξανά το ακόλουθο δέντρο Β.

Ας υποθέσουμε ότι θέλουμε να διαγράψουμε το κλειδί 60 από το δέντρο Β. Εάν ελέγξουμε το δέντρο B, μπορούμε να διαπιστώσουμε ότι το κλειδί που πρέπει να διαγραφεί υπάρχει στον κόμβο των φύλλων. Διαγράφουμε το κλειδί 60 από αυτόν τον κόμβο.

Τώρα το δέντρο θα φαίνεται όπως φαίνεται παρακάτω:

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

Ωστόσο, εάν έπρεπε να διαγράψουμε το κλειδί 20, τότε μόνο το κλειδί 10 θα είχε παραμείνει στον αριστερό κόμβο. Σε αυτήν την περίπτωση, θα πρέπει να μετατοπίσουμε τη ρίζα 30 στον κόμβο των φύλλων και να μετακινήσουμε το κλειδί 40 στη ρίζα.

Έτσι, ενώ διαγράφετε ένα κλειδί από το δέντρο Β, πρέπει να προσέχετε και να μην παραβιάζετε τις ιδιότητες του δέντρου Β.

Διασχίζοντας στο δέντρο Β

Η διέλευση στο δέντρο Β είναι επίσης παρόμοια με την εγκάρσια διέλευση στο BST. Ξεκινάμε αναδρομικά από τα αριστερά και μετά μπαίνουμε στη ρίζα και προχωράμε προς το αριστερό υπόστρωμα.

Εφαρμογές των δέντρων Β

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

B + Δέντρο σε C ++

Το δέντρο B + είναι προέκταση του δέντρου Β. Η διαφορά στο δέντρο Β + και το δέντρο Β είναι ότι στο δέντρο Β τα κλειδιά και οι εγγραφές μπορούν να αποθηκευτούν τόσο εσωτερικά όσο και κόμβοι φύλλων ενώ στα δέντρα Β +, οι εγγραφές αποθηκεύονται ως κόμβοι φύλλων και τα κλειδιά αποθηκεύονται μόνο σε εσωτερικούς κόμβους.

Οι δίσκοι συνδέονται μεταξύ τους με τρόπο συνδεδεμένης λίστας. Αυτή η ρύθμιση κάνει τις αναζητήσεις των δέντρων Β + ταχύτερες και αποτελεσματικότερες. Οι εσωτερικοί κόμβοι του δέντρου B + καλούνται κόμβοι ευρετηρίου.

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

Ένα παράδειγμα δέντρου B + φαίνεται παρακάτω.

Δεδομένου ότι το δέντρο B + είναι μια επέκταση του δέντρου Β, οι βασικές λειτουργίες που συζητήσαμε στο θέμα B-tree εξακολουθούν να ισχύουν.

τι κάνει το c ++

Κατά την εισαγωγή καθώς και τη διαγραφή, πρέπει να διατηρούμε ανέπαφες τις βασικές ιδιότητες των δέντρων B +. Ωστόσο, η λειτουργία διαγραφής στο δέντρο B + είναι συγκριτικά ευκολότερη καθώς τα δεδομένα αποθηκεύονται μόνο στους κόμβους των φύλλων και θα διαγράφονται πάντα από τους κόμβους των φύλλων.

Πλεονεκτήματα των δέντρων B +

• Μπορούμε να πάρουμε εγγραφές σε ίσο αριθμό προσβάσεων δίσκου.
• Σε σύγκριση με το δέντρο Β, το ύψος του δέντρου Β + είναι μικρότερο και παραμένει ισορροπημένο.
• Χρησιμοποιούμε κλειδιά για ευρετηρίαση.
• Τα δεδομένα στο δέντρο B + μπορούν να προσπελαστούν διαδοχικά ή άμεσα καθώς οι κόμβοι των φύλλων είναι διατεταγμένοι σε μια συνδεδεμένη λίστα.
• Η αναζήτηση είναι ταχύτερη καθώς τα δεδομένα αποθηκεύονται μόνο σε κόμβους φύλλων και ως συνδεδεμένη λίστα.

Διαφορά μεταξύ B-Tree και B + Tree

συμπέρασμα

Σε αυτό το σεμινάριο, συζητήσαμε λεπτομερώς το B-tree και το B + tree. Αυτές οι δύο δομές δεδομένων χρησιμοποιούνται όταν υπάρχει πολύ μεγάλη ποσότητα δεδομένων και όταν ολόκληρα τα δεδομένα δεν μπορούν να αποθηκευτούν στην κύρια μνήμη. Έτσι, για την αποθήκευση δεδομένων σε δίσκους, χρησιμοποιούμε το δέντρο B-tree και το B +.

Η αναζήτηση B-tree είναι ελαφρώς πιο αργή καθώς τα δεδομένα αποθηκεύονται σε εσωτερικούς κόμβους καθώς και σε κόμβους φύλλων σε αυτό. Το δέντρο B + είναι μια επέκταση του δέντρου Β και τα δεδομένα εδώ αποθηκεύονται μόνο σε κόμβους φύλλων. Λόγω αυτού του παράγοντα, η αναζήτηση σε δέντρο B + είναι πιο γρήγορη και αποτελεσματική.

=> Επισκεφθείτε εδώ για την πλήρη λίστα μαθημάτων C ++.

Συνιστώμενη ανάγνωση

• Δομή δεδομένων δέντρων και σωρού AVL σε C ++
• Δομή δεδομένων συνδεδεμένης λίστας σε C ++ με απεικόνιση
• Δομή δεδομένων ουράς σε C ++ με απεικόνιση
• Δομή δεδομένων στοίβας σε C ++ με απεικόνιση
• Δομή δεδομένων κυκλικής συνδεδεμένης λίστας σε C ++ με απεικόνιση
• Εισαγωγή στις δομές δεδομένων στο C ++
• Δομή δεδομένων ουράς προτεραιότητας σε C ++ με απεικόνιση
• Διπλά συνδεδεμένη δομή δεδομένων λίστας σε C ++ με απεικόνιση