A self balance BST with the additional property that the recent accessed node are quick to access again.

Splay tree doesn’t require extra space and supports insert, remove, and find operations all in amortized $O(\log{n})$ time and worst case $O(n)$ time.

Operations

Splay

Splaying the tree for a certain node is to rearrange the tree so that that node is put as the root of the tree.

Whenever a node (not root) is accessed, we splay it to move it closer to root. The detailed steps depend on 3 factors:

• whether the node (x) is left or right child of its parent
• whether the parent node (p) is root
• if not, whether the node’s parent is left or right child of its grandparent

other ops

• join: suppose there are 2 BSTs: S and T where all elements in S are ≤ to all elements in T. to merge S and T into 1 tree, we can splay on the largest element in S and merge the root of T as the right child of it
• split on x: split a tree T into 2 trees T1 and T2 where all elements in T1 ≤ to x and all elements in T2 > x.
• insert, remove, etc.: can piggy-back on join() and split()

Analysis

…