Τι είναι ένα δυαδικό δέντρο;

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

Βασικές ιδιότητες:

• Ρίζα (Root): Ο ανώτατος κόμβος του δέντρου.
• Κόμβος (Node): Το στοιχείο του δέντρου που περιέχει δεδομένα και συνδέσμους στους απογόνους του.
• Παιδί (Child): Κόμβος που βρίσκεται άμεσα κάτω από έναν άλλο κόμβο (γονέα).
• Γονέας (Parent): Κόμβος που έχει έναν ή περισσότερους απογόνους άμεσα κάτω από αυτόν.
• Φύλλο (Leaf): Κόμβος χωρίς απογόνους.
• Κλάδος (Branch): Διαδρομή από τη ρίζα μέχρι το φύλλο.
• Υποδέντρο (Subtree): Δέντρο που αποτελείται από έναν κόμβο και όλους τους απογόνους του.

Διάφορα είδη δυαδικών δέντρων:

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

Χρησιμοποιείται σε διάφορους αλγόριθμους και δομές δεδομένων, όπως δυαδικά δέντρα αναζήτησης, σωρούς, συντακτικά δέντρα.