Μονάδα:
Τμήμα Πληροφορικής & ΤηλεπικοινωνιώνΠληροφορική
Ημερομηνία κατάθεσης:
2022-05-20
Συγγραφέας:
ΒΕΝΙΕΡΗΣ ΒΑΣΙΛΕΙΟΣ
Στοιχεία επιβλεπόντων καθηγητών:
Χατζηκοκολάκης Κωνσταντίνος, Αναπληρωτής καθηγητής, Τμήμα πλ/κής και τηλ/νιών, ΕΚΠΑ
Πρωτότυπος Τίτλος:
Scapegoat trees: a comparative performance assessment
Γλώσσες εργασίας:
Αγγλικά
Ελληνικά
Μεταφρασμένος τίτλος:
Δέντρα scapegoat: μια συγκριτική αξιολόγηση επιδόσεων
Περίληψη:
Η εργασία αυτή παρουσιάζει και αναλύει μια εναλλακτική μέθοδο για την αποδοτική
εξισορρόπηση δυαδικών δέντρων αναζήτησης. Τα δέντρα scapegoat είναι ελαφρώς
ισορροπημένα και ανακατασκευάζουν μέρη τους υπό ορισμένες συνθήκες. Η amortized
χρονική πολυπλοκότητα για κάθε λειτουργία INSERT ή REMOVE είναι Ο(logn), ενώ η
worst-case πραγματική χρονική πολυπλοκότητα μιας FIND είναι Ο(logn). Τα δέντρα
scapegoat, σε αντίθεση με τις περισσότερες υλοποιήσεις αυτεξισορροπούμενων BST, δεν
απαιτούν επιπλέον δεδομένα (π.χ. χρώματα, βάρη, ύψη) στους κόμβους των δέντρων.
Χρησιμοποιούνται διάφορες μετρικές και δοκιμές για τη σύγκριση των δέντρων AVL και
scapegoat ως προς τη λειτουργικότητά τους. Τέλος, παρέχουμε δεδομένα ως προς την
επίδοση των δέντρων scapegoat σε πιθανές εφαρμογές πραγματικού χρόνου.
Κύρια θεματική κατηγορία:
Τεχνολογία – Πληροφορική
Λέξεις-κλειδιά:
Scapegoat, δυαδικό δέντρο αναζήτησης, αυτεξισορρόπηση, AVL, amortized χρόνος
Αρ. σελίδων ευρετηρίου:
4
Αρ. βιβλιογραφικών αναφορών:
5
