[talks] Siyu Yang will present her Pre-FPO on March 3, 2015 at 3pm in Room 401.

[Nicki Gotsis]

Siyu Yang will present her Pre-FPO on March 3, 2015 at 3pm in Room 401.

His committee members are Professor Robert Tarjan (advisor), Prof Robert Sedgewick (reader), Dr. David Lee (non-Princeton reader), Prof Andrea LaPaugh (non-reader), Prof Bernard Chazelle (non-reader).

Everyone is invited to attend her talk.  The talk title and abstract follow below:

Title: Eager and Lazy Deletion Rebalancing in Binary Search Trees

The binary search tree is a fundamental data structure with many applications. Following the invention of AVL tree, many kinds of balanced search trees were developed, with the aim of obtaining simpler updating or improved efficiency or both. In most of such data structures, deletion rebalancing is more complicated than insertion rebalancing. This leads naturally to the question of how much rebalancing is necessary to guarantee a logarithmic height bound. We explore ways to make binary search trees more efficient by delaying rebalancing on deletion. This talk will focus on variants of AVL trees. We propose a variant of weak AVL trees with an even weaker balance condition. Our trees improved the amortized time bounds for rebalancing steps while keeping the same worst-case height guarantee as weak AVL trees. We also propose another variant with lazy rebalancing steps separated from deletion operations themselves. The algorithm's performance is guaranteed by running a background process that rebalances unbalanced parts of the tree. Unlike the similar work of relaxed AVL trees, in which the tree only eventually becomes balanced, our method guarantees that the tree remains balanced at all times, if the background process is run sufficiently often. Finally, I will summarize with some ongoing work.