Μη Γραμμικές Δομές Δεδομένων

Εισαγωγή στις Μη Γραμμικές Δομές Δεδομένων

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

Δέντρα (Trees): Ιεραρχικές δομές με κόμβους που έχουν γονείς και παιδιά.
Δυαδικά Δέντρα (Binary Trees): Δέντρα όπου κάθε κόμβος έχει το πολύ δύο παιδιά.
Γράφοι (Graphs): Δομές που αποτελούνται από κόμβους και ακμές που συνδέουν τους κόμβους.

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

Δέντρα (Trees)

Χαρακτηριστικά

Ιεραρχική δομή: Οι κόμβοι είναι οργανωμένοι σε ιεραρχία, με έναν κόμβο ρίζας (root) που δεν έχει γονέα.
Γονείς και Παιδιά: Κάθε κόμβος (εκτός από τον ρίζα) έχει έναν γονέα και μπορεί να έχει πολλαπλούς απογόνους (παιδιά).
Μονοπάτια: Υπάρχει ένα μοναδικό μονοπάτι από τον ρίζα σε κάθε κόμβο.
Βάθος: Το βάθος ενός κόμβου είναι ο αριθμός των ακμών από τον ρίζα μέχρι τον κόμβο.
Ύψος: Το ύψος ενός δέντρου είναι το μέγιστο βάθος οποιουδήποτε κόμβου.

Βασικοί Όροι

Ρίζα (Root): Ο κόμβος που δεν έχει γονέα.
Φύλλο (Leaf): Ένας κόμβος που δεν έχει παιδιά.
Εσωτερικός Κόμβος (Internal Node): Ένας κόμβος που έχει τουλάχιστον ένα παιδί.
Αδερφός Κόμβος (Sibling): Κόμβοι που έχουν τον ίδιο γονέα.
Υποδέντρο (Subtree): Ένα δέντρο που αποτελεί μέρος ενός μεγαλύτερου δέντρου.

Παραδείγματα Χρήσης

Αναπαράσταση ιεραρχικών δεδομένων (π.χ. φάκελοι και αρχεία σε ένα σύστημα αρχείων).
Οργανώγραμμα μιας εταιρείας.
Αναπαράσταση μαθηματικών εκφράσεων.
Αλγόριθμοι αναζήτησης (π.χ. Depth-First Search, Breadth-First Search).

Πλεονεκτήματα και Μειονεκτήματα

Πλεονεκτήματα:
- Αποδοτική αναζήτηση, εισαγωγή και διαγραφή.
- Καλή αναπαράσταση ιεραρχικών δεδομένων.
- Εύκολη περιήγηση και διασχίση.
Μειονεκτήματα:
- Πιο σύνθετη υλοποίηση από τις γραμμικές δομές.
- Απαίτηση για επιπλέον μνήμη για τους δείκτες των κόμβων.

Διάγραμμα Δέντρου

Παρακάτω είναι ένα παράδειγμα ενός δέντρου:

        Α (Ρίζα)
       / \
      Β   Γ
     / \   \
    Δ   Ε   Ζ

Εδώ, ο κόμβος Α είναι η ρίζα, οι Β και Γ είναι παιδιά του Α, και οι Δ, Ε, Ζ είναι φύλλα.

Δυαδικά Δέντρα (Binary Trees)

Χαρακτηριστικά

Δυαδική δομή: Κάθε κόμβος έχει το πολύ δύο παιδιά: ένα αριστερό και ένα δεξιό.
Υποδέντρα: Το αριστερό και το δεξιό υποδέντρο ενός κόμβου είναι επίσης δυαδικά δέντρα.
Ισορροπία: Ένα δυαδικό δέντρο μπορεί να είναι ισορροπημένο ή μη ισορροπημένο.

Τύποι Δυαδικών Δέντρων

