🌳 Δένδρα: Μία Μη Γραμμική Δομή Δεδομένων

🌲 Τι είναι το Δέντρο;

Τα δένδρα είναι μια ιδιαίτερη μη γραμμική δομή δεδομένων όπου κάθε στοιχείο (ή κόμβος) συνδέεται με ένα ή περισσότερα στοιχεία. Στην επιστήμη της Πληροφορικής, το δέντρο εμφανίζεται αντίστροφα σε σχέση με τη φύση: η ρίζα είναι στο πάνω μέρος και τα φύλλα στο κάτω μέρος. Ένα δέντρο αποτελείται από κόμβους που συνδέονται μεταξύ τους με ακμές (γραμμές).

👪 Σχέσεις στους Κόμβους του Δέντρου

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

🧬 Υποδέντρα

Κάθε κόμβος μπορεί να θεωρηθεί ως η ρίζα ενός υποδέντρου. Ένα υποδέντρο είναι μέρος ενός μεγαλύτερου δένδρου. Στην Εικόνα 1.3.14, βλέπουμε τον κόμβο 48 να έχει δύο υποδέντρα: ένα με ρίζα τον κόμβο 45 και ένα με ρίζα τον κόμβο 70.

📚 Πού Χρησιμοποιούνται τα Δέντρα;

Τα δέντρα χρησιμοποιούνται σε πολλές εφαρμογές της Πληροφορικής:

1. Οικογενειακά δέντρα: Αναπαριστούν τις σχέσεις γονέων-παιδιών (Εικόνα 1.3.12).
2. Κατάλογοι αρχείων: Δείχνουν τη δομή των φακέλων σε ένα υπολογιστικό σύστημα (Εικόνα 1.3.16).
3. Λεξικά: Οργανώνουν τις λέξεις με τρόπο που διευκολύνει την αναζήτηση (Εικόνα 1.3.17).

🌲 Δέντρα Αποφάσεων

Τα δέντρα αποφάσεων χρησιμοποιούνται για τη λήψη αποφάσεων σε διάφορα προβλήματα. Κάθε κόμβος αντιπροσωπεύει μια επιλογή ή απόφαση, και οι ακμές αντιπροσωπεύουν τα πιθανά αποτελέσματα. Στην Εικόνα 1.3.19, βλέπουμε ένα παράδειγμα δέντρου απόφασης που απαντά στο ερώτημα αν τα παράθυρα είναι καθαρά.

⚔️ Δένδρα στα Παιχνίδια

Στα παιχνίδια στρατηγικής, τα δέντρα παιχνιδιού (game trees) μοντελοποιούν όλες τις πιθανές κινήσεις των παικτών, αναπαριστώντας τη διαδοχή καταστάσεων του παιχνιδιού (Εικόνα 1.3.20).

🔄 Ιδιότητες των Δέντρων

1. Ιεραρχική δομή: Τα δέντρα οργανώνουν δεδομένα σε επίπεδα.
2. Μοναδική διαδρομή: Υπάρχει μόνο ένας τρόπος να φτάσουμε από τη ρίζα σε οποιονδήποτε κόμβο.
3. Μη γραμμικότητα: Σε αντίθεση με λίστες ή πίνακες, τα δέντρα είναι μη γραμμικές δομές δεδομένων.

🔀 Δυαδικά Δένδρα

Ένα δυαδικό δέντρο (binary tree) είναι ένας ειδικός τύπος δέντρου όπου κάθε κόμβος έχει το πολύ δύο παιδιά: το αριστερό παιδί και το δεξί παιδί.

Στο παράδειγμα της Εικόνας 1.3.21, βλέπουμε ένα δυαδικό δέντρο με τους αριθμούς ως κόμβους και τα παιδιά τους διατεταγμένα ανάλογα με τα κριτήρια που μόλις περιγράψαμε.

🔍 Δυαδικά Δένδρα Αναζήτησης

Τα δυαδικά δέντρα αναζήτησης είναι ένας τύπος δυαδικού δέντρου που επιτρέπει την γρήγορη αναζήτηση στοιχείων. Κάθε κόμβος έχει δύο υποδέντρα:

• Το αριστερό υποδέντρο περιέχει στοιχεία μικρότερα από τον κόμβο.
• Το δεξί υποδέντρο περιέχει στοιχεία μεγαλύτερα από τον κόμβο.

Στην Εικόνα 1.3.22 βλέπουμε ένα τέτοιο δέντρο, όπου τα στοιχεία είναι διατεταγμένα με τέτοιο τρόπο ώστε να επιτρέπουν γρήγορη αναζήτηση με βάση την παραπάνω λογική.

⚡ Αλγόριθμοι Αναζήτησης σε Δυαδικά Δένδρα

Η αναζήτηση σε ένα δυαδικό δέντρο αναζήτησης είναι πολύ πιο αποτελεσματική από ό,τι σε μια γραμμική δομή, όπως πίνακες ή λίστες. Όταν αναζητάμε ένα στοιχείο, ξεκινάμε από τη ρίζα και συγκρίνουμε το στοιχείο που αναζητάμε με αυτό της ρίζας:

• Εάν το στοιχείο είναι μικρότερο από τη ρίζα, προχωράμε στο αριστερό υποδέντρο.
• Εάν το στοιχείο είναι μεγαλύτερο, προχωράμε στο δεξί υποδέντρο.

Στην Εικόνα 1.3.24 βλέπουμε πώς πραγματοποιείται αυτή η αναζήτηση βήμα-βήμα σε ένα δυαδικό δέντρο. Ο αλγόριθμος μας επιτρέπει να εντοπίσουμε το ζητούμενο στοιχείο γρήγορα, χωρίς να εξετάσουμε όλους τους κόμβους του δέντρου.

📊 Σύγκριση Δυαδικών Δένδρων και Ταξινομημένων Πινάκων

Τα δυαδικά δέντρα αναζήτησης προσφέρουν πλεονεκτήματα έναντι των ταξινομημένων πινάκων:

• Η εισαγωγή και διαγραφή στοιχείων είναι πιο εύκολη σε ένα δυαδικό δέντρο.
• Οι πίνακες απαιτούν αναδιάταξη όταν προσθέτουμε ή αφαιρούμε στοιχεία, ενώ στα δέντρα η δομή διατηρείται χωρίς αλλαγές.