insertSplay(tree,item):
|  Input  tree, item
|  Output tree with item splay-inserted
|
|  if tree is empty then return new node containing item
|  else if item=data(tree) then return tree
|  else if item<data(tree) then
|  |  if left(tree) is empty then
|  |     left(tree)=new node containing item
|  |  else if item<data(left(tree)) then
|  |        // Case 1: left-child of left-child "zig-zig"
|  |     left(left(tree))=insertSplay(left(left(tree)),item)
|  |     tree=rotateRight(tree)
|  |  else if item>data(left(tree)) then
|  |        // Case 2: right-child of left-child "zig-zag"
|  |     right(left(tree))=insertSplay(right(left(tree)),item)
|  |     left(tree)=rotateLeft(left(tree))
|  |  end if
|  |  return rotateRight(tree)
|  else     // item>data(tree)
|  |  if right(tree) is empty then
|  |     right(tree)=new node containing item
|  |  else if item<data(right(tree)) then
|  |        // Case 3: left-child of right-child "zag-zig"
|  |     left(right(tree))=insertSplay(left(right(tree)),item)
|  |     right(tree)=rotateRight(right(tree))
|  |  else if item>data(right(tree)) then
|  |        // Case 4: right-child of right-child "zag-zag"
|  |     right(right(tree))=insertSplay(right(right(tree)),item)
|  |     tree=rotateLeft(tree)
|  |  end if
|  |  return rotateLeft(tree)
|  end if