Αρχική ΑΕΠΠ - Δομές Δεδομένων Λειτουργικά Συστήματα Δίκτυα Υπολογιστών ΙΙ Βάσεις Δεδομένων Παιδαγωγικά - Διδακτική

Βασικές Έννοιες

Μεταβλητή - Έκφραση Δομή Ακολουθίας Δομή Επιλογής Δομή Επανάληψης

Αναπαράσταση Αλγορίθμων

Διάγραμμα Ροής

... σε Αλγόριθμο
... από Αλγόριθμο

Πίνακας Τιμών

Πίνακες

Μονοδιάστατοι Δισδιάστατοι Πολυδιάστατοι Αναζήτηση Ταξινόμηση Στοίβα Ουρά

Υποπρογράμματα

Συναρτήσεις Διαδικασίες Σχετικά με τις παράμετρους

Δυναμικές Δομές

Λίστες Δέντρα Γράφοι 

 Ιστορικό Πρόσφατες αλλαγές Εκτύπωση Αναζήτηση

Β-Δέντρα

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

  • Η ρίζα μπορεί να περιέχει από 1 μέχρι 2n κλειδιά.
  • Κάθε κόμβος εκτός της ρίζας περιέχει από n μέχρι 2n κλειδιά.
  • Ένας εσωτερικός κόμβος με m κλειδιά έχει m+1 παιδιά (n<=m<=2n).
  • Όλοι οι τερματικοί κόμβοι βρίσκονται στο ίδιο επίπεδο.

Τυπικός κόμβος Β-Δέντρου με 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

  • Εισαγωγή 20, 40
  • Εισαγωγή 10
Η εισαγωγή ενός στοιχείου σε μία σελίδα γίνεται με ταξινόμηση των αριθμών σε αύξουσα σειρά.
  • Εισαγωγή 30
Με την εισαγωγή αυτή γεμίζει η πρώτη σελίδα.
  • Εισαγωγή 15
Η εισαγωγή του κλειδιού 15 δεν μπορεί να γίνει στην σελίδα. Η διαδικασία που ακολουθούμε είναι:
  • Τα εμπλεκόμενα κλειδιά μπαίνουν σε αύξουσα σειρά
  • Το μεσαίο στοιχείο θα μπει στην από πάνω σελίδα. Επειδή εδώ δεν υπάρχει θα πρέπει να δημιουργηθεί
  • Τα αριστερά κλειδιά θα δημιουργήσουν μία νέα σελίδα η οποία θα υποδεικνύεται από τον αριστερό δείκτη του 20
  • Τα δεξιά κλειδιά θα δημιουργήσουν μία νέα σελίδα η οποία θα υποδεικνύεται από το δεξιό δείκτη του 20
  • Εισαγωγή 35, 7, 26, 18
Τα κλειδιά αυτά εισάγωνται στις αντίστοιχες σελίδες. Προσέξτε ότι παρόλο που αρχική σελίδα έχει λιγότερα από 2 στοιχεία η εισαγωγή γίνεται στις χαμηλότερες σελίδες.
  • Εισαγωγή 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. Σ' αυτήν την περίπτωση πρέπει να γίνει εξισορρόπηση.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • αν η διαγραφή του κλειδιού αφήνει τουλάχιστον n κλειδιά, τότε το κλειδί απλώς διαγράφεται,
  • αν αφήνει n-1 κλειδιά, διακρίνουμε τρεις περιπτώσεις:
  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

  • Διαγραφή 25
Το κλειδί αυτό ανήκει σε εσωτερικό κόμβο, έτσι πρέπει να βρούμε το αμέσως μεγαλύτερο κλειδί του που θα το αντικαταστήσει. Αυτό είναι το 26. Η μετακίνηση του κλειδιού 26 αφήνει τον κόμβο που άνηκε με 1 κλειδί, οπότε πρέπει να γίνει εξισορρόπηση. Ο κόμβος αυτός, τώρα, είναι τερματικός. Ο διπλανός του κόμβος (δεξιά) έχει τρία κλειδιά, άρα μπορεί να δώσει ένα. Η διαδικασία είναι:
  • Το κλειδί που είναι δείκτης στους δύο κόμβους, δηλαδή το 30, κατεβαίνει στον αριστερό κόμβο
  • Το κλειδί 32 ανεβαίνει στον επάνω κόμβο.
Με τις ενέργειες αυτές καλύπτονται όλες οι ιδιότητες των Β-Δέντρων.
  • Διαγραφή 45
Το κλειδί αυτό ανήκει σε τερματικό κόμβο. Με τη διαγραφή του ο κόμβος παραμένει με 2 κλειδιά, οπότε δε χρειάζεται να γίνει άλλη ενέργεια.
  • Διαγραφή 24
Το κλειδί ανήκει σε τερματικό κόμβο. Με τη διαγραφή του ο κόμβος παραμένει με 1 κλειδί, οπότε πρέπει να πάρει ένα. Ο αριστερός του κόμβους έχει 3 κλειδιά. Η διαδικασία έχει ως εξής:
  • Το κλειδί που είναι δείκτης στους δύο κόμβους, δηλαδή το 20, κατεβαίνει στο δεξί κόμβο
  • Το κλειδί 18 ανεβαίνει στον επάνω κόμβο.
  • Διαγραφή 38
