DataStructures: B-Tree-Theory

Β-Δέντρα

Τα Β-Δέντρα είναι μερική περίπτωση των πολυκατευθυνόμενων δέντρων. Ένα δέντρο τάξης n είναι το δέντρο που έχει τα παρακάτω χαρακτηριστικά:

Τυπικός κόμβος Β-Δέντρου με m κλειδιά.

Η έννοια του κόμβου προέρχεται από τον ορισμό του δέντρου. Στα Β-Δέντρα χρησιμοποιείται και ο όρος σελίδα ταυτόσημα με τον κόμβο. Στο παρακάτω κείμενο μπορεί να χρησιμοποιηθεί ο ένας ή ο άλλος όρος σημαίνοντας όμως πάντα το ίδιο, δηλαδή, ένα κόμβο Β-Δέντρου.

Εισαγωγή

Διακρίνουμε δύο περιπτώσεις στην εισαγωγή ενός κλειδιού:

  1. Αν η σελίδα έχει λιγότερα από 2n τότε το κλειδί παρεμβάλλεται στα υπόλοιπα της σελίδας έτσι ώστε όλα να είναι ταξινομημένα σε αύξουσα σειρά.
  2. Αν η σελίδα είναι γεμάτη, τότε γίνεται διάσπαση της σελίδας.

Η διάσπαση της σελίδας γίνεται με της εξής διαδικασία:

Παράδειγμα

Θα δημιουργήσουμε ένα Β-δέντρο με διαδοχική εισαγωγή των κλειδιών:

20, 40, 10, 30, 15, 35, 7, 26, 18, 22, 5, 42, 13, 46, 27, 8, 32, 38, 24, 45, 25

Η εισαγωγή ενός στοιχείου σε μία σελίδα γίνεται με ταξινόμηση των αριθμών σε αύξουσα σειρά.
Με την εισαγωγή αυτή γεμίζει η πρώτη σελίδα.
Η εισαγωγή του κλειδιού 15 δεν μπορεί να γίνει στην σελίδα. Η διαδικασία που ακολουθούμε είναι:
Τα κλειδιά αυτά εισάγωνται στις αντίστοιχες σελίδες. Προσέξτε ότι παρόλο που αρχική σελίδα έχει λιγότερα από 2 στοιχεία η εισαγωγή γίνεται στις χαμηλότερες σελίδες.
Το 22 θα έπρεπε να τοποθετηθεί στη δεξιά σελίδα του δευτέρου επιπέδου. Αυτό όμως δεν μπορεί να γίνει γιατί η σελίδα είναι πλήρης. Η διαδικασία που θα ακολουθήσουμε είναι:
Αυτή τη φορά γίνεται διάσπαση της αριστερής σελίδας του δεύτερου επιπέδου. Η λογική είναι όπως η προηγούμενη.
Εδώ έχουμε μία ακόμη διάσπαση σελίδας του δευτέρου επιπέδου. Τα κλειδιά που εμπλέκονται είναι: 32, 35, 40, 42, 25
Τα κλειδιά μπαίνουν στις αντίστοιχες σελίδες.
Η εισαγωγή του κλειδιού αυτή θα πρέπει να γίνει στη μεσαία σελίδα του δευτέρου επιπέδου. Τα εμπλεκόμενα κλειδιά είναι τα 22, 24, 25, 26, 27. Το κλειδί 25 θα ανέβει στην από πάνω σελίδα και τα υπόλοιπα θα φτιάξουν δύο σελίδες. Επειδή, όμως, και η από πάνω σελίδα είναι γεμάτη, θα πρέπει να γίνει διάσπαση και εκεί. Έχουμε, δηλαδή:

Διαγραφή

Ο αλγόριθμος για τη διαγραφή κλειδιών είναι όμοιος με εκείνον της διαγραφής από τα AVL δέντρα. Όταν ένα κλειδί διαγράφεται από έναν κόμβο είναι πιθανόν ότι ο αριθμός των κλειδιών που παραμένουν είναι μικρότερος από n. Σ' αυτήν την περίπτωση πρέπει να γίνει εξισορρόπηση.

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

Διακρίνουμε δύο περιπτώσεις:

  1. το κλειδί να ανήκει σε εσωτερικό κόμβο, και,
  2. το κλειδί να ανήκει σε τερματικό κόμβο

