Scapegoat trees: a comparative performance assessment

Graduate Thesis uoadl:3217992 44605 Read counter

Unit:
Department of Informatics and Telecommunications
Πληροφορική
Deposit date:
2022-05-20
Year:
2022
Author:
ΒΕΝΙΕΡΗΣ ΒΑΣΙΛΕΙΟΣ
Supervisors info:
Χατζηκοκολάκης Κωνσταντίνος, Αναπληρωτής καθηγητής, Τμήμα πλ/κής και τηλ/νιών, ΕΚΠΑ
Original Title:
Scapegoat trees: a comparative performance assessment
Languages:
English
Greek
Translated title:
Scapegoat trees: a comparative performance assessment
Summary:
This Thesis presents and analyzes an alternative tree scheme for the efficient balancing of
binary search trees. Scapegoat trees are loosely balanced and restructure parts of
themselves on certain conditions. The amortized time complexity for each INSERT or
REMOVE operation is Ο(logn), while the worst-case real-time complexity of a FIND one
is Ο(logn). Scapegoat trees, unlike most self-balancing BST implementations, do not
require extra data (e.g. colors, weights, heights) in the tree nodes. Various metrics and
tests are used to compare AVL and scapegoat trees on their functionality. Finally, we
provide data as to the performance of scapegoat trees in potential real-time applications.
Main subject category:
Technology - Computer science
Keywords:
Scapegoat, binary search tree, self-balancing, AVL, amortized time
Index:
Yes
Number of index pages:
4
Contains images:
Yes
Number of references:
5
Number of pages:
32
Scapegoat trees - a comparative performance assessment.pdf (2 MB) Open in new window