MORRIS COUNTERS AND RANDOMIZED BINARY SEARCH TREES

MPhil Thesis Defence


Title: "MORRIS COUNTERS AND RANDOMIZED BINARY SEARCH TREES"

By

Mr. Siu Chung CHAN


Abstract

Randomized binary search trees are an efficient dynamic data structure for 
storing items when the access sequence is not known a priori. We propose a 
space-efficient variation of randomized binary search trees that is 
approximately optimal in random key ordering, using Morris' counters. The 
space required on average is Θ(log log m) for an access sequence of 
length m, compared to Θ(log m) for Seidel and Aragon's treaps. In 
the case that a probability distribution of the keys is given but the 
ordering of the keys is random, we prove that our algorithm has an 
expected access runtime within a constant factor of the optimal one. The 
proof is based on a novel Markov chain decomposition technique and a 
coupling argument. Moreover, our numerical experiments demonstrate that 
our approach is empirically superior to the original treap for certain 
access patterns.


Date:  			Monday, 31 October 2022

Time:			10:00am - 12:00noon

Venue:			Room 5501
 			lifts 25/26

Committee Members:	Prof. Mordecai Golin (Supervisor)
 			Prof. Siu-Wing Cheng (Chairperson)
 			Dr. Amir Goharshady


**** ALL are Welcome ****