Η πρώτη περίπτωση, αφού γίνει πρώτα μία μετακίνηση κλειδιού, ανάγεται στη δεύτερη.

Διαγραφή από Εσωτερικό Κόμβο

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

Για να βρούμε το αμέσως μεγαλύτερο:

Για να βρούμε το αμέσως μικρότερο:

Το πιο κλειδί από τα δύο θα χρησιμοποιήσουμε δεν έχει σημασία αφού και με τις δύο περιπτώσεις διατηρούνται οι ιδιότητες των Β-Δέντρων. Αρκεί, όμως, να διαλέξουμε τη μία από τις δύο διαδικασίες και να "κολλήσουμε" σ' αυτή.

Εμείς, στο παράδειγμα που ακολουθεί, βρίσκουμε το μεγαλύτερο.

Διαγραφή από Τερματικό Κόμβο

Δεδομένου ενός κόμβου Τ:

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


      Αν ο κόμβος Τ τύχει να έχει κόμβους και δεξιά και αριστερά οι οποίοι να έχουν περισσότερα από n κλειδιά, τότε από ποιον θα πάρουμε; Η απάντηση είναι ότι δεν έχει σημασία από τη στιγμή που δεν παραβιάζονται τα κριτήρια για το δέντρο. Μπορούμε όμως να έχουμε έναν κανόνα, π.χ. παίρνω από τον κόμβο που έχει τα περισσότερα κλειδιά.
  3. Ο κόμβος Τ έχει n-1 κλειδιά και οι διπλανοί του κόμβοι έχουν ακριβώς n κλειδιά ο καθένας. Σ' αυτή την περίπτωση πρέπει να γίνει συγχώνευση του Τ με έναν από τους διπλανούς κόμβους.
    • Επιλέγουμε το δεξιό ή τον αριστερό κόμβο του Τ. Αν έχει έναν διπλανό, τότε επιλέγουμε αυτόν ενώ αν έχει δύο επιλέγουμε όποιον θέλουμε. Η επιλογή δεν έχει σημασία αφού όποιον κόμβο και να επιλέξουμε, το αποτέλεσμα θα είναι ένα σωστό Β-Δέντρο.
    • Τοποθετούμε τα κλειδιά του κόμβου Τ, του διπλανού του και το κλειδί του γονικού κόμβου που δείχνει σ' αυτούς τους δύο, σε αύξουσα σειρά και φτιάχνουμε τον συγχωνευμένο κόμβο.

Παράδειγμα

Έστω το παρακάτω αρχικό δέντρο.

Τα κλειδιά που θα διαγραφούν είναι: 25, 45, 24, 38, 32, 8, 27, 46, 13, 42, 5, 22, 18, 26, 7, 35, 15

