SplayTree

This is the implementation of splay tree - self-balancing binary search tree.

Preamble · Operations · Amortized analysis

---

Preamble

The purpose of this project is to implement SplayTree class and it's basic operations.

• Splay tree qualities

Advantages	Disadvantages
Average-case performance is as efficient as other trees	In some cases the height of a splay tree can be linear
Splay trees don't need to store any additional data in nodes

---

Operations

• rotate(child, parent) - rotates edge between child and parent node in splay tree

• splay(x) - moves node x to splay tree's root due to following operations:

  • zig(x) - runs if there is no grandparent of target node

  

  • zig-zig(x) - runs if node and it's parent are both left or right childs of their parents

  

  • zig-zag(x) - runs if node and it's parent are not both left or right childs of their parents

  

• find(vertex, x) - trying to find node with value x beginning from given node vertex (as in simple BST).
  Then runs splay of it's result. If there is no node with value x in the tree then runs splay from node with closest value to x (leaf-node that was last during find process)

• split(vertex, x) - splits given by pointer vertex tree into two: in first all values are less than x, in second one all values are bigger or equal

• insert(vertex, x) - splits given by pointer vertex tree by value x. Then first subtree becomes left child and second subtree becomes right child of new node

• merge(root1, root2) - merges two trees into one. All values in first tree must be less than values in second tree

• remove(vertex, x) - removes from given by pointer vertex tree node with value x. Runs find(vertex, tree). Then runs merge left and right childs of new root.

---

Amortized analysis

• Amortized time of m operations is actually O(m*log(n))

• You can find proof here