HW 5

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s