Μελέτη των αλγορίθμων ταξινόμησης Binary Search - Tree, Quad-Tree και R-Tree και εφαρμογή των Binary Search-Tree και Quad-Tree σε σχεσιακές βάσεις δεδομένων

Abstract

Η μελέτη των δομών δεδομένων και των αλγορίθμων είναι καθοριστικής σημασίας για την επιστήμη και τη τεχνολογία των υπολογιστών. Οι αλγόριθμοι Binary Search – Tree, Quad – Tree και R – Tree αποτελούν τρεις από τους καλύτερους αλγόριθμους ταξινόμησης με βάση την δενδρική δομή δεδομένων. Το Binary Search – Tree για δεδομένα μίας διάστασης, το Quad – Tree δύο διαστάσεων ενώ το R – Tree για δεδομένα δύο ή περισσότερων διαστάσεων. Οι αλγόριθμοι που αναφέραμε εφαρμόζονται συχνά σε γεωγραφικά συστήματα πληροφορίας (GIS), εφαρμογές σχεδίασης τύπου CAD, εφαρμογές εικόνας και ήχου (multimedia), την ρομποτική και αλλού για την ταχύτερη ταξινόμηση των δεδομένων και την βελτιστοποίηση της αναζήτησης. Σκοπός της πτυχιακής εργασίας είναι καταρχήν η κατασκευή μιας βάσης δεδομένων στον SQL Server και η επικοινωνία της βάσης αυτής με το MatLab και τον C++ Builder. Επιπλέον, η κατασκευή μίας εφαρμογής σε προγραμματιστικό περιβάλλον (C++), η οποία θα παράγει – εισάγει δεδομένα στη βάση δεδομένων και θα τα ταξινομεί χρησιμοποιώντας τις μεθόδους Binary Search – Tree και Quad - Tree. Η εφαρμογή θα αντλεί τα δεδομένα από τη βάση δεδομένων και θα κατασκευάζει δένδρα ταξινόμησης βασισμένα στις σχετικές θέσεις των σημειακών δεδομένων, εφαρμόζοντας σε αυτά διάφορες τεχνικές αναζήτησης.

The research of data structures and algorithms is significant for the science and the technology of computers. The algorithms Binary Search –Tree, Quad –Tree and R –Tree represent three of the best algorithms for classification with tree data structures. The Binary Search –Tree for one dimension data, the Quad –Tree for two dimensions data and the R –Tree for multiple dimensions data. The algorithms often used in geographic information systems (GIS), design applications like CAD, multimedia applications, robotics and elsewhere for the quickest classification of data and the optimisation of search. The thesis aims to create a database in SQL Server and to establish a connection with Matlab and C++ Builder, also the design and programming of an application using the C++ language. The application has to generate and classify the data in order to create an index. The application will use the data of the database and create Binary Search – Tree and Quad - Tree data structures and apply in them various search techniques.