splaytree.pas

伸展树……我写的很难看

Program SplayTree;
Type
    Dat=Record
              Father, LeftChild, RightChild, Num:Longint;
        End;
Var
   I, Len, N, M, Root:Longint;
   Tree:Array[0..10000] Of Dat;

   Procedure Splay(X:Longint);
   Var
      I, J:Longint;

      Procedure Zig(Var X:Longint);
      Var
         I, J:Longint;
      Begin
           I:=Tree[X].Father;
           J:=Tree[I].Father;
           Tree[X].Father:=Tree[I].Father;
           Tree[I].Father:=X;
           Tree[I].LeftChild:=Tree[X].RightChild;
           Tree[Tree[X].RightChild].Father:=I;
           Tree[X].RightChild:=I;
           If Tree[J].LeftChild=I Then Tree[J].LeftChild:=X
           Else Tree[J].RightChild:=X;
           If Tree[X].Father=0 Then Root:=X;
      End;

      Procedure Zag(Var X:Longint);
      Var
         I, J:Longint;
      Begin
           I:=Tree[X].Father;
           J:=Tree[I].Father;
           Tree[X].Father:=Tree[I].Father;
           Tree[I].Father:=X;
           Tree[I].RightChild:=Tree[X].LeftChild;
           Tree[Tree[X].LeftChild].Father:=I;
           Tree[X].LeftChild:=I;
           If Tree[J].LeftChild=I Then Tree[J].LeftChild:=X
           Else Tree[J].RightChild:=X;
           If Tree[X].Father=0 Then Root:=X;
      End;

   Begin
        I:=Tree[X].Father;
        While (I<>0) And (Tree[I].Father<>0) Do
        Begin
             J:=Tree[I].Father;
             If (Tree[J].LeftChild=I) And (Tree[I].LeftChild=X) Then
             Begin
                  Zig(I);
                  Zig(X);
             End
             Else If (Tree[J].RightChild=I) And (Tree[I].RightChild=X) Then
             Begin
                  Zag(I);
                  Zag(X);
             End
             Else If (Tree[J].RightChild=I) And (Tree[I].LeftChild=X) Then
             Begin
                  Zig(X);
                  Zag(X);
             End
             Else If (Tree[J].LeftChild=I) And (Tree[I].RightChild=X) Then
             Begin
                  Zag(X);
                  Zig(X);
             End;
             I:=Tree[X].Father;
        End;
        If I<>0 Then
           If X=Tree[I].LeftChild Then Zig(X)
           Else Zag(X);
   End;

   Procedure InsertNum(N:Longint);
   Var
      I:Longint;
   Begin
        I:=Root;
        While True Do
        Begin
             If N<=Tree[I].Num Then
                If Tree[I].LeftChild<>0 Then
                Begin
                     I:=Tree[I].LeftChild;
                     Continue;
                End
                Else
                Begin
                     Tree[I].LeftChild:=Len;
                     Tree[Len].Num:=N;
                     Tree[Len].Father:=I;
                     Splay(Len);
                     Break;
                End;
             If N>Tree[I].Num Then
                If Tree[I].RightChild<>0 Then
                Begin
                     I:=Tree[I].RightChild;
                     Continue;
                End
                Else
                Begin
                     Tree[I].RightChild:=Len;
                     Tree[Len].Num:=N;
                     Tree[Len].Father:=I;
                     Splay(Len);
                     Break;
                End;
        End;
   End;

   Procedure Delete(X:Longint);
   Var
      I, J:Longint;
   Begin
        I:=0;
        If Tree[X].LeftChild<>0 Then Inc(I, 1);
        If Tree[X].RightChild<>0 Then Inc(I, 10);
        If I<11 Then
        Begin
             If I=1 Then
             Begin
                  J:=Tree[X].LeftChild;
                  Tree[J].Father:=Tree[X].Father;
                  Tree[Tree[J].LeftChild].Father:=X;
                  Tree[Tree[J].RightChild].Father:=X;
                  Tree[X]:=Tree[J];
                  FillChar(Tree[J], SizeOf(Tree[J]), 0);
             End;
             If I=10 Then
             Begin
                  J:=Tree[X].RightChild;
                  Tree[J].Father:=Tree[X].Father;
                  Tree[Tree[J].LeftChild].Father:=X;
                  Tree[Tree[J].RightChild].Father:=X;
                  Tree[X]:=Tree[J];
                  FillChar(Tree[J], SizeOf(Tree[J]), 0);
             End;
             If (I=0) And (I<>Root) Then
             Begin
                  If Tree[Tree[X].Father].LeftChild=X Then Tree[Tree[X].Father].LeftChild:=0
                  Else Tree[Tree[X].Father].RightChild:=0;
                  Tree[X].Father:=0;
                  FillChar(Tree[X], SizeOf(Tree[X]), 0);
             End;
        End
        Else
        Begin
             J:=Tree[X].RightChild;
             While True Do
             Begin
                  If Tree[J].LeftChild<>0 Then J:=Tree[J].LeftChild
                  Else Break;
             End;
             If Tree[Tree[J].Father].LeftChild=J Then
                Tree[Tree[J].Father].LeftChild:=Tree[J].RightChild
             Else Tree[Tree[J].Father].RightChild:=Tree[J].RightChild;
             Tree[Tree[J].RightChild].Father:=Tree[J].Father;
             Tree[X].Num:=Tree[J].Num;
             FillChar(Tree[J], SizeOf(Tree[J]), 0);
        End;
   End;

Begin
     Readln(N);
     Len:=0;
     For I:=1 To N Do
     Begin
          Inc(Len);
          Readln(M);
          InsertNum(M);
     End;
End.