AVL Tree

Εισαγωγή

Κλάση Node: αναπαριστά έναν κόμβο από το AVL δένδρο και περιέχει 5 πεδία:

• string key: η τιμή του κόμβου - λέξη από το αρχείο.
• Node *left: αριστερό παιδί του κόμβου.
• Node *right: δεξί παιδί του κόμβου.
• int height: ύψος του δένδρου.
• int appearances: μετράει πόσες φορές εμφανίζεται η λέξη key στο κείμενο.

Σε ένα δένδρο AVL τα ύψη των δύο παιδιών της ρίζας διαφέρουν το πολύ κατά 1 όπως και δυο παιδιά των παιδιών της ρίζας κ.ο.κ. Για να γίνει η διατήρηση της ιδιότητας αυτής του δένδρου θα χρησιμοποιηθούν στην εισαγωγή και διαγραφή (όταν χρειαστεί) κάποιες μέθοδοι που αναλαμβάνουν την περιστροφή του δένδρου. Σαφέστερα:

• Μέθοδος που υλοποιεί τη δεξιά περιστροφή του δένδρου, ώστε να μη χάσει την ιδιότητά του σαν AVL δένδρο. Δίνεται ο κόμβος y σαν παράμετρος. Δημιουργούνται δύο νέοι κόμβοι: x και Τ2. Ο x αρχικοποιείται με το αριστερό παιδί του κόμβου y και στη συνέχεια ο Τ2 αρχικοποιείται με το δεξί παιδί του x. Στη θέση του δεξιού παιδιού του x πάει ο y, ενώ στη θέση του αριστερού παιδιού του y πάει ο Τ2. Τέλος, το height του κόμβου y αλλάζει καλώντας τη μέθοδο max(int, int) που παίρνει ως ορίσματα:

1. το height του αριστερού παιδιού του y και
2. το δεξί height του y αυξημένο κατά 1.

Ομοίως, αλλάζει το height του x, αλλά με ορίσματα:

1. το height του αριστερού παιδιού του x και
2. το δεξί height του x αυξημένο κατά 1.

• Μέθοδος που υλοποιεί την αριστερή περιστροφή του δένδρου, ώστε να μη χάσει την ιδιότητά του σαν AVL δένδρο. Δίνεται ο κόμβος x σαν παράμετρος. Δημιουργούνται δύο νέοι κόμβοι: y και Τ2. Ο y αρχικοποιείται με το δεξί παιδί του κόμβου x και στη συνέχεια ο Τ2 αρχικοποιείται με το αριστερό παιδί του y. Στη θέση του αριστερού παιδιού του y πάει ο x, ενώ στη θέση του δεξιού παιδιού του x πάει ο Τ2. Τέλος, το height του κόμβου x αλλάζει καλώντας τη μέθοδο max(int, int) που παίρνει ως ορίσματα:

1. το height του αριστερού παιδιού του x και
2. το δεξί height του x αυξημένο κατά 1. Ομοίως, αλλάζει το height του y, αλλά με ορίσματα:
3. το height του αριστερού παιδιού του y και
4. το δεξί height του y αυξημένο κατά 1.

---

Λειτουργίες

Eισαγωγή (insert)

