splay trees

Question 1

splay tree property

Answer 1

Data more recently accessed is near the root

The operation on each element will rearrange the tree so that this element will be placed at the root of the tree

Question 2

zig

Answer 2

right rotation

Question 3

zag

Answer 3

left rotation

Question 4

zig-zig

Answer 4

right-right rotate

Question 5

zag-zag

Answer 5

left-left rotate

Question 6

zig-zag

Answer 6

right left rotate

Question 7

zag-zig

Answer 7

left right rotate

Question 8

Splay Operations: Find

Answer 8

Find the node in normal BST manner
Splay the node to the root

Question 9

what is amortized analysis?

Answer 9

In Amortized Analysis, we analyze a sequence of operations and guarantee a worst-case average time which is lower than the worst-case time of a particular expensive operation.

Question 10

splay tree algorithm analysis

Answer 10

Worst case time is 𝑂(𝑛)

Amortized time for all operations is 𝑂(log⁡𝑛)
a sequence of 𝑀 operations on an 𝑛-node splay tree takes 𝑂(𝑀 log⁡𝑛) time.
Maybe not now, but soon, and for the rest of the operations

Question 11

what is the final depth of a node on the splay path?

Answer 11

If a node on the access path is at depth 𝑑 before the splay, it’s final depth ≤3+𝑑⁄2

Question 12

splay tree insert and delete

Answer 12

Insert x
Insert x as normal then splay x to root.

Delete x
Find x
Splay x to root and remove it
Splay the max in the left subtree to the root
Attach the right subtree to the new root of the left subtree.

𝑂(𝑛2) time for 𝑛 inserts