Magister Curationis / Binary search trees (BSTs) are important data structures which are widely used in various guises. Splay trees are a specific kind of binary search tree, one without explicit balancing. Skip lists use more space than BSTs and are related to them in terms of much of their run-time behavior. Even though binary search trees have been used for about half a century, there are still many open questions regarding their run-time performance and algorith mic complexity. In many instances, their worst-case, average-case, and best-case behaviors are unknown and need further research. Our analysis provides a basis for selecting more suitable data structures and algorithms for specific processes and applications. We contrast the empirical behavior of splay trees and skip lists with their theoretical behavior. In particular we explore when splay trees outperform skip lists and vice versa. The performance of a splay tree depends on the history of accesses to its el ements. On the other hand, the performance of a skip list depends on an indepen dent randomization of the height of links that lead to specific elements. Therefore, probabilistic methods are used to analyze the operation of splay trees and skip lists. Our main results are that splay trees are faster for sorted insertion, where AVL trees are faster for random insertion. For searching, skip lists are faster than single class top-down splay trees, but two-class and multi-class top-down splay trees can behave better than skip lists.

<p>Our main results are that splay trees are faster for sorted insertion, where AVL trees are faster for random insertion. For searching, skip lists are faster than single class top-down splay trees, but two-class and multi-class top-down splay trees can behave better than skip lists.</p>

