Carleton University - School of Computer Science Honours Project
Summer 2021
Analysis of Probability Distributions on Access Balancing Weighted Treaps
Patrick Shipton
SCS Honours Project Image
ABSTRACT
In this report, we experimentally examine weighted and unweighted treaps. We explore a modification of weighted treaps that rebalance based on node accesses. Their performance is experimentally tested under different access distributions. Additionally, we compare the performance found experimentally to known bounds and expectations of unweighted treaps performance.