Splay tree

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)

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

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