Το κλειδί αυτό ανήκει σε εσωτερικό κόμβο, έτσι πρέπει να βρούμε το αμέσως μεγαλύτερο κλειδί του που θα το αντικαταστήσει. Αυτό είναι το 26. Η μετακίνηση του κλειδιού 26 αφήνει τον κόμβο που άνηκε με 1 κλειδί, οπότε πρέπει να γίνει εξισορρόπηση. Ο κόμβος αυτός, τώρα, είναι τερματικός. Ο διπλανός του κόμβος (δεξιά) έχει τρία κλειδιά, άρα μπορεί να δώσει ένα. Η διαδικασία είναι:
Με τις ενέργειες αυτές καλύπτονται όλες οι ιδιότητες των Β-Δέντρων.
Το κλειδί αυτό ανήκει σε τερματικό κόμβο. Με τη διαγραφή του ο κόμβος παραμένει με 2 κλειδιά, οπότε δε χρειάζεται να γίνει άλλη ενέργεια.
Το κλειδί ανήκει σε τερματικό κόμβο. Με τη διαγραφή του ο κόμβος παραμένει με 1 κλειδί, οπότε πρέπει να πάρει ένα. Ο αριστερός του κόμβους έχει 3 κλειδιά. Η διαδικασία έχει ως εξής:
Το κλειδί ανήκει σε τερματικό κόμβο. Με τη διαγραφή του ο κόμβος παραμένει με 1 κλειδί, οπότε πρέπει να πάρει ένα. Οι διπλανοί του, όμως, κόμβοι δεν έχουν κλειδιά να δώσουν. Έτσι, θα πρέπει να γίνει συγχώνευση κόμβων. Το κλειδί του κόμβου όπου έγινε η διαγραφή, τα κλειδιά του αριστερού του κόμβου και το κλειδί του γονικού κόμβου που δείχνει σ' αυτούς φτιάχνουν έναν νέο κόμβο, τον: 27, 30, 32, 35.
Η χρήση του κλειδιού 32 στον νέο κόμβο, αφήνει στον κόμβο που ήταν το 40 ως το μόνο κλειδί. Αυτό σημαίνει ότι ο κόμβος θα πρέπει να πάρει ένα κλειδί. Η μετακίνηση κλειδιού θα πρέπει να γίνει από διπλανό κόμβο στο ίδιο επίπεδο με τον κόμβο του 40. Ο διπλανός κόμβος, όμως, έχει 2 κλειδιά και δεν μπορεί να δώσει. Θα πρέπει, λοιπόν, να γίνει συγχώνευση κόμβων. Συγχωνεύονται τα κλειδιά του αριστερού κόμβου, το κλειδί του γονικού και του κλειδιού 40. Ο νέος κόμβος είναι ο: 10, 18, 26, 40.
Τα κλειδιά βρίσκονται σε τερματικούς κόμβους και απλά διαγράφονται αφού δεν αφήνουν τους αντίστοιχους κόμβους με λιγότερα από 2 κλειδιά.
Το κλειδί βρίσκεται σε τερματικό κόμβο και διαγράφεται. Αφήνει τον κόμβο του με ένα κλειδί. Ο διπλανός κόμβος έχει μόνο δύο κλειδιά, άρα θα πρέπει να γίνει συγχώνευση. Ο νέος κόμβος έχει τα κλειδιά: 30, 35, 40, 42
Το κλειδί βρίσκεται σε τερματικό κόμβο και διαγράφεται. Αφήνει τον κόμβο του με ένα κλειδί. Οι διπλανοί κόμβοι δεν έχουν περίσσευμα κλειδιών, άρα θα πρέπει να γίνει συγχώνευση. Θα γίνει συγχώνευση με τον αριστερό κόμβο. Ο νέος κόμβος έχει τα κλειδιά: 5, 7, 10, 15
Τα κλειδιά βρίσκονται σε τερματικούς κόμβους και απλά διαγράφονται αφού δεν αφήνουν τους αντίστοιχους κόμβους με λιγότερα από 2 κλειδιά.
Η διαγραφή του κλειδιού αφήνει τον κόμβο με ένα κλειδί. Οι γειτονικοί κόμβου έχουν κλειδιά τα οποία μπορούν να μετακινηθούν. Θα γίνει λοιπόν μία μετακίνηση από τον αριστερό κόμβο και έχουμε:
Η διαγραφή του κλειδιού αφήνει τον κόμβο με ένα κλειδί. Ο δεξιός του κόμβος έχει περίσσευμα κλειδιών. Θα γίνει λοιπόν μία μετακίνηση από τον κόμβο αυτό και έχουμε:
Το κλειδί βρίσκεται σε τερματικό κόμβο και διαγράφεται. Αφήνει τον κόμβο του με ένα κλειδί. Οι διπλανοί κόμβοι δεν έχουν περίσσευμα κλειδιών, άρα θα πρέπει να γίνει συγχώνευση. Θα γίνει συγχώνευση με τον αριστερό κόμβο. Ο νέος κόμβος έχει τα κλειδιά: 7, 10, 15, 20
Το κλειδί βρίσκεται σε τερματικό κόμβο και απλά διαγράφεται αφού δεν αφήνει τον κόμβο με λιγότερα από 2 κλειδιά.
Το κλειδί βρίσκεται σε τερματικό κόμβο και διαγράφεται. Αφήνει τον κόμβο του με ένα κλειδί. Ο διπλανός κόμβος έχει περίσσευμα κλειδιών, έτσι θα γίνει μετακίνηση κλειδιών ως εξής:
Η διαγραφή αφήνει τον κόμβο με ένα κλειδί. Ο διπλανός κόμβος δεν έχει περίσσευμα κλειδιών. Θα πρέπει, λοιπόν, να γίνει συγχώνευση. Όλα τα κλειδιά που έχουν μείνει δημιουργούν τον νέο κόμβο ο οποίος είναι και ο μοναδικός πλέον στο δέντρο.
Page last modified on 19-04-2008 (09:26)