Θέμα της παρούσης διπλωματικής εργασίας αποτελεί η μελέτη, ανάπτυξη και πειραματική επιβεβαίωση αλγοριθμικών τεχνικών για την σχεδίαση αυτοοργανώμενων δομών δεδομένων (self-organizing data structures) και η ανάπτυξη τυχαιοποιημένων εκδόσεών τους. Μια αυτοοργανώμενη δομή δεδομένων διαθέτει κάποιον αλγόριθμο για να αναδιοργανώνει τους δείκτες και τα δεδομένα κατάστασης μετά από κάθε πρόσβαση ή πράξη . Ο αλγόριθμος αυτοοργάνωσης είναι σχεδιασμένος ώστε αντιδρώντας σε αρχικά άγνωστες ιδιότητες της ακολουθίας αιτήσεων (request sequence), να οδηγεί τη δομή δεδομένων σε κατάσταση πλεονεκτική για τις ιδιότητες της ακολουθίας με αποτέλεσμα τη μείωση του χρόνου που χρειάζεται στο μέλλον ανά πράξη. Ο πρώτος αλλά και ο μόνος μέχρι σήμερα πιθανός υποψήφιος αλγόριθμος αναζήτησης σε δένδρο που μπορεί να είναι Ο(1)-ανταγωνιστικός είναι το splay δένδρο (splay tree) που παρουσιάστηκε από τους Sleator και Tarjan [1]. Στην εργασία των Sleator και Tarjan παρουσιάζονται κάποιες εικασίες, οι οποίες δεν έχουν αποδειχθεί. Σημαντικότερη είναι η εικασία δυναμικής βελτιστότητας (dynamic optimality conjecture) σύμφωνα με την οποία το splay δένδρο είναι Ο(1)-ανταγωνιστικό. Η εικασία δυναμικής δακτυλοδότησης (dynamic finger conjecture) και η εικασία διαπέρασης (traversal conjecture) είναι αληθείς, αν είναι αληθής η εικασία δυναμικής βελτιστότητας. Ο Cole [3], [4] προσπάθησε να αποδείξει την ορθότητα της εικασίας δυναμικής δακτυλοδότησης σε μια από τις σημαντικότερες εργασίες για τα splay δένδρα. O J. Iacono [2] ανέπτυξε εναλλακτικές δομές δεδομένων που έχουν χρόνο χειρότερης περίπτωσης ανά πράξη (και όχι επιμερισμένο κόστος) της τάξης του Ο(logn), σε αντιδιαστολή με τον Ο(n) χρόνο χειρότερης περίπτωσης των splay trees. Σε αντιπαράθεση με τη δομή του Iacono, οι Mihai Badoiu και Erik D. Demaine παρουσίασαν μια δυναμική δομή αναζήτησης[7], η οποία επιτυγχάνει την ενοποιημένη ιδιότητα και που είναι απλούστερη από τη δομή του Iacono. Μεταξύ όλων των δυναμικών δομών αναζήτησης με βάση τις συγκρίσεις , η συγκεκριμένη δομή έχει τον καλύτερο χρόνο εκτέλεσης. Εκτός της παραπάνω δομής, ο Demaine ανέπτυξε ένα Ο(loglogn) ανταγωνιστικό online δυαδικό δέντρο αναζήτησης[5] , βελτιώνοντας το μέχρι πρότινος βέλτιστο ανταγωνιστικό ποσοστό της τάξης Ο(logn). Αυτή είναι η πρώτη μεγάλη βελτίωση της εικασίας δυναμικής βελτιστότητας (dynamic optimality conjecture) των Sleator και Tarjan , σύμφωνα με την οποία υπάρχουν Ο(1) ανταγωνιστικά δυαδικά δέντρα αναζήτησης. Σε σχέση με τη δυναμική βελτιστότητα των Splay trees, σημαντική συνεισφορά αποτελεί και η εργασία του George F. Georgakopoulos[6]. Ο George F. Georgakopoulos παρουσιάζει μια επέκταση της splay τεχνικής , την οποία ονομάζει chain-splay(αλυσιδωτό splay) . Τα chain-splay δέντρα εφαρμόζουν splay στο στοιχείο που προσπελαύνουμε προς τη ρίζα όπως ακριβώς γίνεται και στα κλασικά splay trees, αλλά εκτελούν και μερικές τοπικές splay πράξεις τακτοποίησης κάτω από το στοιχείο που προσπελάσαμε. Αποδεικνύεται πως η τεχνική chain–splay είναι Ο(loglogn) ανταγωνιστική σε σχέση με οποιοδήποτε offline αλγόριθμο αναζήτησης. Tέλος, ο George F. Georgakopoulos [9] έδωσε ένα νέο λήμμα επαναζύγισης για τα splay δέντρα και με βάση αυτό το λήμμα, αποδεικνύει πως τα splay δέντρα είναι ανταγωνιστικά προς κάθε κλάση δυναμικών ισοζυγισμένων δέντρων. Οι παραπάνω δομές θα μελετηθούν τόσο σε θεωρητικό όσο και σε πειραματικό επίπεδο με σκοπό την εξαγωγή χρήσιμων συμπερασμάτων σε σχέση με την αποδοτικότητά τους αλλά και με σκοπό την καταγραφή των ακόμη ανοικτών προβλημάτων και των προοπτικών επίλυσης τους. Επιπλέον, θα παρουσιαστούν τυχαιοποιημένες εκδόσεις των δομών των Demaine και Georgakopoulos. Οι δομές αυτές θα υλοποιηθούν και η απόδοσή τους θα τεκμηριωθεί τόσο πειραματικά όσο και θεωρητικά. Σημαντικής σημασίας είναι η σύγκρισή τους με τις αρχικές δομές, ώστε να εξαχθούν συμπεράσματα σχετικά με την συμβολή της τυχαιοποίησης στη βελτίωση της απόδοσης των δομών. / -

<p>Our main results are that splay trees are faster for sorted insertion, where AVL trees are faster for random insertion. For searching, skip lists are faster than single class top-down splay trees, but two-class and multi-class top-down splay trees can behave better than skip lists.</p>

Magister Scientiae - MSc / Our main results are that splay trees are faster for sorted insertion, where AVL trees are faster for random insertion. For searching, skip lists are faster than single class top-down splay trees, but two-class and multi-class top-down splay trees can behave better than skip lists. / South Africa

In this thesis we compared some variants of binary search trees that approach dynamic optimality: Tango trees, Multisplay trees, and Splay trees. We empirically tested the behavior of these three types of trees, as well as Red-Black trees. We measured the amount of visited nodes per operation and running time on real hardware. We proved that Tango trees and Multisplay trees are in most cases less efficient than Splay trees and Red-Black trees. Cache-related effects played a surprisingly large part in the behavior of Red-Black tree and Splay tree. 1