Parte 1 da T5: Splay tree e treaps com split e join

Splay tree

Seu programa deve inicializar uma splay tree vazia.

Codificação das operações: 

1 <x> significa Insert(r, x)
2 <x> significa Delete(r, x)
3 <x> significa println(Search(r, x)? 1 : 0)
4     significa println(Min(r))
5     significa Print(r)
6 <x> significa Print(r1) e Print(r2) onde (r1,r2) é o resultado do Split(r, x)
Exemplo de entrada para o programa de testes: 
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
5
4
5
3 2
5
2 8
Saída esperada para este teste:

Exceto pela última impressão da árvore, que depende de se você substitui o 8 pelo mínimo da árvore direita, ou pelo máximo da árvore esquerda. 

                           1
                        2
                     3
                  4
               5
            6
         7
      8
   9
10
1
1
               2
                  3
            4
               5
         6
            7
      8
         9
   10			   
1
   1
2
         3
      4
            5
         6
            7
   8
         9
      10

Treaps com split e join

Sua treap deve aceitar os mesmos comandos da splay tree, e você pode submeter a sua treap ao mesmo teste acima.

Aqui você encontra mais alguns exemplos de testes.