🚀 go-pugleaf

Student Seminar
Speaker: Murray Sherk
Time and place: Tuesday, February 21, 3:00pm, GB420.

Basic Outline:

In 1983, Sleator and Tarjan introduced an efficient form of self-adjusting 
search tree called a splay tree. I show how to extend the idea of splaying so
it applies to k-ary search trees as well as binary search trees.
There are several problems encountered in doing this and I'll explain
them a bit as I give my solutions. 

Consider the following: Let s be a sequence of search requests. Assume you
know s and want to minimize the cost of doing s. You get to pick any search
tree you want, but you are not allowed to change it during the sequence. 
The tree you pick will be a static optimal tree for sequence s. 

In order to find the static optimal tree, you have to know s in advance.
For some sequences, the cost of s in the static optimal tree can be a factor
of logn better than the cost of s in a balanced tree (such as an AVL tree).
Surprisingly, splay trees do "as well" as static optimal trees but are
completely online (i.e. have no knowledge of s). They can also get completely
unbalanced, yet do "as well" as balanced trees when we allow insertions 
and deletions.

I'll talk about amortized analysis and splay tree efficiency. Then I'll
show how to extend splaying to k-ary search trees -- meaning we can now get
a self-adjusting version of the ever-popular B-tree data structure.
No prior knowledge of splay trees or amortized analysis is required, but
you should know what a binary search tree is. Even if you don't follow all
of the analysis, the definitions of the data structures are easy to understand
and well worth knowing.