12 - Splay Trees

Is the following tree a valid splay tree?

• no

• yes

Which of the following is TRUE about splay trees?

• Splay trees implement the move-to-front heuristic<br />
• Splay trees are perfectly balanced
• Inserting an entry into a splay tree has worst-case cost of O(logn)
• Splay trees are proper binary trees

When splaying X, what is the first rotation performed?

• zig-zig

• zig-zag

• zig

• zag

When splaying X, which node do you rotate FIRST?

• rotate T left around L

• rotate X left around T

• rotate S right around T

When splaying S, what is the first rotation performed?

• zig-zag

• zig-zig

• zig

• zag

When splaying S, which node do you rotate FIRST?

• rotate S right around T

• rotate T left around L

• rotate X left around T