Δομή Δεδομένων: Δυαδικά Δέντρα (Binary Trees)

Θεωρία για τα Δυαδικά Δέντρα

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

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

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

Βασικοί Όροι

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

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

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

Εφαρμογές Δυαδικών Δέντρων

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

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

8 3 10 1 6 14 4 7 13

Παραστάσεις ενός δυαδικού δέντρου αναζήτησης (BST) με ρίζα τον κόμβο 8.

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

Παραδείγματα Δυαδικών Δέντρων

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

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

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

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

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

Εδώ, ο κόμβος 8 είναι η ρίζα. Το αριστερό υποδέντρο του 8 περιέχει τιμές μικρότερες από 8, ενώ το δεξιό υποδέντρο περιέχει τιμές μεγαλύτερες από 8.

Παράδειγμα 2: Πλήρες Δυαδικό Δέντρο

Ένα πλήρες δυαδικό δέντρο είναι ένα δέντρο όπου κάθε κόμβος έχει είτε 0 είτε 2 παιδιά: 

          1
         / \
        2   3
       / \
      4   5

Εδώ, όλοι οι κόμβοι έχουν είτε 0 είτε 2 παιδιά.

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

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

          1
         / \
        2   3
       / \ / \
      4  5 6  7

Εδώ, όλα τα επίπεδα του δέντρου είναι πλήρως γεμάτα.

Παράδειγμα 4: Ισορροπημένο Δυαδικό Δέντρο

Ένα ισορροπημένο δυαδικό δέντρο είναι ένα δέντρο όπου το ύψος των αριστερών και δεξιών υποδέντρων κάθε κόμβου διαφέρει το πολύ κατά 1: 

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

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

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

Ένα δυαδικό δέντρο μπορεί να χρησιμοποιηθεί για να αναπαραστήσει μια αριθμητική έκφραση: 

          +
         / \
        *   5
       / \
      3   4

Εδώ, το δέντρο αναπαριστά την έκφραση (3 * 4) + 5.

Quiz

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

Ερώτηση 2: Ποια ιδιότητα ικανοποιεί ένα Δυαδικό Δέντρο Αναζήτησης (BST);

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

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

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

Ερώτηση 6 (Θεωρητική): Ποιο είναι το ύψος ενός δυαδικού δέντρου με ρίζα τον κόμβο Α, που έχει δύο παιδιά Β και Γ, και ο Β έχει δύο παιδιά Δ και Ε;

Ασκήσεις

Άσκηση 1: Να σχεδιάσετε ένα δυαδικό δέντρο αναζήτησης (BST) που να περιέχει τις ακόλουθες τιμές: 10, 5, 15, 3, 7, 12, 18. Στη συνέχεια, να καταγράψετε:
  1. Ποιος είναι ο κόμβος ρίζας;
  2. Ποιο είναι το αριστερό και το δεξιό υποδέντρο του κόμβου 10;
  3. Ποιοι είναι οι κόμβοι φύλλα;
  4. Ποιο είναι το ύψος του δέντρου;
Άσκηση 2: Να σχεδιάσετε ένα πλήρες δυαδικό δέντρο με 7 κόμβους. Στη συνέχεια, να καταγράψετε:
  1. Ποιος είναι ο κόμβος ρίζας;
  2. Ποιοι είναι οι κόμβοι φύλλα;
  3. Ποιοι είναι οι εσωτερικοί κόμβοι;
  4. Ποιο είναι το ύψος του δέντρου;
Άσκηση 3: Να σχεδιάσετε ένα τέλειο δυαδικό δέντρο με 3 επίπεδα. Στη συνέχεια, να καταγράψετε:
  1. Ποιος είναι ο κόμβος ρίζας;
  2. Ποιοι είναι οι κόμβοι φύλλα;
  3. Ποιοι είναι οι εσωτερικοί κόμβοι;
  4. Ποιο είναι το ύψος του δέντρου;

Animation: Δυαδικά Δέντρα

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

8 3 10 1 6 14 4 7 13