Unit Splay;

Interface

Type PTree = ^TTree;
     TTree = Record
               x : Integer;
               l, r : PTree;
             End;

Function member(Var T : PTree; x : Integer) : Boolean;

Implementation

Procedure print(T : PTree; d : integer);
Var i : Integer;
Begin
  If T = Nil Then Exit;
  For i := 1 To d Do Write('  ');
  Print(T^.l, d+1);
  Writeln(T^.x);
  Print(T^.r, d+1);
End;

Procedure Rotace1(Var T, U : PTree);
Var B, P : PTree;
Begin
  If U^.l = T Then
    Begin
      B := T^.r;

      P := U;
      U := T;
      T^.r := P;
      P^.l := B;
    End
  Else
    Begin
      B := T^.l;

      P := U;
      U := T;
      T^.l := P;
      P^.r := B;
    End;
End;


Procedure Rotace2(Var T, U, V : PTree);
Var A, B, C, P : PTree;
Begin
  If T = U^.l Then
    Begin
      A := V^.r;
      B := U^.r;
      C := T^.r;

      P := V;
      V := T;
      T^.r := U;
      U^.r := P;
      U^.l := C;
      P^.r := A;
      P^.l := B;
    End
  Else
    Begin
      A := V^.l;
      B := U^.l;
      C := T^.l;

      P := V;
      V := T;
      T^.l := U;
      U^.l := P;
      U^.r := C;
      P^.l := A;
      P^.r := B;
    End;
End;


Procedure Rotace3(Var T, U, V : PTree);
Var B, C, P : PTree;
Begin
  If T = U^.l Then
    Begin
      B := T^.l;
      C := T^.r;

      P := V;
      V := T;
      T^.l := P;
      T^.r := U;
      U^.l := C;
      P^.r := B;
    End
  Else
    Begin
      B := T^.r;
      C := T^.l;

      P := V;
      V := T;
      T^.r := P;
      T^.l := U;
      U^.r := C;
      P^.l := B;
    End;
End;


{ nepocita s T = nil, vraci True, pokud doslo k rotaci }
Function splay_r(Var T, U, V : PTree; x : Integer) : Boolean;
Var b : Boolean;
Begin
  splay_r := False;
  If (x < T^.x) And (T^.l <> Nil) Then
    Begin
      If splay_r(T^.l, T, U, x) Then Exit; { doslo k modifikaci U }
    End
  Else If (T^.x < x) And (T^.r <> Nil) Then
    Begin
      If splay_r(T^.r, T, U, x) Then Exit; { doslo k modifikaci U }
    End;

  { v tomto bodu je bud nalezen prvek T^.x, nebo nelze
    pokracovat v sestupu, nebo byla volana operace splay,
    ktera zmenila hodnotu T }

  If U = Nil Then Exit; { T je koren }
  If V = Nil Then
    Begin { U je koren }
      Rotace1(T, U);
      Exit;
    End;

  If ((V^.l = U) And (U^.l = T)) Or
     ((V^.r = U) And (U^.r = T)) Then
    Rotace2(T, U, V)
  Else
    Rotace3(T, U, V);

  splay_r := True;
End;

{ nepocita s T = nil }
Procedure splay_p(Var T : PTree; x : Integer);
Var U, V : PTree;
Begin
  U := Nil;
  V := Nil;
  splay_r(T, U, V, x);
End;

Function member(Var T : PTree; x : Integer) : Boolean;
Begin
  If T = Nil Then
    member := False
  Else
    Begin
      splay_p(T, x);
      member := T^.x = x;
    End;
End;

End.