Binary Search Tree

Εισαγωγή

Για την αποθήκευση των λέξεων μέσα στο δυαδικό δένδρο χρησιμοποιείται ένα struct (node), η δομή του struct είναι η εξής: χρησιμοποιείται η μεταβλητή word τύπου string για την αποθήκευση της λέξης, μια μεταβλητή appearances τύπου int για την αποθήκευση των εμφανίσεων της συγκεκριμένης λέξης και υπάρχουν τρεις μεταβλητές (parent, left, right) τύπου node (struct) για την αποθήκευση του προγόνου (πατέρα) κόμβου, την αποθήκευση του αριστερού απογόνου (παιδιού) και του δεξιού απογόνου (παιδιού) αντίστοιχα. Για την δημιουργία λοιπόν του δένδρου, θα χρησιμοποιηθεί η root τύπου node που θα αναπαριστά την ρίζα του δένδρου (η τιμή της root κατά την κατασκευή της δομής θέτεται σε nullptr).

---

Λειτουργίες

Eισαγωγή (insert)

Για την εισαγωγή των λέξεων στο πίνακα από τον χρήστη καλείται η μέθοδος insert (public), η οποία εξετάζει αρχικά την ρίζα (root) του δένδρου δεν έχει πάρει κάποια λέξη ως τιμή (root == nullptr). Εάν είναι άδειος ο κόμβος τότε η λέξη τοποθετείται στην ρίζα και γίνεται αρχικοποίηση των μεταβλητών του node (appearances = 1, parent = nullptr, right = nullptr, left = nullptr), σε κάθε άλλη περίπτωση καλείται η insert (private), σε αυτή την μέθοδο εξετάζεται εάν η λέξη είναι ίδια με αυτή που έχει ήδη ο κόμβος εάν ναι η μεταβλητή appearances αυξάνεται κατά ένα (1), εάν όχι εξετάζεται εάν είναι λεξικογραφικά μεγαλύτερη από την λέξη που υπάρχει ήδη στον κόμβο δημιουργείται ένας νέος κόμβος δεξιά του κόμβου που εξετάζεται διαφορετικά, (δηλ. είναι λεξικογραφικά μικρότερη) δημιουργείται ένας νέος κόμβος που τοποθετείτε η λέξη στα αριστερά του κόμβου που εξετάζεται.

Διαγραφή (remove)

Την διαγραφή θα την χωρίσουμε σε τρεις περιπτώσεις:

• Διαγραφή κόμβου που δεν έχει παιδιά (δηλ. ενός φύλλου),
• διαγραφή κόμβου που έχει ένα παιδί,
• διαγραφή κόμβου που έχει δύο παιδία.

Σε κάθε περίπτωση γίνεται κλήση της remove (private) όπου πραγματοποιείται η αναζήτηση του κόμβου που πρέπει να διαγραφεί και αποθηκεύετε στην parent (τύπου node) ο πρόγονος του κόμβου που πρέπει να διαγραφεί. Στη πρώτη περίπτωση εξετάζεται εάν ο πρόγονος είναι κενός σημαίνει ότι βρισκόμαστε στην ρίζα όπου και την διαγράφουμε. Εναλλακτικά εξετάζεται εάν ο κόμβος είναι το αριστερό ή το δεξί παιδί του προγόνου όπου και διαγράφεται. Στην δεύτερη περίπτωση εάν ο πρόγονος είναι κενός που σημαίνει ότι ήμαστε στην ρίζα, εξετάζουμε ποιο από τα παιδιά του παιδιού είναι κενό και τοποθετούμε το άλλο ως ρίζα το δένδρου ενώ τέλος διαγράφουμε το παιδί (rt). Διαφορετικά εξετάζεται εάν ο κόμβος που πρέπει να διαγραφεί είναι αριστερό ή δεξί παιδί του προγόνου του και εάν ο κόμβος που θα διαγραφεί έχει αριστερό ή δεξί παιδί. Έτσι διακρίνουμε και τέσσερις πιθανές περιπτώσεις:

• Ο κόμβος διαγράφης είναι αριστερό παιδί του προγόνου και o κόμβος διαγράφης δεν έχει αριστερό παιδί, άρα το αριστερό παιδί του του προγόνου γίνεται το δεξί παιδί του κόμβου διαγράφης, ενώ έπειτα διαγράφεται ο κόμβος αυτός.
• Ο κόμβος διαγράφης είναι αριστερό παιδί του προγόνου και o κόμβος διαγράφης δεν έχει δεξί παιδί, άρα το αριστερό παιδί του του προγόνου γίνεται το αριστερό παιδί του κόμβου διαγράφης, ενώ έπειτα διαγράφεται ο κόμβος αυτός.
• Ο κόμβος διαγράφης είναι δεξί παιδί του προγόνου και o κόμβος διαγράφης δεν έχει αριστερό παιδί, άρα το δεξί παιδί του του προγόνου γίνεται το δεξί παιδί του κόμβου διαγράφης, ενώ έπειτα διαγράφεται ο κόμβος αυτός.
• Ο κόμβος διαγράφης είναι δεξί παιδί του προγόνου και o κόμβος διαγράφης δεν έχει αριστερό παιδί, άρα το δεξί παιδί του του προγόνου γίνεται το δεξί παιδί του κόμβου διαγράφης, ενώ έπειτα διαγράφεται ο κόμβος αυτός.

Στην τρίτη περίπτωση αποθηκεύεται στην successor ο μικρότερος κόμβος κάτω από το δεξί παιδί του κόμβου διαγραφής ώστε να αποθηκευτούν στα πεδία word & appearances του κόμβου διαγραφής οι τιμές word & appearances του successor ενώ έπειτα καλείται ξανά η remove (private) με όρισμα την successor.

Aναζήτηση (search)

Η αναζήτηση επιτυγχάνεται μέσω της κλήσης της search (public) που επιστρέφει την αριθμό εμφανίσεων της λέξης εάν υπάρχει διαφορετικά επιστρέφει 0. Για την εύρεση της λέξης γίνεται κλήση της search (private) η οποία εξετάζει εάν η λεξικογραφική θέση της λέξης που ψάχνουμε είναι μεγαλύτερη ή μικρότερη από έναν δεδομένο κόμβο (η πρώτη εξέταση γίνεται με την ρίζα) και αναλόγως επιλέγετε το σωστό μονοπάτι για την εύρεση της λέξης.

Διάσχιση

Η λειτουργίες τις διάσχισης του δένδρου υλοποιούνται όλες αναδρομικά.

Ενδοδιατεταγμένη (inorder)

Για κάθε κόμβο, επισκεπτόμαστε πρώτα τους κόμβους του αριστερού του υποδένδρου, έπειτα τον ίδιο τον κόμβο και στη συνέχεια τους κόμβους του δεξιού του υποδένδρου.

Μεταδιατεταγμένη (postorder)

Για κάθε κόμβο, επισκεπτόμαστεπρώτα τους κόμβους του αριστερού του υποδένδρου, έπειτα τους κόμβους του δεξιού του υποδένδρουκαι στη συνέχεια τον ίδιο τον κόμβο.

Προδιατεταγμένη (preorder)

Για κάθε κόμβο, επισκεπτόμαστεπρώτα τον ίδιο τον κόμβο, έπειτα τους κόμβους του αριστερού του υποδένδρουκαι στη συνέχεια τους κόμβους του δεξιού του υποδένδρου.