Ένα δένδρο (tree) είναι μία δομή που αποτελείται από ένα σύνολο κόμβων και ένα σύνολο ακμών μεταξύ των κόμβων, με βάση τους εξής κανόνες:
Υπάρχει ένας ξεχωριστός κόμβος που ονομάζεται ρίζα (root). Αυτός είναι ένας κόμβος χωρίς γονέα.
Για κάθε κόμβο c, εκτός από τη ρίζα, υπάρχει μόνο μια ακμή που καταλήγει στον κόμβο αυτόν ξεκινώντας από κάποιον άλλον κόμβο p. Ο κόμβος p ονομάζεται γονέας του c και ο κόμβος cπαιδί του p.
Για κάθε κόμβο υπάρχει μία μοναδική διαδρομή, δηλαδή μια ακολουθία διαδοχικών ακμών, που ξεκινάει από τη ρίζα και τερματίζει σε αυτόν τον κόμβο.
💡 Σημείωση: Τα δένδρα υλοποιούνται στις σύγχρονες γλώσσες προγραμματισμού με τη βοήθεια των δεικτών. Το κύριο χαρακτηριστικό των δένδρων είναι ότι από έναν κόμβο δεν υπάρχει ένας μόνο επόμενος κόμβος, αλλά περισσότεροι.
🌿 Βασικοί Όροι
Γονέας (Parent): Ο κόμβος από τον οποίο ξεκινάει μια ακμή.
Παιδί (Child): Ο κόμβος στον οποίο καταλήγει μια ακμή.
Αδέλφια (Siblings): Κόμβοι με τον ίδιο γονέα.
Φύλλα (Leaves): Κόμβοι χωρίς παιδιά.
Ρίζα (Root): Ο κόμβος χωρίς γονέα, βρίσκεται στην κορυφή του δένδρου.
Ένας κόμβος μπορεί να έχει κανένα, ένα ή περισσότερα παιδιά. Όλοι οι κόμβοι, εκτός από έναν, έχουν ακριβώς έναν γονέα.
A (Ρίζα)
/ \
B Γ
/ \ / | \
Δ Ε Ζ Η Θ
/ \ |
Ι Κ Λ
Φύλλα: Δ, Ι, Κ, Ζ, Λ, Θ
🌲 Ειδικές Περιπτώσεις Δένδρων
Κενό Δένδρο
Το κενό δένδρο είναι το δένδρο που δεν έχει ούτε κόμβους, ούτε ακμές. Είναι το μόνο δένδρο χωρίς ρίζα.
Δένδρο με έναν κόμβο
Μπορούμε να έχουμε ένα απλό δένδρο, το οποίο να απαρτίζεται από έναν μόνο κόμβο. Αυτός ο κόμβος είναι και ρίζα του (διότι δεν έχει γονέα) και φύλλο (διότι δεν έχει παιδιά).
🌳 Υποδένδρα
Μέσα σε ένα δένδρο μπορούμε να εντοπίσουμε και άλλα μικρότερα δένδρα, που ονομάζονται υποδένδρα. Πιο συγκεκριμένα, κάθε κόμβος ενός δένδρου μπορεί να θεωρηθεί ως ρίζα ενός υποδένδρου, δηλαδή ενός άλλου μικρότερου δένδρου, που ξεκινάει από τον κόμβο αυτόν.
Παράδειγμα: Σε ένα δένδρο με ρίζα τον κόμβο 48:
Ο κόμβος 48 έχει δύο υποδένδρα που ξεκινούν από τους κόμβους 45 και 70.
Ο κόμβος 45 έχει ένα υποδένδρο που αποτελείται από τον κόμβο 2.
Ο κόμβος 70 έχει δύο υποδένδρα που αποτελούνται από τους κόμβους 66 και 83.
Τα υποδένδρα των κόμβων 2, 66 και 83 είναι κενά δένδρα (δεν έχουν παιδιά).
📋 Διατεταγμένο Δένδρο
Σε περίπτωση που για κάθε κόμβο υπάρχει μια γραμμική σχέση μεταξύ των παιδιών του κόμβου αυτού (δηλαδή μας ενδιαφέρει η σειρά τους), αναφερόμαστε σε ένα διατεταγμένο δένδρο.
✨ Πλεονεκτήματα των Δένδρων
Υπάρχουν δύο λόγοι για τους οποίους τα δένδρα είναι τόσο ισχυρά:
Δυναμικότητα: Σε ένα δένδρο (ως δυναμική δομή που είναι) είναι πολύ εύκολο να προσθέσουμε, να αφαιρέσουμε ή να αναζητήσουμε ένα στοιχείο.
Μεταφορά πληροφοριών: Η δομή των δένδρων μεταφέρει πληροφορίες. Για παράδειγμα, στο σύστημα αρχείων ενός υπολογιστή, λόγω του ότι ο κατάλογος "users" είναι παιδί της ρίζας "/" και ο κατάλογος "student" είναι παιδί του "users", μπορούμε να συμπεράνουμε ότι υπάρχει η διαδρομή "/users/student".
🖥️ Τομείς Χρήσης Δένδρων
Τα δένδρα είναι μια μη-γραμμική ευέλικτη δομή δεδομένων που χρησιμοποιούνται σε πολλούς τομείς της επιστήμης των υπολογιστών:
Λειτουργικά συστήματα
Συστήματα βάσεων δεδομένων
Γραφικά
Παιχνίδια
Τεχνητή νοημοσύνη
Δικτύωση
👨👩👧👦 Αναπαράσταση Ιεραρχίας
Συνήθως, όταν αναφερόμαστε στα δένδρα, μας έρχονται στο νου διάφορες αναπαραστάσεις δεδομένων του πραγματικού κόσμου αλλά και της Πληροφορικής που διέπονται από ένα είδος φυσικής ιεραρχίας:
Τα δένδρα αποτελούν τη βάση αρκετών αλγορίθμων επίλυσης προβλήματος:
Συμπίεση εικόνων
Ταξινόμηση
Αυτόματη συμπλήρωση λέξεων στα κινητά τηλέφωνα
Μεταγλώττιση ενός προγράμματος
Λήψη αποφάσεων
🎯 Δένδρα Απόφασης
Τα δένδρα απόφασης είναι δένδρα στα οποία:
Κάθε κόμβος αντιπροσωπεύει ένα χαρακτηριστικό (ιδιότητα).
Κάθε ακμή αντιπροσωπεύει μια απόφαση (κανόνα).
Κάθε φύλλο αντιπροσωπεύει ένα αποτέλεσμα.
Παράδειγμα: "Είναι το σπίτι καθαρό;" → Ναι → "Χαλαρώνω!!!" / Όχι → "Είναι το πάτωμα καθαρό;" → Ναι → "Πλένω τα παράθυρα" / Όχι → "Σφουγγαρίζω το πάτωμα".
Χρήσεις: Αλγόριθμοι μηχανικής μάθησης (machine learning), ιατρικές διαγνώσεις, παιχνίδια (σκάκι, τρίλιζα, τάβλι) μέσω του δένδρου παιχνιδιού (game tree).
🔢 Αναπαράσταση Αριθμητικών Εκφράσεων
Τα δένδρα χρησιμοποιούνται για την αναπαράσταση και τον υπολογισμό αριθμητικών εκφράσεων.
*
/ \
+ c
/ \
a b
*(+(a,b), c) → (a+b)*c
🌿 Δυαδικό Δένδρο (Binary Tree)
Ένα δυαδικό δένδρο είναι ένα διατεταγμένο δένδρο, στο οποίο κάθε κόμβος έχει το πολύ δύο παιδιά, το αριστερό και το δεξιό παιδί.
Σε ένα δυαδικό δένδρο μπορούμε, συνεπώς, να μιλάμε για αριστερό και δεξιό υποδένδρο ενός κόμβου.
⚠️ Σημαντικό: Αν ανταλλάξουμε το αριστερό με το δεξιό υποδένδρο ενός κόμβου, παίρνουμε ένα διαφορετικό δένδρο.
🔍 Δυαδικό Δένδρο Αναζήτησης (BST)
Ένα δυαδικό δένδρο αναζήτησης (Binary Search Tree) είναι ένα δυαδικό δένδρο, όπου για κάθε κόμβο u:
Όλοι οι κόμβοι του αριστερού υποδένδρου έχουν τιμές μικρότερες της τιμής του κόμβου u.
Όλοι οι κόμβοι του δεξιού υποδένδρου έχουν τιμές μεγαλύτερες (ή ίσες) της τιμής του κόμβου u.
⚠️ Προσοχή: Το δένδρο πρέπει να ικανοποιεί την ιδιότητα BST για κάθε κόμβο, όχι μόνο για τη ρίζα. Για παράδειγμα, αν ένας κόμβος με τιμή 3 είναι παιδί του κόμβου 1, αλλά ο κόμβος 1 ανήκει στο αριστερό υποδένδρο του κόμβου 2, τότε το δένδρο δεν είναι BST, γιατί 3 > 2 και βρίσκεται στο αριστερό υποδένδρο του 2.
🔎 Αναζήτηση σε BST
Έστω ότι αναζητούμε το στοιχείο 5 σε ένα BST:
Επισκεπτόμαστε τη ρίζα του δένδρου.
Αν το στοιχείο που αναζητούμε είναι μικρότερο από την τιμή της ρίζας, πηγαίνουμε στο αριστερό υποδένδρο.
Αλλιώς πηγαίνουμε στο δεξιό υποδένδρο.
Συνεχίζουμε με τον ίδιο τρόπο μέχρι να φτάσουμε στον κόμβο που έχει την τιμή που αναζητούμε.
Αν το στοιχείο δεν υπάρχει, κάποια στιγμή θα φτάσουμε σε ένα κενό υποδένδρο και εκεί τερματίζει η διαδικασία.
💡 Παρατήρηση: Ο αλγόριθμος αναζήτησης σε BST θυμίζει τη δυαδική αναζήτηση. Κάθε φορά αφήνουμε στην άκρη ένα υποδένδρο και συνεχίζουμε με το άλλο, περιορίζοντας δραματικά τους κόμβους που επισκεπτόμαστε.
⚖️ Επίδραση Μορφής Δένδρου στην Ταχύτητα
Η ταχύτητα της αναζήτησης εξαρτάται από τη δομή του δυαδικού δένδρου αναζήτησης:
Ισορροπημένο δένδρο: Η ρίζα χωρίζει το δένδρο σε υποδένδρα παρόμοιου μεγέθους. Η αναζήτηση είναι πολύ γρήγορη (λογαριθμική πολυπλοκότητα).
Μη ισορροπημένο δένδρο: Η ρίζα έχει ένα πολύ μεγάλο υποδένδρο και ένα πολύ μικρό. Η αναζήτηση μπορεί να χρειαστεί πολλά βήματα (γραμμική πολυπλοκότητα στη χειρότερη περίπτωση).
Παράδειγμα: Η αναζήτηση του 1 σε ένα ισορροπημένο δένδρο μπορεί να χρειαστεί 3 βήματα, ενώ σε ένα μη ισορροπημένο μπορεί να χρειαστεί 5 βήματα.
💡 Συμπέρασμα: Αν θέλουμε να έχουμε γρήγορους αλγορίθμους αναζήτησης, πρέπει να αποθηκεύουμε τις τιμές στα δυαδικά δένδρα αναζήτησης με έναν συγκεκριμένο τρόπο (δηλαδή να διατηρούμε το δένδρο όσο το δυνατόν πιο ισορροπημένο).
🏆 Πλεονεκτήματα Δυαδικών Δένδρων Αναζήτησης
Τα δυαδικά δένδρα αναζήτησης συνδυάζουν τα πλεονεκτήματα δύο δομών:
Λίστες: Όσον αφορά τις πράξεις της εισαγωγής και της διαγραφής.
Ταξινομημένοι πίνακες: Όσον αφορά την πράξη της αναζήτησης.
💡 Συμβουλή: Κάνε κλικ σε κάθε ερώτηση για να δεις την αναλυτική απάντηση.
1. Τι είναι ένα δένδρο και από τι αποτελείται;
▼
Ένα δένδρο (tree) είναι μια δομή που αποτελείται από ένα σύνολο κόμβων και ένα σύνολο ακμών μεταξύ των κόμβων. Οι βασικοί κανόνες που διέπουν ένα δένδρο είναι:
Υπάρχει ένας ξεχωριστός κόμβος, η ρίζα, που δεν έχει γονέα.
Για κάθε κόμβο εκτός από τη ρίζα, υπάρχει μόνο μια ακμή που τον συνδέει με τον γονέα του.
Υπάρχει μοναδική διαδρομή από τη ρίζα σε κάθε κόμβο.
2. Ποιος είναι ο ρόλος της ρίζας σε ένα δένδρο;
▼
Η ρίζα (root) είναι ένας ξεχωριστός κόμβος που:
Δεν έχει γονέα (δεν υπάρχει ακμή που να καταλήγει σε αυτόν από άλλον κόμβο).
Βρίσκεται στην κορυφή του δένδρου.
Αποτελεί το σημείο εκκίνησης για την πρόσβαση σε όλους τους υπόλοιπους κόμβους.
Το μόνο δένδρο που δεν έχει ρίζα είναι το κενό δένδρο (δεν έχει ούτε κόμβους ούτε ακμές).
3. Τι ονομάζουμε γονέα και παιδί σε ένα δένδρο;
▼
Όταν δύο κόμβοι συνδέονται με μια ακμή:
Ο κόμβος από τον οποίο ξεκινάει η ακμή ονομάζεται γονέας (parent).
Ο κόμβος στον οποίο καταλήγει η ακμή ονομάζεται παιδί (child).
Ένας κόμβος μπορεί να έχει κανένα, ένα ή περισσότερα παιδιά. Όλοι οι κόμβοι εκτός από τη ρίζα έχουν ακριβώς έναν γονέα.
4. Τι είναι τα φύλλα ενός δένδρου;
▼
Τα φύλλα (leaves) ενός δένδρου είναι οι κόμβοι που δεν έχουν παιδιά. Είναι οι κόμβοι που βρίσκονται στα "άκρα" του δένδρου.
Σε ένα δένδρο με έναν μόνο κόμβο, αυτός ο κόμβος είναι ταυτόχρονα και ρίζα και φύλλο.
5. Τι είναι τα αδέλφια σε ένα δένδρο;
▼
Αδέλφια (siblings) ονομάζονται οι κόμβοι που έχουν τον ίδιο γονέα. Για παράδειγμα, αν ο κόμβος Α έχει παιδιά τους κόμβους Β, Γ και Δ, τότε οι Β, Γ και Δ είναι αδέλφια.
6. Τι είναι τα υποδένδρα;
▼
Τα υποδένδρα είναι μικρότερα δένδρα που βρίσκονται μέσα σε ένα μεγαλύτερο δένδρο. Πιο συγκεκριμένα:
Κάθε κόμβος ενός δένδρου μπορεί να θεωρηθεί ως ρίζα ενός υποδένδρου.
Το υποδένδρο περιλαμβάνει τον κόμβο αυτόν και όλους τους απογόνους του.
Για παράδειγμα, σε ένα δένδρο με ρίζα 48 που έχει παιδιά 45 και 70, ο κόμβος 45 είναι ρίζα ενός υποδένδρου που περιλαμβάνει τον εαυτό του και τον απόγονό του 2.
7. Τι είναι το διατεταγμένο δένδρο;
▼
Διατεταγμένο δένδρο ονομάζεται το δένδρο στο οποίο για κάθε κόμβο υπάρχει μια γραμμική σχέση μεταξύ των παιδιών του, δηλαδή μας ενδιαφέρει η σειρά με την οποία εμφανίζονται τα παιδιά.
Σε ένα διατεταγμένο δένδρο, το αριστερό παιδί διαφέρει από το δεξιό παιδί — η ανταλλαγή τους δημιουργεί ένα διαφορετικό δένδρο.
8. Ποια είναι τα δύο κύρια πλεονεκτήματα των δένδρων;
▼
Τα δύο κύρια πλεονεκτήματα των δένδρων είναι:
Δυναμικότητα: Είναι πολύ εύκολο να προσθέσουμε, να αφαιρέσουμε ή να αναζητήσουμε ένα στοιχείο, αφού είναι δυναμική δομή δεδομένων.
Μεταφορά πληροφοριών: Η ιεραρχική δομή των δένδρων μεταφέρει πληροφορίες. Για παράδειγμα, στο σύστημα αρχείων, η διαδρομή "/users/student" προκύπτει από τη σχέση γονέα-παιδιού μεταξύ των καταλόγων.
9. Σε ποιους τομείς της Πληροφορικής χρησιμοποιούνται τα δένδρα;
10. Τι είναι τα δένδρα απόφασης και πού χρησιμοποιούνται;
▼
Τα δένδρα απόφασης είναι δένδρα στα οποία:
Κάθε κόμβος αντιπροσωπεύει ένα χαρακτηριστικό (ερώτηση).
Κάθε ακμή αντιπροσωπεύει μια απόφαση (απάντηση/κανόνα).
Κάθε φύλλο αντιπροσωπεύει ένα αποτέλεσμα.
Χρησιμοποιούνται σε:
Αλγορίθμους μηχανικής μάθησης (machine learning).
Ιατρικές διαγνώσεις (συμπτώματα → διάγνωση).
Παιχνίδια (σκάκι, τρίλιζα, τάβλι) μέσω του δένδρου παιχνιδιού.
11. Τι είναι το δυαδικό δένδρο;
▼
Ένα δυαδικό δένδρο (binary tree) είναι ένα διατεταγμένο δένδρο στο οποίο κάθε κόμβος έχει το πολύ δύο παιδιά:
Το αριστερό παιδί (left child).
Το δεξιό παιδί (right child).
Μπορούμε να μιλάμε για αριστερό και δεξιό υποδένδρο κάθε κόμβου. Αν ανταλλάξουμε τα δύο υποδένδρα, παίρνουμε ένα διαφορετικό δυαδικό δένδρο.
12. Τι είναι το δυαδικό δένδρο αναζήτησης (BST);
▼
Ένα δυαδικό δένδρο αναζήτησης (Binary Search Tree - BST) είναι ένα δυαδικό δένδρο που ικανοποιεί την εξής ιδιότητα για κάθε κόμβο u:
Όλοι οι κόμβοι του αριστερού υποδένδρου έχουν τιμές μικρότερες από την τιμή του u.
Όλοι οι κόμβοι του δεξιού υποδένδρου έχουν τιμές μεγαλύτερες ή ίσες από την τιμή του u.
Προσοχή: Η ιδιότητα πρέπει να ισχύει για όλους τους κόμβους, όχι μόνο για τη ρίζα. Αν ένας κόμβος με τιμή 3 είναι παιδί του κόμβου 1, αλλά ο κόμβος 1 ανήκει στο αριστερό υποδένδρο του κόμβου 2, τότε το δένδρο δεν είναι BST, γιατί 3 > 2.
13. Πώς γίνεται η αναζήτηση σε ένα BST;
▼
Η αναζήτηση σε ένα δυαδικό δένδρο αναζήτησης γίνεται ως εξής:
Ξεκινάμε από τη ρίζα του δένδρου.
Συγκρίνουμε το στοιχείο που αναζητούμε με την τιμή του τρέχοντος κόμβου.
Αν είναι μικρότερο, πηγαίνουμε στο αριστερό υποδένδρο.
Αν είναι μεγαλύτερο ή ίσο, πηγαίνουμε στο δεξιό υποδένδρο.
Επαναλαμβάνουμε μέχρι να βρούμε τον κόμβο ή να φτάσουμε σε κενό υποδένδρο (το στοιχείο δεν υπάρχει).
Ο αλγόριθμος αυτός θυμίζει τη δυαδική αναζήτηση σε ταξινομημένο πίνακα. Κάθε βήμα αποκλείει το μισό υποδένδρο, περιορίζοντας δραματικά τους κόμβους που ελέγχουμε.
14. Πώς επηρεάζεται η ταχύτητα αναζήτησης από τη μορφή του BST;
▼
Η ταχύτητα της αναζήτησης εξαρτάται άμεσα από το πόσο ισορροπημένο είναι το δένδρο:
Ισορροπημένο δένδρο: Οι κόμβοι κατανέμονται ομοιόμορφα. Η αναζήτηση απαιτεί λίγα βήματα (περίπου log₂(N) για N κόμβους).
Μη ισορροπημένο δένδρο: Ένα υποδένδρο είναι πολύ μεγαλύτερο από το άλλο. Στη χειρότερη περίπτωση (δένδρο που μοιάζει με λίστα), η αναζήτηση μπορεί να απαιτήσει N βήματα.
Για γρήγορη αναζήτηση, πρέπει να διατηρούμε το δένδρο όσο το δυνατόν πιο ισορροπημένο.
15. Ποια πλεονεκτήματα συνδυάζει ένα BST;
▼
Τα δυαδικά δένδρα αναζήτησης συνδυάζουν τα πλεονεκτήματα δύο δομών:
Λίστες: Όσον αφορά τις πράξεις της εισαγωγής και της διαγραφής στοιχείων (εύκολες και γρήγορες λόγω δυναμικής δομής).
Ταξινομημένοι πίνακες: Όσον αφορά την πράξη της αναζήτησης (γρήγορη αναζήτηση παρόμοια με τη δυαδική αναζήτηση).
🎯 Οδηγίες: Επίλεξε μία απάντηση σε κάθε ερώτηση. Θα δεις άμεση ανατροφοδότηση. Στο τέλος θα εμφανιστεί το συνολικό σου σκορ.
1. Ποιος κόμβος σε ένα δένδρο δεν έχει γονέα;
α) Το φύλλο
β) Η ρίζα
γ) Το παιδί
δ) Το αδέρφι
2. Πόσοι γονείς έχει κάθε κόμβος ενός δένδρου εκτός από τη ρίζα;
α) Κανέναν
β) Δύο
γ) Ακριβώς έναν
δ) Τουλάχιστον έναν
3. Τι είναι οι κόμβοι χωρίς παιδιά σε ένα δένδρο;
α) Φύλλα
β) Ρίζες
γ) Γονείς
δ) Υποδένδρα
4. Ποιο είναι το μόνο δένδρο που δεν έχει ρίζα;
α) Το δυαδικό δένδρο
β) Το δένδρο με έναν κόμβο
γ) Το διατεταγμένο δένδρο
δ) Το κενό δένδρο
5. Σε ένα διατεταγμένο δένδρο, τι μας ενδιαφέρει για τα παιδιά ενός κόμβου;
α) Ο αριθμός τους
β) Η σειρά τους
γ) Το άθροισμά τους
δ) Το χρώμα τους
6. Σε ένα δυαδικό δένδρο, πόσα παιδιά μπορεί να έχει το πολύ ένας κόμβος;
α) Ένα
β) Τρία
γ) Δύο
δ) Άπειρα
7. Σε ένα BST, πού βρίσκονται οι κόμβοι με τιμές μικρότερες από τη ρίζα;
α) Στο αριστερό υποδένδρο
β) Στο δεξιό υποδένδρο
γ) Στα φύλλα
δ) Στη ρίζα
8. Αν ανταλλάξουμε το αριστερό με το δεξιό υποδένδρο ενός κόμβου σε δυαδικό δένδρο, τι συμβαίνει;
α) Τίποτα, παραμένει το ίδιο
β) Παίρνουμε διαφορετικό δένδρο
γ) Το δένδρο γίνεται κενό
δ) Ο κόμβος γίνεται ρίζα
9. Ποια δομή θυμίζει ο αλγόριθμος αναζήτησης σε BST;
α) Σειριακή αναζήτηση
β) Αναζήτηση με πλήρη διερεύνηση
γ) Δυαδική αναζήτηση
δ) Αναζήτηση με hash
10. Τι συνδυάζει ένα BST από άλλες δομές;
α) Την ευκολία εισαγωγής/διαγραφής των λιστών και την ταχύτητα αναζήτησης των ταξινομημένων πινάκων
β) Την απλότητα του πίνακα και το μέγεθος της στοίβας
γ) Την ταχύτητα της ουράς και την ευελιξία της λίστας
δ) Το στατικό μέγεθος του πίνακα και τη δυναμικότητα της ουράς
🏆 Τελικό Σκορ
💪 Προκλήσεις: Προσπάθησε να τις λύσεις μόνος σου πριν δεις την απάντηση!
Άσκηση 1: Αναγνώριση στοιχείων δένδρου
⭐
Δίνεται το παρακάτω δένδρο:
10
/ \
5 15
/ \ / \
3 7 12 20
Ερωτήσεις:
Ποιος είναι η ρίζα του δένδρου;
Ποιοι είναι οι γονείς των κόμβων 3, 12 και 20;
Ποια είναι τα φύλλα του δένδρου;
Ποια είναι τα αδέλφια του κόμβου 7;
Λύση:
Η ρίζα είναι ο κόμβος 10.
Ο γονέας του 3 είναι ο 5. Ο γονέας του 12 είναι ο 15. Ο γονέας του 20 είναι ο 15.
Τα φύλλα είναι οι κόμβοι: 3, 7, 12, 20 (δεν έχουν παιδιά).
Τα αδέλφια του 7 είναι ο κόμβος 3 (έχουν τον ίδιο γονέα, τον 5).
Άσκηση 2: Έλεγχος BST
⭐⭐
Εξέτασε αν τα παρακάτω δένδρα είναι δυαδικά δένδρα αναζήτησης (BST). Αν όχι, εξήγησε γιατί.
Δένδρο Β:✗ Δεν είναι BST. Ο κόμβος 9 είναι παιδί του κόμβου 3 (αριστερό υποδένδρο), αλλά 9 > 3. Επίσης, 9 > 8 (ρίζα), επομένως δεν μπορεί να βρίσκεται στο αριστερό υποδένδρο της ρίζας.
Άσκηση 3: Αναζήτηση σε BST
⭐⭐
Δίνεται το παρακάτω BST:
50
/ \
30 70
/ \ / \
20 40 60 80
/
65
Ερωτήσεις:
Περιέγραψε τα βήματα αναζήτησης του αριθμού 65.
Περιέγραψε τα βήματα αναζήτησης του αριθμού 25 (που δεν υπάρχει).
Πόσες συγκρίσεις χρειάζονται για να βρούμε το 65; Και για το 25;
Λύση:
1. Αναζήτηση 65:
Σύγκριση 65 με ρίζα 50: 65 > 50 → πάμε δεξιά.
Σύγκριση 65 με 70: 65 < 70 → πάμε αριστερά.
Σύγκριση 65 με 60: 65 > 60 → πάμε δεξιά.
Βρήκαμε τον κόμβο 65!
2. Αναζήτηση 25:
Σύγκριση 25 με ρίζα 50: 25 < 50 → πάμε αριστερά.
Σύγκριση 25 με 30: 25 < 30 → πάμε αριστερά.
Σύγκριση 25 με 20: 25 > 20 → πάμε δεξιά.
Κενό υποδένδρο! Ο αριθμός 25 δεν υπάρχει στο δένδρο.
3. Συγκρίσεις: Για το 65 χρειάστηκαν 4 συγκρίσεις. Για το 25 χρειάστηκαν 3 συγκρίσεις (μέχρι να φτάσουμε σε κενό υποδένδρο).
Άσκηση 4: Υποδένδρα και Ιεραρχία
⭐⭐⭐
Ένα σχολείο έχει την εξής ιεραρχία:
Διευθυντής Σχολείου
Υποδιευθυντής (αναφέρεται στον Διευθυντή)
Υπεύθυνος Τμήματος Α (αναφέρεται στον Υποδιευθυντή)
Υπεύθυνος Τμήματος Β (αναφέρεται στον Υποδιευθυντή)
Καθηγητής 1 (αναφέρεται στον Υπεύθυνο Τμήματος Α)
Καθηγητής 2 (αναφέρεται στον Υπεύθυνο Τμήματος Α)
Καθηγητής 3 (αναφέρεται στον Υπεύθυνο Τμήματος Β)
Ερωτήσεις:
Σχεδίασε το δένδρο που αναπαριστά αυτή την ιεραρχία.
Ποιοι είναι οι κόμβοι-φύλλα;
Πόσα υποδένδρα έχει ο Υποδιευθυντής;
Αν αφαιρέσουμε τον Υποδιευθυντή, πόσα ξεχωριστά δένδρα δημιουργούνται;
Η ισορροπία είναι σημαντική γιατί καθορίζει την πολυπλοκότητα της αναζήτησης. Σε ισορροπημένο δένδρο με Ν κόμβους, η αναζήτηση απαιτεί περίπου log₂(N) βήματα. Σε μη ισορροπημένο δένδρο, στη χειρότερη περίπτωση μπορεί να απαιτήσει N βήματα (όπως σε μια απλή λίστα).