Μέθοδος που υλοποιεί την εισαγωγή μιας λέξης από το κείμενο στο AVL δένδρο (insert(Node* node, string key)). Αρχικά, γίνεται έλεγχος για το αν ο κόμβος που δίνεται σαν παράμετρος είναι κενός. Σε αυτή τη περίπτωση καλείται η μέθοδος newNode(string) και το αποτέλεσμα αυτής επιστρέφει η insert. Αν ο κόμβος δεν είναι κενός, γίνεται έλεγχος για το αν η λέξη από το κείμενο είναι λεξικογραφικά μεγαλύτερη, μικρότερη ή ίση με τη λέξη που υπάρχει στον κόμβο που δίνεται. Αν είναι μικρότερη, καλείται αναδρομικά η insert δίνοντας ως πρώτη παράμετρο το αριστερό παιδί του κόμβου και αποθηκεύει το αποτέλεσμα στο αριστερό παιδί του κόμβου. Ομοίως, αν είναι η λέξη του κειμένου μεγαλύτερη, αλλά για το δεξί παιδί του κόμβου. Αν η λέξη του κειμένου είναι ίδια με αυτή του κόμβου, αυξάνεται το πεδίο appearances του κόμβου κατά 1 και η μέθοδος επιστρέφει τον κόμβο. Μετά από αυτόν τον έλεγχο, η μέθοδος βρίσκει το height του κόμβου και τη διαφορά των υψών μεταξύ των υποδένδρων καλώντας τις κατάλληλες συναρτήσεις. Τέλος,με βάση τις δύο προηγούμενες τιμές, γίνεται έλεγχος για το αν πρέπει να γίνει δεξιά ή αριστερή περιστροφή στο δένδρο, έτσι ώστε να μη χάσει την ιδιότητά του ως AVL.

Διαγραφή (remove)

Μέθοδος που υλοποιεί την διαγραφή ενός κόμβου του δένδρου AVL(remove(Node* root, string key)). Αρχικά γίνεται έλεγχος για το αν δόθηκε κενός κόμβος. Σε αυτή τη περίπτωση, επιστρέφεται ο κενός κόμβος. Αν η λέξη που είναι προς διαγραφή είναι μικρότερη από τη τιμή του κόμβου, βρίσκεται στο αριστερό υποδένδρο, γι αυτό ξανακαλείται η deleteNode με πρώτο όρισμα το αριστερό παιδί του κόμβου. Αν η λέξη που είναι προς διαγραφή είναι μεγαλύτερη από τη τιμή του κόμβου, βρίσκεται στο αριστερό υποδένδρο, γι αυτό ξανακαλείται η deleteNode με πρώτο όρισμα το δεξί παιδί του κόμβου. Στη περίπτωση που βρεθεί ο κόμβος με τη λέξη που είναι προς διαγραφή, αν ο κόμβος έχει ένα παιδί, αντικαθίσταται με τον κόμβο-παιδί. Αν δεν έχει παιδί, διαγράφεται με τη χρήση της free. Αν έχει δύο παιδιά, καλεί την minValueNode με όρισμα το δεξί παιδί, για να βρεθεί ο κόμβος με τη μικρότερη τιμή του δεξιού υποδένδρου και αποθηκεύεται στον κόμβο προσωρινό temp. Τότε ο κόμβος αντικαθίστανται με τον temp, ως προς τα πεδία key και appearances. Τότε καλείται ξανά η deleteNode με πρώτο όρισμα το δεξί παιδί του root και με δεύτερο όρισμα το key του temp. Μετά του παραπάνω ελέγχους, αλλάζει κατάλληλα το πεδίο height του root με τη χρήση της height() και γίνεται έλεγχος της διαφοράς των υψών μεταξύ του αριστερού και του δεξιού υποδένδρου, ώστε να γίνουν οι κατάλληλες περιστροφές στο δένδρο.

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

Μέθοδος που υλοποιεί την αναζήτηση της λέξης που δίνεται από το κείμενο στο AVL (search(Node* root, string key)). Η μέθοδος επιστρέφει ακέραιο αριθμό, ο οποίος αναπαριστά το πόσες φορές βρίσκεται η λέξη στο κείμενο. Αν ο κόμβος που δίνεται ως όρισμα είναι κενός, επιστρέφει 0. Αν η λέξη βρεθεί σε κάποιον κόμβο του δένδρου, επιστρέφει το πεδίο appearances του κόμβου αυτού. Αν η λέξη του κειμένου είναι μεγαλύτερη από τη τιμή του κόμβου, καλείται ξανά η search αλλά με πρώτο όρισμα το δεξί παιδί του κόμβου. Αν η λέξη του κειμένου είναι μικρότερη από τη τιμή του κόμβου, τότε καλείται πάλι η search, αλλά με πρώτο όρισμα το αριστερό παιδί του κόμβου.

Διάσχιση

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

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

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

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

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

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