1.  Splay Trees

Always move an element you are interested in to the root. Capitol letters are trees and lowercase letters are elements in the following

Split(i,S) will do Insert(i,S) then Splay(i,S) where Splay(i,S) moves i to the root of the tree by rotations.

1.1  Splay(x,S)

1. while (x not root)
2. parent(x)=y, parant(y)=z if z exists
3. !$z then rotate(x)
4. $z

• case a: z>y>x or x>y>z then rotate(y); rotate(x)
• case b: z>x>y or y>x>z then rotate(x); rotate(y)

1.2  Timing analysis

Definitions

• |S| = # nodes in tree S
• S(x) = subtree rooted at x
• m(s) = ë log|S| û
• m(x) = m(S(x))
• [`(m)](S) = S_{x Î S}m(x)

3 credit cards to charge costs to:

visa, mastercard (MC), americanexpress (AE)

• !$z -> AE
• $z , case 1. if [`(m)](S¢) < [`(m)](S) then visa else MC

[`(m)] is a measure of how balanced a tree is. For a completely unbalanced tree, [`(m)](S) = O(n*log(n)) . For a totally balanced tree, [`(m)](S) = O(n)

after m splay(x,S) calls

• AE £ m
• MC

in all cases [`(m)](x¢) ³ m(x) because x is moving up in the tree.

The lemma, together with m(x) £ log(n) means MC £ m*log(n) because m(x) can increase at least 1 to log(n) .

• Visa £ [`(m)](S<sub>begin</sub>)-[`(m)](S_end)+ something more due to the times when the MC is charged

The total ``something more'' is less than 2*log(n) for each splay.

Visa £ [`(m)](S<sub>begin</sub>)-[`(m)](S_end)+2m*log(n)

proof: add up AE, MC, and Visa