Δομή Δεδομένων: Δέντρα (Trees)

Θεωρία για τα Δέντρα

Τα δέντρα (trees) είναι μια μη γραμμική δομή δεδομένων που οργανώνει τα δεδομένα σε ιεραρχική μορφή. Αποτελούνται από κόμβους που συνδέονται μεταξύ τους με ακμές.

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

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

Βασικοί Όροι

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

Εφαρμογές Δέντρων

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

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

Α Β Γ Δ Ε Ζ

Παραστάσεις ενός δέντρου με ρίζα τον κόμβο Α. Οι κόμβοι Β και Γ είναι παιδιά του Α, ενώ οι Δ, Ε, Ζ είναι παιδιά των Β και Γ αντίστοιχα.

Θεωρητικά Παραδείγματα Δέντρων

Παραδείγματα Δέντρων

Παρακάτω παρουσιάζονται θεωρητικά παραδείγματα δέντρων και πώς μπορούν να χρησιμοποιηθούν για την αναπαράσταση διάφορων δομών.

Παράδειγμα 1: Οργανώγραμμα Εταιρείας

Ένα δέντρο μπορεί να χρησιμοποιηθεί για να αναπαραστήσει το οργανώγραμμα μιας εταιρείας: 

        Διευθύνων Σύμβουλος (Α)
               /          \
         Διευθυντής Πωλήσεων (Β)  Διευθυντής Παραγωγής (Γ)
         /       \                     /       \
  Υπεύθυνος Πωλήσεων (Δ)  Υπεύθυνος Marketing (Ε)  Υπεύθυνος Παραγωγής (Ζ)  Υπεύθυνος Ποιοτικού Ελέγχου (Η)

Εδώ, ο Διευθύνων Σύμβουλος είναι η ρίζα του δέντρου, και κάθε διευθυντής και υπεύθυνος είναι κόμβοι του δέντρου.

Παράδειγμα 2: Σύστημα Αρχείων

Ένα δέντρο μπορεί να αναπαραστήσει την ιεραρχία ενός συστήματος αρχείων: 

        C:\
        │
        ├── Documents
        │   ├── Work
        │   │   ├── Project1.docx
        │   │   └── Project2.docx
        │   └── Personal
        │       ├── Notes.txt
        │       └── Photos
        │
        └── Programs
            ├── App1.exe
            └── App2.exe

Εδώ, ο φάκελος C:\ είναι η ρίζα, και κάθε υποφάκελος ή αρχείο είναι κόμβος του δέντρου.

Παράδειγμα 3: Γενεαλογικό Δέντρο

Ένα δέντρο μπορεί να αναπαραστήσει ένα γενεαλογικό δέντρο: 

        Παππούς (Α)
           /    \
     Πατέρας (Β)   Θείος (Γ)
     /    \
  Εγώ (Δ)  Αδερφή (Ε)

Εδώ, ο Παππούς είναι η ρίζα, και κάθε απόγονος είναι κόμβος του δέντρου.

Παράδειγμα 4: Δυαδικό Δέντρο Αναζήτησης

Ένα δυαδικό δέντρο αναζήτησης (BST) οργανώνει τις τιμές έτσι ώστε για κάθε κόμβο:

  • Όλες οι τιμές στο αριστερό υποδέντρο είναι μικρότερες από την τιμή του κόμβου.
  • Όλες οι τιμές στο δεξιό υποδέντρο είναι μεγαλύτερες από την τιμή του κόμβου.

          8
         / \
        3   10
       / \   \
      1   6   14
         / \  /
        4   7 13

Παράδειγμα 5: Δέντρο Απόφασης

Ένα δέντρο απόφασης μπορεί να χρησιμοποιηθεί για να λάβει αποφάσεις βάσει συνθηκών: 

        Θα πάω εκδρομή;
               /          \
     Καλός καιρός;         Κακός καιρός;
     /       \
  Ναι      Όχι
  /        \
Πάω       Δεν πάω

Quiz

Ερώτηση 1: Ποιος είναι ο κόμβος που δεν έχει γονέα σε ένα δέντρο;

Ερώτηση 2: Ποιος είναι ο ορισμός του βάθους ενός κόμβου σε ένα δέντρο;

Ερώτηση 3: Ποιος από τους παρακάτω όρους περιγράφει έναν κόμβο που δεν έχει παιδιά;

Ερώτηση 4 (Θεωρητική): Ποια είναι η διαφορά μεταξύ ενός δέντρου και ενός γράφου;

Ερώτηση 5 (Θεωρητική): Ποιος από τους παρακάτω τύπους διασχίσεων δέντρου επισκέπτεται πρώτα τον κόμβο και μετά τα υποδέντρα;

Ερώτηση 6 (Θεωρητική): Ποιος είναι ο μέγιστος αριθμός παιδιών που μπορεί να έχει ένας κόμβος σε ένα δυαδικό δέντρο;

Ασκήσεις

Άσκηση 1: Να σχεδιάσετε ένα δέντρο που να αναπαριστά την ακόλουθη ιεραρχία:
  1. Ο κόμβος Α είναι η ρίζα.
  2. Ο κόμβος Α έχει δύο παιδιά: Β και Γ.
  3. Ο κόμβος Β έχει δύο παιδιά: Δ και Ε.
  4. Ο κόμβος Γ έχει ένα παιδί: Ζ.
Στη συνέχεια, να καταγράψετε:
  1. Ποιος είναι ο κόμβος ρίζας;
  2. Ποιοι είναι οι κόμβοι φύλλα;
  3. Ποιοι είναι οι εσωτερικοί κόμβοι;
  4. Ποιο είναι το βάθος του κόμβου Ζ;
Άσκηση 2: Να σχεδιάσετε ένα δυαδικό δέντρο αναζήτησης (BST) που να περιέχει τις ακόλουθες τιμές: 8, 3, 10, 1, 6, 14, 4, 7, 13. Στη συνέχεια, να καταγράψετε:
  1. Ποιος είναι ο κόμβος ρίζας;
  2. Ποιο είναι το αριστερό και το δεξιό υποδέντρο του κόμβου 8;
  3. Ποιοι είναι οι κόμβοι φύλλα;
  4. Ποιο είναι το ύψος του δέντρου;
Άσκηση 3: Να σχεδιάσετε ένα δέντρο που να αναπαριστά το ακόλουθο οργανώγραμμα:
  1. Ο Διευθύνων Σύμβουλος (Α) είναι η ρίζα.
  2. Ο Διευθύνων Σύμβουλος έχει δύο υποδιευθυντές: Διευθυντής Πωλήσεων (Β) και Διευθυντής Παραγωγής (Γ).
  3. Ο Διευθυντής Πωλήσεων έχει δύο υπαλλήλους: Υπεύθυνος Πωλήσεων (Δ) και Υπεύθυνος Marketing (Ε).
  4. Ο Διευθυντής Παραγωγής έχει δύο υπαλλήλους: Υπεύθυνος Παραγωγής (Ζ) και Υπεύθυνος Ποιοτικού Ελέγχου (Η).
Στη συνέχεια, να καταγράψετε:
  1. Ποιος είναι ο κόμβος ρίζας;
  2. Ποιοι είναι οι κόμβοι φύλλα;
  3. Ποιο είναι το βάθος του κόμβου Υπεύθυνος Ποιοτικού Ελέγχου (Η);
  4. Ποιοι είναι οι αδερφοί κόμβοι;

Animation: Δέντρα

Παρακολουθήστε πώς λειτουργούν οι βασικές έννοιες ενός δέντρου με οπτικοποίηση.

Α Β Γ Δ Ε Ζ Η