Υλοποίηση και οπτικοποίηση δένδρων αναζήτησης και δένδρων τουρνουά

Abstract

Στην μελέτη αυτή, γίνεται αναφορά σε δένδρα των αλγορίθμων δομών δεδομένων. Τα είδη των δένδρων που περιγράφονται είναι τα δυαδικά δένδρα, τα δένδρα τουρνουά και τέλος τα δυαδικά δένδρα αναζήτησης. Η παρουσίαση της απαραίτητης θεωρίας των λειτουργιών και των ιδιοτήτων κάθε δένδρου είναι ουσιώδης για την κατανόηση τους. Για την αναλυτική περιγραφή των δένδρων γίνεται αναφορά και στις ουρές προτεραιότητας και περιγράφονται τα αριστερίστικα δένδρα με απόλυτη σαφήνεια. Είναι απαραίτητη η αναφορά των αριστερίστικων δένδρων για την πλήρη κατανόηση των δένδρων τουρνουά και των δυαδικών δένδρων αναζήτησης. Παρουσιάζονται, επίσης, τρεις περιπτώσεις ισορροπημένων δυαδικών δένδρων αναζήτησης, τα AVL δένδρα, τα Κόκκινα-Μαύρα δένδρα και τα Β-δένδρα. Ακόμη, γίνεται υλοποίηση και οπτικοποίηση των αλγορίθμων με σκοπό την εμβάθυνση σε εφαρμογές με χρήση δένδρων όπως είναι το πρόβλημα της συσκευασίας κιβωτίων και το πρόβλημα της κατανομής διασταυρώσεων. Οι εφαρμογές περιγράφονται τόσο σε θεωρητικό επίπεδο όσο και σε προγραμματιστικό επίπεδο. Η εφαρμογή του προβλήματος της συσκευασίας κιβωτίων υλοποιείται με δύο τρόπους, με την χρήση των δένδρων τουρνουά (Πρώτη Εφαρμογή) και με την χρήση των δένδρων αναζήτησης AVL (Καλύτερη Εφαρμογή). Η εφαρμογή της κατανομής διασταυρώσεων υλοποιείται με την χρήση των δένδρων αναζήτησης και γραμμικής λίστας. Τέλος, η μελέτη αυτή αποσκοπεί αποκλειστικά στην κατανόηση των δένδρων και των αλγορίθμων τους, όπως και στην παρουσίαση εφαρμογών αλλά δεν επικεντρώνεται στην δημιουργία βέλτιστου προγράμματος.