Δυαδικό Δέντρο Αναζήτησης (Binary Search Tree - BST):
- Για κάθε κόμβο, όλα τα στοιχεία στο αριστερό υποδέντρο είναι μικρότερα από τον κόμβο.
- Όλα τα στοιχεία στο δεξιό υποδέντρο είναι μεγαλύτερα από τον κόμβο.
Πλήρες Δυαδικό Δέντρο (Full Binary Tree): Κάθε κόμβος έχει είτε 0 είτε 2 παιδιά.
Τέλειο Δυαδικό Δέντρο (Perfect Binary Tree): Όλα τα επίπεδα είναι πλήρως γεμάτα.
Ισορροπημένο Δυαδικό Δέντρο (Balanced Binary Tree): Το ύψος των αριστερών και δεξιών υποδέντρων κάθε κόμβου διαφέρει το πολύ κατά 1.

Βασικές Λειτουργίες

Εισαγωγή: Προσθήκη ενός νέου κόμβου στο δέντρο σύμφωνα με τις ιδιότητες του BST.
Διαγραφή: Αφαίρεση ενός κόμβου από το δέντρο.
Αναζήτηση: Εύρεση ενός κόμβου στο δέντρο.
Διασχίσεις:
- In-order: Αριστερό υποδέντρο → Κόμβος → Δεξιό υποδέντρο.
- Pre-order: Κόμβος → Αριστερό υποδέντρο → Δεξιό υποδέντρο.
- Post-order: Αριστερό υποδέντρο → Δεξιό υποδέντρο → Κόμβος.
- Level-order: Διασχίση κατά επίπεδο (BFS).

Παραδείγματα Χρήσης

Δομές δεδομένων για γρήγορη αναζήτηση (π.χ. βάσεις δεδομένων).
Υλοποίηση λεξικών.
Αλγόριθμοι ταξινόμησης (π.χ. QuickSort).
Αναπαράσταση μαθηματικών εκφράσεων.

Πλεονεκτήματα και Μειονεκτήματα

Πλεονεκτήματα:
- Γρήγορη αναζήτηση, εισαγωγή και διαγραφή (O(log n) σε ισορροπημένο δέντρο).
- Αποδοτική αποθήκευση ιεραρχικών δεδομένων.
Μειονεκτήματα:
- Σε μη ισορροπημένα δέντρα, οι λειτουργίες μπορεί να είναι αργές (O(n)).
- Πιο σύνθετη υλοποίηση από τις γραμμικές δομές.

Διάγραμμα Δυαδικού Δέντρου

Παρακάτω είναι ένα παράδειγμα ενός δυαδικού δέντρου αναζήτησης:

          8 (Ρίζα)
         /   \
        3     10
       / \     \
      1   6     14
         / \    /
        4   7  13

Εδώ, ο κόμβος 8 είναι η ρίζα, και το δέντρο ικανοποιεί την ιδιότητα του BST.

Γράφοι (Graphs)

Χαρακτηριστικά

Κόμβοι και Ακμές: Οι γράφοι αποτελούνται από κόμβους (vertices) και ακμές (edges) που συνδέουν τους κόμβους.
Κατευθυνόμενοι vs Μη Κατευθυνόμενοι:
- Κατευθυνόμενοι Γράφοι: Οι ακμές έχουν κατεύθυνση (π.χ. από τον κόμβο Α στον κόμβο Β).
- Μη Κατευθυνόμενοι Γράφοι: Οι ακμές δεν έχουν κατεύθυνση.
Βάρος Ακμών: Οι ακμές μπορούν να έχουν βάρη (π.χ. απόσταση μεταξύ δύο κόμβων).
Κύκλοι: Ένας γράφος μπορεί να περιέχει κύκλους (cycles).
Συνεκτικότητα: Ένας γράφος μπορεί να είναι συνεκτικός (όλοι οι κόμβοι είναι συνδεδεμένοι) ή μη συνεκτικός.

Βασικοί Όροι

