Στην Επιστήμη Υπολογιστών, δέντρα ονομάζονται οι δομές δεδομένων που είναι παρόμοιες με τα δέντρα της θεωρίας γράφων, με τη διαφορά ότι τα δέντρα στην επιστήμη των υπολογιστών έχουν κατευθυνόμενες ακμές.
Ορισμοί
Ένα δέντρο είναι ένας μη κατευθυνόμενος απλός γράφος G που ικανοποιεί οποιαδήποτε από τις παρακάτω ισοδύναμες συνθήκες:
Ο G είναι συνεκτικός και δεν έχει κύκλους.
Ο G δεν έχει κύκλους, αλλά ένας απλός κύκλος μπορεί να σχηματιστεί αν προστεθεί μία οποιαδήποτε ακμή στον G.
Ο G είναι συνεκτικός, αλλά παύει να είναι αν αφαιρεθεί έστω και μία ακμή του.
Δύο οποιεσδήποτε κορυφές του G μπορούν να συνδεθούν μέσω ενός μοναδικού απλού μονοπατιού.
Ένα δέντρο με 6 κορυφές και 5 πλευρές
Δάσος είναι ένας μη κατευθυνόμενος γράφος, του οποίου όλες οι συνεκτικές συνιστώσες είναι δέντρα. Με άλλα λόγια, το δάσος αποτελείται από την ένωση ενός αριθμού ξένων μεταξύ τους δέντρων. Ένα πολυδέντρο ή ένα προσανατολισμένο δέντρο είναι ένας κατευθυνόμενος γράφος με το πολύ ένα μη-κατευθυνόμενο μονοπάτι μεταξύ δύο οποιωνδήποτε κορυφών. Δηλαδή ένα προσανατολισμένο δέντρο είναι ένας άκυκλος κατευθυνόμενος γράφος. Ένα κατευθυνόμενο δέντρο προκύπτει όταν από ένα κατευθυνόμενο γράφο αφαιρέσουμε τις κατευθύνεσεις των ακμών του.
Ένα δυαδικό δέντρο σχεδιασμένο έτσι, ώστε οι κορυφές που βρίσκονται στο ίδιο επίπεδο να βρίσκονται στην ίδια οριζόντια ευθεία. Η ρίζα βρίσκεται στο ανώτερο επίπεδο.
Ένα δέντρο ονομάζεται ριζωμένο εάν μία κορυφή έχει οριστεί ως ρίζα. Τότε λέμε ότι οι ακμές έχουν προσανατολισμό προς ή από τη ρίζα. Σε ένα ριζωμένο δέντρο, ο πατέρας μιας κορυφής είναι η αμέσως προηγούμενη κορυφή της διαδρομής από τη ρίζα σ' αυτήν. Κάθε κορυφή εκτός από τη ρίζα έχει ένα μοναδικό γονιό. Το παιδί μιας κορυφής είναι μια κορυφή της οποίας αυτή είναι πατέρας. Μία κορυφή χωρίς παιδιά λέγεται φύλλο. Μία τερματική κορυφή ενός δέντρου είναι μία κορυφή βαθμού 1. Σε ένα ριζωμένο δέντρο, όλα τα φύλλα είναι τερματικές κορυφές.
Οι κόμβοι ενός δέντρου μπορούν να χωριστούν σε επίπεδα, με την έννοια ότι κόμβοι που απέχουν το ίδιο από τη ρίζα βρίσκονται στο ίδιο επίπεδο. Πιο αυστηρά, όλοι οι κόμβοι των οποίων τα μονοπάτια από τη ρίζα προς αυτά έχουν το ίδιο μήκος, ανήκουν στο ίδιο επίπεδο.
Κέντρο ενός δέντρου είναι η κορυφή εκείνη για την οποία ελαχιστοποιούνται οι αποστάσεις των υπόλοιπων κορυφών από αυτήν. Ακτίνα ενός δέντρου είναι η μέγιστη απόσταση του κέντρου από οποιαδήποτε άλλη κορυφή. Διάμετρος ενός δέντρου είναι η μέγιστη μεταξύ των αποστάσεων δύο οποιονδήποτε κορυφών του δέντρου.
Ιδιότητες
Τα δέντρα είναι εξορισμού γράφοι συνεκτικοί και δεν περιέχουν κύκλους. Συνέπεια των ιδιοτήτων αυτών είναι ότι αν ένα δέντρο έχει n κορυφές, τότε έχει n-1 ακμές. Επιπλέον, κάθε δέντρο έχει τουλάχιστον έναν κόμβο βαθμού 1. Βαθμός ενός κόμβου είναι το πλήθος των προσκείμενων σ' αυτόν ακμών.
Ένα δέντρο είναι διμερές γράφημα, δηλαδή οι κορυφές του μπορούν να χωριστούν σε δύο ξένα σύνολα τέτοια, ώστε οι ακμές του γραφήματος να συνδέουν μόνο κορυφές από το ένα σύνολο στο άλλο. Το ένα σύνολο αποτελείται από τους κόμβους που ανήκουν σε άρτιο επίπεδο, ενώ το άλλο σύνολο από τους κόμβους που ανήκουν σε περιττό επίπεδο. Άμεσο επακόλουθο είναι ότι ένα δέντρο είναι 2-χρωματίσιμο. Δηλαδή, οι κόμβοι του μπορούν να χρωματιστούν με τρόπο τέτοιο, ώστε κάθε δύο γειτονικοί κόμβοι να έχουν διαφορετικό χρώμα. Αυτό γίνεται χρωματίζοντας τους κόμβους των άρτιων επιπέδων με ένα χρώμα και τους υπόλοιπους με το άλλο χρώμα.
Κάθε γράφος έχει ένα γεννητικό δέντρο, δηλαδή ένα δέντρο με κορυφές εκείνες του γραφήματος και ακμές υποσύνολο των ακμών του γράφου. Στα σταθμισμένα γραφήματα, ένα συναφές πρόβλημα είναι αυτό της εύρεσης του ελάχιστου γεννητικού δέντρου.
Σημαντικά είδη δέντρων
Αξίζει αναφορά σε συγκεκριμένα είδη δέντρων, καθώς εμφανίζονται συχνά σε εφαρμογές.
Δυαδικό δέντρο. Είναι δέντρα των οποίων κάθε κορυφή έχει το πολύ δύο παιδιά. Εμφανίζονται σε αλγόριθμους αναζήτησης, όπως η δυαδική αναζήτηση.
Β-Δεντρο. Πρόκειται για δομή δεδομένων που αποτελεί γενίκευση των δυαδικών δέντρων αναζήτησης. Κάθε κορυφή ενός Β-Δέντρου μπορεί να έχει πλήθος παιδιών ορισμένο σε ένα προκαθορισμένο εύρος. Αυτού του είδους τα δέντρα χρησιμοποιούνται στη κατασκευή ευρετηρίων για βάσεις δεδομένων.
Γράφημα-αστέρι (star graph). Είναι γραφήματα των οποίων ένας κόμβος είναι γειτονικός προς όλους τους υπόλοιπους και δεν υπάρχουν άλλες γειτνιάσεις. Αυτά τα γραφήματα χρησιμοποιούνται στη μοντελοποίηση δικτύων υπολογιστών με τοπολογία αστέρα.
Γραμμικό γράφημα (path graph). Είναι γραφήματα των οποίων οι κόμβοι συνδέονται με ακμές σειριακά. Τα γραφήματα αυτά αποτελούν μονοπάτια.
Διάτρεξη δέντρων
Προδιάταξη: A-B-D-F-C-G-E. Μεταδιάταξη: D-F-B-G-E-C-A. Κατά επίπεδο: A-B-C-E-D-F-G
Τα δέντρα δεν είναι γραμμικές δομές και για τον λόγο αυτό δεν υπάρχει από τη φύση τους κάποιος γραμμικός τρόπος διαπέρασης των κόμβων τους ή γραμμικής τους διάταξης. Η ύπαρξη πολλαπλών δυνατοτήτων για τη διάταξη ενός κόμβου ως προς τους απογόνους του δημιουργεί διάφορα είδη διελεύσεων/διατάξεων. Ωστόσο τρεις διαφορετικοί τρόποι διαπέρασης των κόμβων ενός δέντρου είναι οι σημαντικότεροι.
Προδιάταξη
Κατά την προδιάταξη (preorder), οι κόμβοι ενός δέντρου διατρέχονται με προτεραιότητα στον πατέρα έναντι του παιδιού. Ο κόμβος εκκίνησης είναι η ρίζα, ως πρόγονος όλων των κόμβων. Η προδιάταξη ενός δέντρου συντακτικής ανάλυσης αντιστοιχεί σε προθεματικές συντάξεις, όπως η Πολωνική γραφή του προτασιακού λογισμού. Επίσης, η προδιάταξη είναι μια πιθανή σειρά διαπέρασης των κόμβων ενός δέντρου με τον αλγόριθμο της αναζήτησης κατά βάθος.
Μεταδιάταξη
Κατά τη μεταδιάταξη (postorder), οι κόμβοι ενός δέντρου διατρέχονται με προτεραιότητα στο παιδί έναντι του πατέρα. Δηλαδή, πριν τη διέλευση από έναν κόμβο, έχουμε διέλθει πρώτα από όλα τα παιδιά του.
Διάταξη κατά επίπεδο
Στην περίπτωση αυτή, η διαπέραση γίνεται ξεκινώντας από το μικρότερο επίπεδο, δηλαδή τη ρίζα. Πρώτα διαπερνώνται όλοι οι κόμβοι ενός επιπέδου και η διαπέραση προχωρά στους κόμβους του επόμενου επιπέδου. Μια αναζήτηση κατά πλάτος διατάσσει τους κόμβους στη σειρά αυτή.
Αναφορές
Diestel, Reinhard (2005), Graph Theory (3rd έκδοση), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4.
Flajolet, Philippe; Sedgewick, Robert (2009), Analytic Combinatorics, Cambridge University Press, ISBN 9780521898065
Donald E. Knuth. The Art of Computer Programming Volume 1: Fundamental Algorithms. Addison-Wesley Professional; 3rd edition (November 14, 1997).
Παναγιώτης Δ. Μποζάνης, Δομές Δεδομένων, Εκδ. Τζιόλα.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
