Αρχική ΑΕΠΠ - Δομές Δεδομένων Λειτουργικά Συστήματα Δίκτυα Υπολογιστών ΙΙ Βάσεις Δεδομένων Παιδαγωγικά - Διδακτική
Μεταβλητή - Έκφραση Δομή Ακολουθίας Δομή Επιλογής Δομή Επανάληψης
Μονοδιάστατοι Δισδιάστατοι Πολυδιάστατοι Αναζήτηση Ταξινόμηση Στοίβα Ουρά
Συναρτήσεις Διαδικασίες Σχετικά με τις παράμετρους
Τα Β-Δέντρα είναι μερική περίπτωση των πολυκατευθυνόμενων δέντρων. Ένα δέντρο τάξης n
είναι το δέντρο που έχει τα παρακάτω χαρακτηριστικά:
1
μέχρι 2n
κλειδιά.
n
μέχρι 2n
κλειδιά.
m
κλειδιά έχει m+1
παιδιά (n<=m<=2n
).
Τυπικός κόμβος Β-Δέντρου με m
κλειδιά.
Η έννοια του κόμβου προέρχεται από τον ορισμό του δέντρου. Στα Β-Δέντρα χρησιμοποιείται και ο όρος σελίδα ταυτόσημα με τον κόμβο. Στο παρακάτω κείμενο μπορεί να χρησιμοποιηθεί ο ένας ή ο άλλος όρος σημαίνοντας όμως πάντα το ίδιο, δηλαδή, ένα κόμβο Β-Δέντρου.
Διακρίνουμε δύο περιπτώσεις στην εισαγωγή ενός κλειδιού:
2n
τότε το κλειδί παρεμβάλλεται στα υπόλοιπα της σελίδας έτσι ώστε όλα να είναι ταξινομημένα σε αύξουσα σειρά.
Η διάσπαση της σελίδας γίνεται με της εξής διαδικασία:
Θα δημιουργήσουμε ένα Β-δέντρο με διαδοχική εισαγωγή των κλειδιών:
20, 40, 10, 30, 15, 35, 7, 26, 18, 22, 5, 42, 13, 46, 27, 8, 32, 38, 24, 45, 25
20
, 40
10
30
15
15
δεν μπορεί να γίνει στην σελίδα. Η διαδικασία που ακολουθούμε είναι:
20
20
35, 7, 26, 18
22
22
θα έπρεπε να τοποθετηθεί στη δεξιά σελίδα του δευτέρου επιπέδου. Αυτό όμως δεν μπορεί να γίνει γιατί η σελίδα είναι πλήρης. Η διαδικασία που θα ακολουθήσουμε είναι:
22, 26, 30, 35, 40
30
θα μπει στην από πάνω σελίδα
30
30
5
42, 13, 46, 27, 8
32
32, 35, 40, 42, 25
38, 24, 45
25
22, 24, 25, 26, 27
. Το κλειδί 25
θα ανέβει στην από πάνω σελίδα και τα υπόλοιπα θα φτιάξουν δύο σελίδες. Επειδή, όμως, και η από πάνω σελίδα είναι γεμάτη, θα πρέπει να γίνει διάσπαση και εκεί. Έχουμε, δηλαδή:
10, 20, 25, 30, 40
. Το μεσαίο πρέπει να ανέβει στην από πάνω σελίδα. Επειδή δεν υπάρχει θα πρέπει να δημιουργηθεί μία η οποία θα έχει μόνο αυτό, στην περίπτωσή μας το 25
.
10, 20
θα γίνουν η αριστερή σελίδα του 25
και
30, 40
θα γίνουν η δεξιά σελίδα του.
Ο αλγόριθμος για τη διαγραφή κλειδιών είναι όμοιος με εκείνον της διαγραφής από τα AVL δέντρα. Όταν ένα κλειδί διαγράφεται από έναν κόμβο είναι πιθανόν ότι ο αριθμός των κλειδιών που παραμένουν είναι μικρότερος από n
. Σ' αυτήν την περίπτωση πρέπει να γίνει εξισορρόπηση.
Εδώ θα πρέπει να αναφέρουμε ότι υπάρχουν μικρές παραλλαγές στον αλγόριθμο που ακολουθείται σε διάφορες υλοποιήσεις. Αυτό, δυστυχώς, μπορεί να μπερδέψει κάποιον ο οποίος ασχολείται πρώτη φορά με τα Β-Δέντρα και προσπαθεί να καταλάβει τη διαδικασία διαγραφής.
Διακρίνουμε δύο περιπτώσεις:
Η πρώτη περίπτωση, αφού γίνει πρώτα μία μετακίνηση κλειδιού, ανάγεται στη δεύτερη.
Το κλειδί που διαγράφεται πρέπει να αντικατασταθεί από το αμέσως μικρότερο ή από το αμέσως μεγαλύτερο.
Για να βρούμε το αμέσως μεγαλύτερο:
Για να βρούμε το αμέσως μικρότερο:
Το πιο κλειδί από τα δύο θα χρησιμοποιήσουμε δεν έχει σημασία αφού και με τις δύο περιπτώσεις διατηρούνται οι ιδιότητες των Β-Δέντρων. Αρκεί, όμως, να διαλέξουμε τη μία από τις δύο διαδικασίες και να "κολλήσουμε" σ' αυτή.
Εμείς, στο παράδειγμα που ακολουθεί, βρίσκουμε το μεγαλύτερο.
Δεδομένου ενός κόμβου Τ
:
n
κλειδιά, τότε το κλειδί απλώς διαγράφεται,
n-1
κλειδιά, διακρίνουμε τρεις περιπτώσεις:
n+1
κλειδιά.
Τ
το οποίο έχει δείκτη προς τον Τ
, κατεβαίνει ένα επίπεδο και γίνεται το πρώτο κλειδί στον κόμβο Τ
.
Τ
ανεβαίνει ένα επίπεδο και μπαίνει στη θέση εκείνου του κλειδιού που μετακινήθηκε στον κόμβο Τ
.
n+1
κλειδιά.
Τ
το οποίο έχει δείκτη προς τον Τ
, κατεβαίνει ένα επίπεδο και γίνεται το τελευταίο κλειδί στον κόμβο Τ
.
Τ
ανεβαίνει ένα επίπεδο και μπαίνει στη θέση εκείνου του κλειδιού που μετακινήθηκε στον κόμβο Τ
.Τ
τύχει να έχει κόμβους και δεξιά και αριστερά οι οποίοι να έχουν περισσότερα από n
κλειδιά, τότε από ποιον θα πάρουμε; Η απάντηση είναι ότι δεν έχει σημασία από τη στιγμή που δεν παραβιάζονται τα κριτήρια για το δέντρο. Μπορούμε όμως να έχουμε έναν κανόνα, π.χ. παίρνω από τον κόμβο που έχει τα περισσότερα κλειδιά.
Τ
έχει n-1
κλειδιά και οι διπλανοί του κόμβοι έχουν ακριβώς n
κλειδιά ο καθένας. Σ' αυτή την περίπτωση πρέπει να γίνει συγχώνευση του Τ
με έναν από τους διπλανούς κόμβους.
Τ
. Αν έχει έναν διπλανό, τότε επιλέγουμε αυτόν ενώ αν έχει δύο επιλέγουμε όποιον θέλουμε. Η επιλογή δεν έχει σημασία αφού όποιον κόμβο και να επιλέξουμε, το αποτέλεσμα θα είναι ένα σωστό Β-Δέντρο.
Τ
, του διπλανού του και το κλειδί του γονικού κόμβου που δείχνει σ' αυτούς τους δύο, σε αύξουσα σειρά και φτιάχνουμε τον συγχωνευμένο κόμβο.
Έστω το παρακάτω αρχικό δέντρο.
Τα κλειδιά που θα διαγραφούν είναι: 25, 45, 24, 38, 32, 8, 27, 46, 13, 42, 5, 22, 18, 26, 7, 35, 15
25
26
. Η μετακίνηση του κλειδιού 26
αφήνει τον κόμβο που άνηκε με 1 κλειδί, οπότε πρέπει να γίνει εξισορρόπηση. Ο κόμβος αυτός, τώρα, είναι τερματικός. Ο διπλανός του κόμβος (δεξιά) έχει τρία κλειδιά, άρα μπορεί να δώσει ένα. Η διαδικασία είναι:
30
, κατεβαίνει στον αριστερό κόμβο
32
ανεβαίνει στον επάνω κόμβο.
45
24
20
, κατεβαίνει στο δεξί κόμβο
18
ανεβαίνει στον επάνω κόμβο.
38
27, 30, 32, 35
.
32
στον νέο κόμβο, αφήνει στον κόμβο που ήταν το 40
ως το μόνο κλειδί. Αυτό σημαίνει ότι ο κόμβος θα πρέπει να πάρει ένα κλειδί. Η μετακίνηση κλειδιού θα πρέπει να γίνει από διπλανό κόμβο στο ίδιο επίπεδο με τον κόμβο του 40
. Ο διπλανός κόμβος, όμως, έχει 2 κλειδιά και δεν μπορεί να δώσει. Θα πρέπει, λοιπόν, να γίνει συγχώνευση κόμβων. Συγχωνεύονται τα κλειδιά του αριστερού κόμβου, το κλειδί του γονικού και του κλειδιού 40
. Ο νέος κόμβος είναι ο: 10, 18, 26, 40
.
32, 8, 27
46
30, 35, 40, 42
13
5, 7, 10, 15
42, 5
22
18
, κατεβαίνει στο δεξί κόμβο
15
ανεβαίνει στον επάνω κόμβο.
18
26
, κατεβαίνει στον αριστερό κόμβο
30
ανεβαίνει στον επάνω κόμβο.
26
7, 10, 15, 20
7
35
30
, κατεβαίνει στο δεξί κόμβο
20
ανεβαίνει στον επάνω κόμβο.
15
Copyright 2008 - Άρης Φεργάδης