Περιεχόμενο

• Περιεχόμενο: Διαφορά μεταξύ B-δέντρου και Δυαδικού δέντρου
• Συγκριτικό διάγραμμα
• B-δέντρο
• Δυαδικό Δέντρο
• Βασικές διαφορές
• συμπέρασμα
• Επεξηγηματικό βίντεο

Η διαφορά μεταξύ του B-tree και ενός δυαδικού δέντρου είναι ότι το B-tree είναι ένα ταξινομημένο δέντρο όπου οι κόμβοι ταξινομούνται inorder traversal ενώ το δυαδικό δέντρο είναι ένα διατεταγμένο δέντρο που έχει δείκτη σε κάθε κόμβο.

Οι δομές δεδομένων είναι οι πιο σημαντικές έννοιες στον προγραμματισμό υπολογιστών και στις δομές δεδομένων οι δύο πιο σημαντικές έννοιες είναι το δέντρο B και το δίδυμο δέντρο. Και οι δύο είναι διαφορετικές μεταξύ τους. Το B-δέντρο είναι ένα ταξινομημένο δέντρο όπου οι κόμβοι ταξινομούνται με διασταύρωση προκειμένου, ενώ το δυαδικό δέντρο είναι ένα ταξινομημένο δέντρο που έχει δείκτη σε κάθε κόμβο. Το B-tree και το δυαδικό δέντρο είναι μη γραμμικές δομές δεδομένων. Από το όνομα, και οι δύο όροι φαίνεται να είναι ίδιοι, αλλά δεν είναι οι ίδιοι με τους διαφορετικούς. Ένας δυαδικός κώδικας δέντρου αποθηκεύεται στη μνήμη RAM ενώ ένας κωδικός B-tree αποθηκεύεται στο δίσκο.

Το B-tree είναι ένα δέντρο M-way που είναι ισορροπημένο, το B-tree είναι γνωστό σαν ισορροπημένο δέντρο ταξινόμησης. Υπάρχει διαμετακόμιση στο B-δέντρο. Η χωρική πολυπλοκότητα του B-δέντρου είναι O (n). Η πολυπλοκότητα του χρόνου εισαγωγής και διαγραφής είναι O (log n). Στο B-δέντρο, το ύψος του δέντρου πρέπει να είναι το ελάχιστο δυνατό. Στο B-δέντρο, δεν πρέπει να υπάρχει κενή υποδία. Όλα τα φύλλα του δέντρου πρέπει να βρίσκονται στο ίδιο επίπεδο. Κάθε κόμβος μπορεί να έχει μέγιστο αριθμό M παιδιών και ελάχιστο αριθμό παιδιών M / 2. Κάθε κόμβος στο B-δέντρο θα πρέπει να έχει μικρότερο κλειδί από το κλειδί του παιδιού. Στο B-δέντρο, τα κλειδιά στο δευτερεύον τμήμα που υπάρχουν στα αριστερά του κλειδιού είναι προκατόχους. Όταν ένας κόμβος είναι γεμάτος και προσπαθείτε να εισάγετε έναν νέο κόμβο, το δέντρο χωρίζεται σε δύο μέρη. Μπορείτε να συγχωνεύσετε κόμβους στο B-tree μέχρι να διαγραφούν οι κόμβοι.

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

Περιεχόμενο: Διαφορά μεταξύ B-δέντρου και Δυαδικού δέντρου

• Συγκριτικό διάγραμμα
• B-δέντρο
• Δυαδικό Δέντρο
• Βασικές διαφορές
• συμπέρασμα
• Επεξηγηματικό βίντεο

Συγκριτικό διάγραμμα

B-δέντρο

Το B-tree είναι ένα δέντρο M-way που είναι ισορροπημένο, το B-tree είναι γνωστό σαν ισορροπημένο δέντρο ταξινόμησης. Υπάρχει διαμετακόμιση στο B-δέντρο. Η χωρική πολυπλοκότητα του B-δέντρου είναι O (n). Η πολυπλοκότητα του χρόνου εισαγωγής και διαγραφής είναι O (log n). Στο B-δέντρο, το ύψος του δέντρου πρέπει να είναι το ελάχιστο δυνατό.

Στο B-δέντρο, δεν πρέπει να υπάρχει κενή υποδία. Όλα τα φύλλα του δέντρου πρέπει να βρίσκονται στο ίδιο επίπεδο. Κάθε κόμβος μπορεί να έχει μέγιστο αριθμό M παιδιών και ελάχιστο αριθμό παιδιών M / 2. Κάθε κόμβος στο B-δέντρο θα πρέπει να έχει μικρότερο κλειδί από το κλειδί του παιδιού. Στο B-δέντρο, τα κλειδιά στο δευτερεύον τμήμα που υπάρχουν στα αριστερά του κλειδιού είναι προκατόχους. Όταν ένας κόμβος είναι γεμάτος και προσπαθείτε να εισάγετε έναν νέο κόμβο, το δέντρο χωρίζεται σε δύο μέρη. Μπορείτε να συγχωνεύσετε κόμβους στο B-tree μέχρι να διαγραφούν οι κόμβοι.

Δυαδικό Δέντρο

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

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

Βασικές διαφορές

1. Το B-δέντρο είναι ένα ταξινομημένο δέντρο όπου οι κόμβοι ταξινομούνται inorder traversal, ενώ το Binary tree είναι ένα διατεταγμένο δέντρο που έχει δείκτη σε κάθε κόμβο.
2. Ο κώδικας B-tree αποθηκεύεται στο δίσκο ενώ ο δυαδικός κώδικας δέντρου αποθηκεύεται στη μνήμη RAM.
3. Το ύψος του B-tree θα είναι logN ενώ το ύψος του δυαδικού δέντρου θα είναι log₂ Ν
4. Το DBMS είναι η εφαρμογή του B-tree ενώ η κωδικοποίηση Huffman είναι μια εφαρμογή Binary Tree.

συμπέρασμα

Σε αυτό το άρθρο, βλέπουμε τη σαφή διαφορά μεταξύ του B-tree και του Binary tree με την υλοποίησή τους.

Επεξηγηματικό βίντεο