Unit:
Department of Informatics and TelecommunicationsΠληροφορική
Author:
ΒΕΝΙΕΡΗΣ ΒΑΣΙΛΕΙΟΣ
Supervisors info:
Χατζηκοκολάκης Κωνσταντίνος, Αναπληρωτής καθηγητής, Τμήμα πλ/κής και τηλ/νιών, ΕΚΠΑ
Original Title:
Scapegoat trees: a comparative performance assessment
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
