Due: ~~Wednesday March 7th, 2012~~ Friday March 9th, 2012

You’re given a splay tree formed by the following sequence of inserts: insert(1, S), insert(2, S), …, insert(n, S). S looks like a linked list n -> n-1 -> … -> 2 -> 1.

Give a sequence of m splay operations that keep the height of S at least \floor{n/2}.

You should end up with a tree that looks like a linked list but is actually 1 -> 2 -> … -> n-1 -> n.

Now, give an explanation as to why this data structure is as good as an ordinary binary search tree given that the tree is always highly unbalanced.

### Like this:

Like Loading...

*Related*