Citation Youtube Harvard University.

Splay Trees supports inserting item k as a key with a v value.

Find (k) returns associated value.

Splay trees are binary search trees.

After each operation, the tree adjusts itself (rebalancing).

BST model - Binary search tree. At the beginning of each operation there is the pointer to the root.

At teach step we can follow a child.

Rotations - Rotate (x) (y). x is the root, then y then b and c.

To do a find. Search for x as you would in a BST. Then after reaching x, Splay (x).

Insert x as in any BST then splay (x).

Then delete: :" Splay x