Μια άλλη διαφορά μεταξύ του δέντρου B και του δυαδικού δέντρου είναι ότι το B-δέντρο πρέπει να έχει όλους τους κόμβους του παιδιού στο ίδιο επίπεδο, ενώ το δυαδικό δένδρο δεν έχει τέτοιο περιορισμό. Ένα δυαδικό δέντρο μπορεί να έχει μέγιστο 2 υποκείμενα ή κόμβους, ενώ στο Β-δέντρο μπορεί να έχει Μ όχι από υποκείμενα ή κόμβους όπου το Μ είναι η σειρά του Β-δέντρου.
Συγκριτικό διάγραμμα
| Βάση σύγκρισης | B-δέντρο | Δυαδικό δέντρο |
|---|---|---|
| Βασικός περιορισμός | Ένας κόμβος μπορεί να έχει σε μέγιστο αριθμό M αριθμό παιδικών κόμβων (όπου M είναι η σειρά του δέντρου). | Ένας κόμβος μπορεί να έχει σε max 2 αριθμό subtrees. |
| Μεταχειρισμένος | Χρησιμοποιείται όταν τα δεδομένα αποθηκεύονται στο δίσκο. | Χρησιμοποιείται όταν τα αρχεία και τα δεδομένα αποθηκεύονται στη μνήμη RAM. |
| Ύψος του δέντρου | log M N (όπου m είναι η σειρά του δέντρου M-way) | log 2 N |
| Εφαρμογή | Δομή δεδομένων ευρετηρίασης κώδικα σε πολλά ΣΔΒΔ. | Βελτιστοποίηση κώδικα, κωδικοποίηση Huffman κλπ. |
Ορισμός του B-δέντρου
Ένα B-δέντρο είναι το ισορροπημένο δέντρο M-way και είναι επίσης γνωστό ως το ισορροπημένο δέντρο ταξινόμησης. Είναι παρόμοιο με το δυαδικό δέντρο αναζήτησης όπου οι κόμβοι είναι οργανωμένοι με βάση το inorder traversal. Η χωρική πολυπλοκότητα του B-δέντρου είναι O (n). Η πολυπλοκότητα του χρόνου εισαγωγής και διαγραφής είναι O (log n).
Υπάρχουν ορισμένες προϋποθέσεις που πρέπει να ισχύουν για ένα δέντρο B:
- Το ύψος του δέντρου πρέπει να βρίσκεται στο ελάχιστο δυνατό.
- Πάνω από τα φύλλα του δέντρου, δεν πρέπει να υπάρχουν κενά υποκείμενα.
- Τα φύλλα του δέντρου πρέπει να έρχονται στο ίδιο επίπεδο.
- Όλοι οι κόμβοι θα πρέπει να έχουν τον ελάχιστο αριθμό παιδιών εκτός από τους κόμβους που αφήνουν.
Ιδιότητες του B-δένδρου της τάξης Μ
- Κάθε κόμβος μπορεί να έχει μέγιστο αριθμό M παιδιών και ελάχιστο αριθμό παιδιών M / 2 ή οποιοδήποτε αριθμό από 2 έως το μέγιστο.
- Κάθε κόμβος έχει ένα κλειδί μικρότερο από τα παιδιά με τα μέγιστα πλήκτρα M-1.
- Η διάταξη των κλειδιών είναι με κάποια συγκεκριμένη σειρά εντός των κόμβων. Όλα τα κλειδιά στο δευτερεύον τμήμα που βρίσκονται στα αριστερά του κλειδιού είναι προκατόχους του κλειδιού και εκείνο που βρίσκεται στα δεξιά του κλειδιού ονομάζονται διαδότες.
- Κατά τη στιγμή της εισαγωγής ενός πλήρους κόμβου, το δέντρο χωρίζεται σε δύο μέρη και το κλειδί με διάμεση τιμή εισάγεται στον γονικό κόμβο.
- Η συγχώνευση πραγματοποιείται όταν διαγραφούν οι κόμβοι.
Ορισμός του δυαδικού δέντρου
Ένα δυαδικό δέντρο είναι μια δομή δέντρου που μπορεί να έχει το πολύ δύο δείκτες για τους κόμβους του παιδιού. Σημαίνει ότι ο υψηλότερος βαθμός που ένας κόμβος μπορεί να έχει είναι 2 και θα μπορούσε να είναι και κόμβος μηδέν ή ενός βαθμού.
Υπάρχουν ορισμένες παραλλαγές ενός δυαδικού δέντρου, όπως το αυστηρά δυαδικό δέντρο, το πλήρες δυαδικό δέντρο, το εκτεταμένο δυαδικό δέντρο κλπ.
- Το αυστηρά δυαδικό δένδρο είναι ένα δέντρο όπου κάθε μη τερματικός κόμβος πρέπει να έχει αφήσει το subtree και το δεξί subtree.
- Ένα δέντρο ονομάζεται πλήρες δυαδικό δέντρο όταν ικανοποιεί την προϋπόθεση ότι έχουμε 2 κόμβους i σε κάθε επίπεδο όπου i είναι το επίπεδο.
- Το δυαδικό νήμα είναι ένα δυαδικό δέντρο που αποτελείται από 0 όχι κόμβων ή 2 αριθμούς κόμβων.
Τεχνικές ταχυτήτων
Η μετακίνηση των δέντρων είναι μία από τις πιο συχνές λειτουργίες που πραγματοποιήθηκαν στη δομή δεδομένων των δέντρων, όπου κάθε κόμβος επισκέφθηκε με μία συστηματική μέθοδο μία φορά.
- Inorder- Σε αυτήν την διαδρομή του δένδρου επισκέπτεται αναδρομικά το αριστερό δευτερεύον αντικείμενο, τότε επισκέπτεται ο κόμβος ρίζας και επισκέπτεται το τελευταίο δεξί δευτερεύον τμήμα.
- Preorer- Σε αυτήν την διαδρομή του δέντρου, ο κόμβος ρίζας επισκέπτεται αρχικά στη συνέχεια αριστερά στο subtree και στην τελευταία δεξιά δευτερεύουσα γραμμή.
- Postorder- Αυτή η τεχνική επισκέπτεται το αριστερό subtree, στη συνέχεια το δεξί subtree και στο τελευταίο κόμβο ρίζας.
Βασικές διαφορές μεταξύ B-tree και Binary tree
- Στο B-δέντρο, ο μέγιστος αριθμός παιδικών κόμβων που μπορεί να έχει ένας μη τερματικός κόμβος είναι M όπου M είναι η σειρά του B-δέντρου. Από την άλλη πλευρά, ένα δυαδικό δέντρο μπορεί να έχει το πολύ δύο υποκείμενα ή παιδικούς κόμβους.
- Το B-tree χρησιμοποιείται όταν τα δεδομένα αποθηκεύονται στο δίσκο ενώ το δυαδικό δέντρο χρησιμοποιείται όταν τα δεδομένα αποθηκεύονται σε γρήγορη μνήμη όπως RAM.
- Ένας άλλος τομέας εφαρμογής για το B-tree είναι η δομή δεδομένων για την ευρετηρίαση κώδικα στο ΣΔΒΔ, αντίθετα, το Δυαδικό δέντρο χρησιμοποιείται στη βελτιστοποίηση κώδικα, στην κωδικοποίηση huffman κλπ.
- Το μέγιστο ύψος ενός B-δέντρου είναι το log M N (M είναι η σειρά του δέντρου). Αντιθέτως, το μέγιστο ύψος δυαδικού δένδρου είναι log 2 N (N είναι ο αριθμός κόμβων και η βάση είναι 2 επειδή είναι για δυαδικό).
συμπέρασμα
Το B-δέντρο χρησιμοποιείται μέσω δυαδικού και δυαδικού δέντρου αναζήτησης, ο κύριος λόγος πίσω από αυτό είναι η ιεραρχία μνήμης όπου η CPU συνδέεται στην κρυφή μνήμη με τα κανάλια μεγάλου εύρους ζώνης ενώ η CPU συνδέεται στο δίσκο μέσω καναλιού χαμηλού εύρους ζώνης. Χρησιμοποιείται ένα δυαδικό δέντρο όταν τα αρχεία αποθηκεύονται σε RAM (μικρά και γρήγορα) και το B-tree χρησιμοποιούνται όταν οι εγγραφές αποθηκεύονται σε δίσκο (μεγάλο και αργό). Έτσι, η χρήση του B-tree αντί του Binary tree μειώνει σημαντικά τον χρόνο πρόσβασης λόγω του υψηλού συντελεστή διακλάδωσης και του μειωμένου ύψους του δέντρου.