Το κλειδί ανήκει σε τερματικό κόμβο. Με τη διαγραφή του ο κόμβος παραμένει με 1 κλειδί, οπότε πρέπει να πάρει ένα. Οι διπλανοί του, όμως, κόμβοι δεν έχουν κλειδιά να δώσουν. Έτσι, θα πρέπει να γίνει συγχώνευση κόμβων. Το κλειδί του κόμβου όπου έγινε η διαγραφή, τα κλειδιά του αριστερού του κόμβου και το κλειδί του γονικού κόμβου που δείχνει σ' αυτούς φτιάχνουν έναν νέο κόμβο, τον: 27, 30, 32, 35.
Η χρήση του κλειδιού 32 στον νέο κόμβο, αφήνει στον κόμβο που ήταν το 40 ως το μόνο κλειδί. Αυτό σημαίνει ότι ο κόμβος θα πρέπει να πάρει ένα κλειδί. Η μετακίνηση κλειδιού θα πρέπει να γίνει από διπλανό κόμβο στο ίδιο επίπεδο με τον κόμβο του 40. Ο διπλανός κόμβος, όμως, έχει 2 κλειδιά και δεν μπορεί να δώσει. Θα πρέπει, λοιπόν, να γίνει συγχώνευση κόμβων. Συγχωνεύονται τα κλειδιά του αριστερού κόμβου, το κλειδί του γονικού και του κλειδιού 40. Ο νέος κόμβος είναι ο: 10, 18, 26, 40.
  • Διαγραφή 32, 8, 27
Τα κλειδιά βρίσκονται σε τερματικούς κόμβους και απλά διαγράφονται αφού δεν αφήνουν τους αντίστοιχους κόμβους με λιγότερα από 2 κλειδιά.
  • Διαγραφή 46
Το κλειδί βρίσκεται σε τερματικό κόμβο και διαγράφεται. Αφήνει τον κόμβο του με ένα κλειδί. Ο διπλανός κόμβος έχει μόνο δύο κλειδιά, άρα θα πρέπει να γίνει συγχώνευση. Ο νέος κόμβος έχει τα κλειδιά: 30, 35, 40, 42
  • Διαγραφή 13
Το κλειδί βρίσκεται σε τερματικό κόμβο και διαγράφεται. Αφήνει τον κόμβο του με ένα κλειδί. Οι διπλανοί κόμβοι δεν έχουν περίσσευμα κλειδιών, άρα θα πρέπει να γίνει συγχώνευση. Θα γίνει συγχώνευση με τον αριστερό κόμβο. Ο νέος κόμβος έχει τα κλειδιά: 5, 7, 10, 15
  • Διαγραφή 42, 5
Τα κλειδιά βρίσκονται σε τερματικούς κόμβους και απλά διαγράφονται αφού δεν αφήνουν τους αντίστοιχους κόμβους με λιγότερα από 2 κλειδιά.
  • Διαγραφή 22
Η διαγραφή του κλειδιού αφήνει τον κόμβο με ένα κλειδί. Οι γειτονικοί κόμβου έχουν κλειδιά τα οποία μπορούν να μετακινηθούν. Θα γίνει λοιπόν μία μετακίνηση από τον αριστερό κόμβο και έχουμε:
  • Το κλειδί που είναι δείκτης στους δύο κόμβους, δηλαδή το 18, κατεβαίνει στο δεξί κόμβο
  • Το κλειδί 15 ανεβαίνει στον επάνω κόμβο.
  • Διαγραφή 18
Η διαγραφή του κλειδιού αφήνει τον κόμβο με ένα κλειδί. Ο δεξιός του κόμβος έχει περίσσευμα κλειδιών. Θα γίνει λοιπόν μία μετακίνηση από τον κόμβο αυτό και έχουμε:
  • Το κλειδί που είναι δείκτης στους δύο κόμβους, δηλαδή το 26, κατεβαίνει στον αριστερό κόμβο
  • Το κλειδί 30 ανεβαίνει στον επάνω κόμβο.
  • Διαγραφή 26
Το κλειδί βρίσκεται σε τερματικό κόμβο και διαγράφεται. Αφήνει τον κόμβο του με ένα κλειδί. Οι διπλανοί κόμβοι δεν έχουν περίσσευμα κλειδιών, άρα θα πρέπει να γίνει συγχώνευση. Θα γίνει συγχώνευση με τον αριστερό κόμβο. Ο νέος κόμβος έχει τα κλειδιά: 7, 10, 15, 20
  • Διαγραφή 7
Το κλειδί βρίσκεται σε τερματικό κόμβο και απλά διαγράφεται αφού δεν αφήνει τον κόμβο με λιγότερα από 2 κλειδιά.
  • Διαγραφή 35
Το κλειδί βρίσκεται σε τερματικό κόμβο και διαγράφεται. Αφήνει τον κόμβο του με ένα κλειδί. Ο διπλανός κόμβος έχει περίσσευμα κλειδιών, έτσι θα γίνει μετακίνηση κλειδιών ως εξής:
  • Το κλειδί που είναι δείκτης στους δύο κόμβους, δηλαδή το 30, κατεβαίνει στο δεξί κόμβο
  • Το κλειδί 20 ανεβαίνει στον επάνω κόμβο.
  • Διαγραφή 15
Η διαγραφή αφήνει τον κόμβο με ένα κλειδί. Ο διπλανός κόμβος δεν έχει περίσσευμα κλειδιών. Θα πρέπει, λοιπόν, να γίνει συγχώνευση. Όλα τα κλειδιά που έχουν μείνει δημιουργούν τον νέο κόμβο ο οποίος είναι και ο μοναδικός πλέον στο δέντρο.

Τελευταία ενημέρωση: 19-04-2008 (09:26)

Copyright 2008 - Άρης Φεργάδης