Κόμβος (Vertex): Ένα βασικό στοιχείο του γράφου.
Ακμή (Edge): Μια σύνδεση μεταξύ δύο κόμβων.
Βαθμός Κόμβου (Degree): Ο αριθμός των ακμών που συνδέονται με έναν κόμβο.
Μονοπάτι (Path): Μια ακολουθία κόμβων όπου κάθε ζεύγος διαδοχικών κόμβων συνδέεται με μια ακμή.
Κύκλος (Cycle): Ένα μονοπάτι που ξεκινά και τελειώνει στον ίδιο κόμβο.

Αναπαράσταση Γράφων

Μήτρα Γειτνίασης (Adjacency Matrix):\n
- Ένας πίνακας όπου κάθε κελί (i, j) δείχνει αν υπάρχει ακμή μεταξύ του κόμβου i και j.
- Καλή για πυκνούς γράφους (πολλές ακμές).
Λίστα Γειτνίασης (Adjacency List):
- Μια λίστα όπου κάθε κόμβος έχει μια λίστα με τους γειτονικούς του κόμβους.
- Καλή για αραιούς γράφους (λίγες ακμές).

Βασικές Λειτουργίες

Προσθήκη Κόμβου: Προσθήκη ενός νέου κόμβου στο γράφο.
Προσθήκη Ακμής: Προσθήκη μιας νέας ακμής μεταξύ δύο κόμβων.
Διαγραφή Κόμβου: Αφαίρεση ενός κόμβου και όλων των ακμών που συνδέονται με αυτόν.
Διαγραφή Ακμής: Αφαίρεση μιας ακμής μεταξύ δύο κόμβων.
Αναζήτηση: Εύρεση ενός κόμβου ή μιας ακμής.

Παραδείγματα Χρήσης

Δίκτυα υπολογιστών.
Δίκτυα κοινωνικής δικτύωσης.
Χάρτες και συστήματα πλοήγησης (π.χ. GPS).
Αλγόριθμοι βέλτιστου μονοπατιού (π.χ. Dijkstra, A*).

Πλεονεκτήματα και Μειονεκτήματα

Πλεονεκτήματα:
- Πολύ ευέλικτη δομή για αναπαράσταση σύνθετων σχέσεων.
- Μπορεί να αναπαραστήσει οποιοδήποτε είδος σχέσης μεταξύ δεδομένων.
Μειονεκτήματα:
- Πιο σύνθετη υλοποίηση και διαχείριση.
- Απαίτηση για μεγάλες ποσότητες μνήμης για πυκνούς γράφους.

Διάγραμμα Γράφου

Παρακάτω είναι ένα παράδειγμα ενός μη κατευθυνόμενου γράφου:

          Α
         / \
        Β---Γ
        |   |
        Δ---Ε

Εδώ, οι κόμβοι Α, Β, Γ, Δ, Ε είναι συνδεδεμένοι με ακμές.

Σύγκριση Μη Γραμμικών Δομών Δεδομένων

Παρακάτω παρουσιάζεται μια σύγκριση των βασικών μη γραμμικών δομών δεδομένων:

Χαρακτηριστικό	Δέντρα (Trees)	Δυαδικά Δέντρα (Binary Trees)	Γράφοι (Graphs)
Δομή	Ιεραρχική	Ιεραρχική (2 παιδιά ανά κόμβο)	Δίκτυο κόμβων και ακμών
Κόμβοι	Ένας γονέας, πολλά παιδιά	Ένας γονέας, 2 παιδιά	Συνδεδεμένοι με ακμές
Αναζήτηση	O(n)	O(log n) (ισορροπημένο)	O(V + E)
Εισαγωγή	O(1) (στο τέλος)	O(log n) (ισορροπημένο)	O(1) (κόμβος), O(V) (ακμή)
Διαγραφή	O(1) (φύλλο)	O(log n) (ισορροπημένο)	O(V + E)
Χρήσεις	Ιεραρχικά δεδομένα	Γρήγορη αναζήτηση, ταξινόμηση	Δίκτυα, χάρτες, αλγόριθμοι μονοπατιού

Ποια Δομή να Επιλέξω;

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