Complete Binary Tree vs Full Binary Tree
Δυαδικό δέντρο είναι ένα δέντρο όπου κάθε κόμβος έχει ένα ή δύο παιδιά. Σε ένα δυαδικό δέντρο, ένας κόμβος δεν μπορεί να έχει περισσότερα από δύο παιδιά. Σε ένα δυαδικό δέντρο, τα παιδιά ονομάζονται «αριστερά» και «δεξιά» παιδιά. Οι θυγατρικοί κόμβοι περιέχουν μια αναφορά στον γονέα τους. Ένα πλήρες δυαδικό δέντρο είναι ένα δυαδικό δέντρο στο οποίο κάθε επίπεδο του δυαδικού δέντρου είναι πλήρως γεμάτο εκτός από το τελευταίο επίπεδο. Στο μη γεμισμένο επίπεδο, οι κόμβοι συνδέονται ξεκινώντας από την πιο αριστερή θέση. Ένα πλήρες δυαδικό δέντρο είναι ένα δέντρο στο οποίο κάθε κόμβος στο δέντρο έχει δύο παιδιά εκτός από τα φύλλα του δέντρου.
Τι είναι το Full Binary Tree;
Το πλήρες δυαδικό δέντρο είναι ένα δυαδικό δέντρο στο οποίο κάθε κόμβος στο δέντρο έχει ακριβώς μηδέν ή δύο παιδιά. Με άλλα λόγια, κάθε κόμβος στο δέντρο εκτός από τα φύλλα έχει ακριβώς δύο παιδιά. Το σχήμα 1 παρακάτω απεικονίζει ένα πλήρες δυαδικό δέντρο. Σε ένα πλήρες δυαδικό δέντρο, ο αριθμός των κόμβων (n), ο αριθμός των κόμβων (l) και ο αριθμός των εσωτερικών κόμβων (i) σχετίζονται με έναν ειδικό τρόπο, ώστε αν γνωρίζετε κάποιον από αυτούς, μπορείτε να προσδιορίσετε τους άλλους δύο τιμές ως εξής:
1. Εάν ένα πλήρες δυαδικό δέντρο έχει i εσωτερικούς κόμβους:
– Αριθμός φύλλων l=i+1
– Συνολικός αριθμός κόμβων n=2i+1
2. Εάν ένα πλήρες δυαδικό δέντρο έχει n κόμβους:
– Αριθμός εσωτερικών κόμβων i=(n-1)/2
– Αριθμός φύλλων l=(n+1)/2
3. Εάν ένα πλήρες δυαδικό δέντρο έχει l φύλλα:
– Συνολικός αριθμός κόμβων n=2l-1
– Αριθμός εσωτερικών κόμβων i=l-1
Τι είναι το πλήρες δυαδικό δέντρο;
Όπως φαίνεται στο σχήμα 2, ένα πλήρες δυαδικό δέντρο είναι ένα δυαδικό δέντρο στο οποίο κάθε επίπεδο του δέντρου είναι πλήρως γεμάτο εκτός από το τελευταίο επίπεδο. Επίσης, στο τελευταίο επίπεδο, οι κόμβοι θα πρέπει να συνδέονται ξεκινώντας από την πιο αριστερή θέση. Ένα πλήρες δυαδικό δέντρο ύψους h ικανοποιεί τις ακόλουθες προϋποθέσεις:
– Από τον ριζικό κόμβο, το επίπεδο πάνω από το τελευταίο επίπεδο αντιπροσωπεύει ένα πλήρες δυαδικό δέντρο ύψους h-1
– Ένας ή περισσότεροι κόμβοι στο τελευταίο επίπεδο μπορεί να έχουν 0 ή 1 παιδιά
– Εάν οι a, b είναι δύο κόμβοι στο επίπεδο πάνω από το τελευταίο επίπεδο, τότε ο a έχει περισσότερα παιδιά από το b εάν και μόνο εάν ο a βρίσκεται αριστερά του b
Ποια είναι η διαφορά μεταξύ Complete Binary Tree και Full Binary Tree;
Τα πλήρη δυαδικά δέντρα και τα πλήρη δυαδικά δέντρα έχουν σαφή διαφορά. Ενώ ένα πλήρες δυαδικό δέντρο είναι ένα δυαδικό δέντρο στο οποίο κάθε κόμβος έχει μηδέν ή δύο παιδιά, ένα πλήρες δυαδικό δέντρο είναι ένα δυαδικό δέντρο στο οποίο κάθε επίπεδο του δυαδικού δέντρου είναι πλήρως γεμάτο εκτός από το τελευταίο επίπεδο. Ορισμένες ειδικές δομές δεδομένων όπως οι σωροί πρέπει να είναι πλήρη δυαδικά δέντρα ενώ δεν χρειάζεται να είναι πλήρη δυαδικά δέντρα. Σε ένα πλήρες δυαδικό δέντρο, αν γνωρίζετε τον αριθμό των συνολικών κόμβων ή τον αριθμό των λαβών ή τον αριθμό των εσωτερικών κόμβων, μπορείτε να βρείτε τους άλλους δύο πολύ εύκολα. Αλλά ένα πλήρες δυαδικό δέντρο δεν έχει ειδική ιδιότητα που να σχετίζεται με αυτές τις τρεις ιδιότητες.
