Λίστες, δένδρα, γράφοι
Βιβλίο 2 §1.3 · Άλλες δομές δεδομένων: λίστες, δένδρα, γράφοι
Οι φάκελοι στον υπολογιστή σου σχηματίζουν ένα δένδρο. Οι φίλοι σου στο Instagram και οι δρόμοι στο Google Maps σχηματίζουν γράφους. Η λίστα αναπαραγωγής όπου προσθέτεις και αφαιρείς τραγούδια οπουδήποτε θυμίζει λίστα.
Οι πίνακες είναι σπουδαίοι, αλλά έχουν σταθερό μέγεθος και «δύσκαμπτη» δομή. Εδώ γνωρίζεις τις δυναμικές δομές που λύνουν αυτά τα προβλήματα.
Λίστες
Μια συνδεδεμένη λίστα αποτελείται από κόμβους. Κάθε κόμβος έχει δύο μέρη:
- το δεδομένο (την τιμή που αποθηκεύει) και
- έναν δείκτη που δείχνει στον επόμενο κόμβο.
Ο δείκτης του τελευταίου κόμβου δεν δείχνει πουθενά (κενός δείκτης, nil). Ξέρουμε πού αρχίζει η λίστα από έναν ξεχωριστό δείκτη προς τον πρώτο κόμβο.
Οι κόμβοι δεν χρειάζεται να βρίσκονται σε συνεχόμενες θέσεις μνήμης — γι' αυτό η λίστα είναι δυναμική δομή: μεγαλώνει και μικραίνει κατά την εκτέλεση.
Εισαγωγή και διαγραφή σε λίστα
Εισαγωγή νέου κόμβου Ν ανάμεσα στους Α και Β:
- ο δείκτης του Ν δείχνει στον Β,
- ο δείκτης του Α δείχνει πλέον στον Ν.
Διαγραφή του κόμβου Β που βρίσκεται ανάμεσα στους Α και Γ: ο δείκτης του Α δείχνει πλέον στον Γ — ο Β «παρακάμπτεται».
Πλεονέκτημα: εισαγωγές και διαγραφές χωρίς μετακίνηση άλλων στοιχείων (σε πίνακα θα έπρεπε να μετακινηθούν όλα τα επόμενα). Μειονέκτημα: δεν υπάρχει άμεση πρόσβαση στο k-οστό στοιχείο — πρέπει να ακολουθήσεις τους δείκτες από την αρχή· επίσης οι δείκτες καταλαμβάνουν επιπλέον μνήμη.
Σε μια συνδεδεμένη λίστα θέλουμε να εισαγάγουμε έναν νέο κόμβο Ν μετά τον κόμβο Α. Ποια σειρά ενεργειών είναι σωστή;
Δένδρα
Το δένδρο είναι μια ιεραρχική δομή κόμβων:
- Ρίζα: ο μοναδικός κόμβος χωρίς γονέα, στην κορυφή.
- Κάθε άλλος κόμβος έχει ακριβώς έναν γονέα και μπορεί να έχει παιδιά.
- Φύλλα (τερματικοί κόμβοι): κόμβοι χωρίς παιδιά.
- Επίπεδο: η ρίζα είναι στο επίπεδο 0 (ή 1, ανάλογα με τη σύμβαση), τα παιδιά της στο επόμενο κ.ο.κ.
Δυαδικό δένδρο: κάθε κόμβος έχει το πολύ δύο παιδιά (αριστερό και δεξί).
Παραδείγματα: το δένδρο φακέλων του υπολογιστή, το γενεαλογικό δένδρο, το διάγραμμα ανάλυσης ενός προβλήματος από πάνω προς τα κάτω.
Γράφοι
Ένας γράφος αποτελείται από ένα σύνολο κόμβων (κορυφών) και ένα σύνολο ακμών που συνδέουν ζεύγη κόμβων. Σε αντίθεση με το δένδρο, δεν υπάρχει ιεραρχία ούτε ρίζα, και μπορεί να υπάρχουν κύκλοι (διαδρομές που επιστρέφουν στην αφετηρία).
- Κατευθυνόμενος γράφος: οι ακμές έχουν φορά (π.χ. μονόδρομοι, «ακολουθώ» στα social media).
- Μη κατευθυνόμενος: οι ακμές ισχύουν και προς τις δύο κατευθύνσεις (π.χ. φιλία).
- Με βάρη: κάθε ακμή έχει μια τιμή (π.χ. απόσταση σε km).
Το δένδρο είναι ειδική περίπτωση γράφου: συνδεδεμένος γράφος χωρίς κύκλους.
Ποια δομή είναι η καταλληλότερη για να αναπαραστήσει το οδικό δίκτυο μεταξύ πόλεων με τις αποστάσεις τους;
Μέθοδος: ποια δομή ταιριάζει;
- Υπάρχει ιεραρχία (γονέας–παιδί, ένας γονέας για κάθε στοιχείο); → δένδρο.
- Υπάρχουν αυθαίρετες συνδέσεις, πιθανόν με κύκλους; → γράφος (με βάρη αν οι συνδέσεις έχουν κόστος).
- Γραμμική σειρά με συχνές εισαγωγές/διαγραφές στη μέση; → λίστα.
- Γραμμική σειρά με γνωστό πλήθος και άμεση πρόσβαση κατά θέση; → πίνακας.
- Πρόσβαση μόνο από τα άκρα; → στοίβα (ένα άκρο) ή ουρά (δύο άκρα).
Παράδειγμα 1: Σε ένα δένδρο η ρίζα Α έχει παιδιά Β, Γ, Δ. Ο Β έχει παιδιά Ε, Ζ και ο Δ έχει παιδί Η. Βρες: τα φύλλα, τον γονέα του Η, το πλήθος των ακμών. Είναι δυαδικό;
Λύση:
- Φύλλα (χωρίς παιδιά): Ε, Ζ, Γ, Η.
- Γονέας του Η: Δ.
- Κόμβοι: Α, Β, Γ, Δ, Ε, Ζ, Η = 7, άρα ακμές (Α–Β, Α–Γ, Α–Δ, Β–Ε, Β–Ζ, Δ–Η ✓).
- Όχι δυαδικό: ο Α έχει τρία παιδιά.
Θέμα τύπου Πανελλαδικών: Να αναφέρετε ένα πλεονέκτημα και ένα μειονέκτημα της συνδεδεμένης λίστας σε σχέση με τον πίνακα, και να εξηγήσετε πώς γίνεται η διαγραφή ενός κόμβου.
Λύση: Πλεονέκτημα: οι εισαγωγές και διαγραφές γίνονται μόνο με αλλαγή δεικτών, χωρίς μετακίνηση των υπόλοιπων στοιχείων· επιπλέον το μέγεθος δεν είναι σταθερό (δυναμική δομή). Μειονέκτημα: δεν υπάρχει άμεση πρόσβαση σε στοιχείο με βάση τη θέση του — η προσπέλαση γίνεται σειριακά από τον πρώτο κόμβο· επίσης απαιτείται επιπλέον μνήμη για τους δείκτες.
Διαγραφή του κόμβου Β (με προηγούμενο τον Α): ο δείκτης του Α παίρνει την τιμή του δείκτη του Β, δηλαδή δείχνει στον κόμβο που ακολουθούσε τον Β. Ο Β δεν ανήκει πλέον στη λίστα και η μνήμη του μπορεί να ελευθερωθεί.
Ένα δένδρο έχει 15 κόμβους. Πόσες ακμές έχει;
Παράδειγμα 2: Σε ένα μικρό κοινωνικό δίκτυο πέντε φίλων υπάρχουν οι φιλίες Α–Β, Α–Γ, Β–Γ, Γ–Δ, Δ–Ε. Περιέγραψε τον γράφο. Είναι δένδρο;
Λύση:
- Κόμβοι: 5 (Α, Β, Γ, Δ, Ε) · ακμές: 5.
- Μη κατευθυνόμενος: η φιλία ισχύει και προς τις δύο κατευθύνσεις.
- Υπάρχει κύκλος: Α → Β → Γ → Α.
- Δεν είναι δένδρο: ένα δένδρο 5 κόμβων θα είχε ακμές και κανέναν κύκλο. Αν αφαιρεθεί η ακμή Β–Γ, ο γράφος γίνεται δένδρο.
Η θεωρία γράφων γεννήθηκε το 1736, όταν ο Leonhard Euler απέδειξε ότι δεν γίνεται να κάνεις βόλτα στο Königsberg περνώντας από κάθε μία από τις επτά γέφυρές του ακριβώς μία φορά. Αναπαρέστησε τις περιοχές της πόλης ως κόμβους και τις γέφυρες ως ακμές — τον πρώτο γράφο της ιστορίας.
Σε ένα πλήρες δυαδικό δένδρο κάθε εσωτερικός κόμβος έχει ακριβώς δύο παιδιά και όλα τα φύλλα είναι στο ίδιο επίπεδο. Αν έχει 5 επίπεδα, πόσους κόμβους και πόσα φύλλα έχει; Πόσες «ερωτήσεις ναι/όχι» χρειάζονται για να φτάσεις από τη ρίζα σε οποιοδήποτε φύλλο;
Δοκίμασε πρώτα μόνος σου — μετά δες τη λύση
Τα επίπεδα έχουν 1, 2, 4, 8, 16 κόμβους, άρα σύνολο . Φύλλα: οι 16 του τελευταίου επιπέδου. Από τη ρίζα στο φύλλο περνάς 4 ακμές, δηλαδή 4 επιλογές «αριστερά ή δεξιά». Έτσι, με 4 ερωτήσεις ναι/όχι ξεχωρίζεις ένα από 16 αντικείμενα — η ίδια ιδέα με τη δυαδική αναζήτηση.
- «Το δένδρο μπορεί να έχει κύκλους.» Όχι — αν έχει κύκλο είναι γενικός γράφος.
- «Ένας κόμβος δένδρου μπορεί να έχει δύο γονείς.» Όχι — ακριβώς ένας γονέας, εκτός από τη ρίζα που δεν έχει κανέναν.
- Στην εισαγωγή σε λίστα αλλάζεις πρώτα τον δείκτη του προηγούμενου κόμβου και χάνεις τη συνέχεια της λίστας.
- Λίστα: κόμβοι με δεδομένο + δείκτη στον επόμενο· εισαγωγή/διαγραφή με αλλαγή δεικτών, χωρίς μετακινήσεις.
- Δένδρο: ιεραρχία, μία ρίζα, ένας γονέας ανά κόμβο, φύλλα χωρίς παιδιά· n κόμβοι → n − 1 ακμές.
- Δυαδικό δένδρο: έως δύο παιδιά ανά κόμβο.
- Γράφος: κόμβοι και ακμές χωρίς ιεραρχία· κατευθυνόμενος ή όχι, με ή χωρίς βάρη.
- Λίστες, δένδρα, γράφοι είναι δυναμικές δομές που χρησιμοποιούν δείκτες.