Двоичное дерево

{$I-,Q-,R-,S-}
const
    FileIn  = 'Input.txt' ;
    FileOut = 'Output.txt';
 
type
    TTreeType = ^TreeType ;
    TreeType  = record
               Left  : TTreeType ;
               Right : TTreeType ;
               Prev  : TTreeType ;
               key   : longint   ;
            end;
 
var
    N     : longint   ;
    Root,Buff : TTreeType ;
 
procedure TreeInsert( var X : TTreeType ; p : longint );
begin
    if X = nil then begin
                 New( X );
                 X^.Prev := Buff ;
                 X^.Left := nil ;
                 X^.Right := nil ;
                 X^.key := p ;
                 Exit ;
                end;
    Buff := X ;
    if p < X^.key then TreeInsert( X^.Left , p )    
              else TreeInsert( X^.Right , p );
end;
 
function TreeSearch( var X : TTreeType ; p : longint ) : TTreeType ;
begin
    TreeSearch := nil ;
    if X <> nil then
      if X^.key = p then TreeSearch := X
            else begin
                  if p < X^.key
                        then TreeSearch := TreeSearch( X^.Left,p )
                    else TreeSearch := TreeSearch( X^.Right,p );
                 end;           
end;
 
function TreeSuccessor( X : TTreeType ) : TTreeType ;
begin
    X := X^.Right ;
    while X^.Left <> nil do
      X := X^.Left ;
    TreeSuccessor := X ;
end;
 
procedure TreeDelete( p : longint );
 
procedure DeleteNode( var z : TTreeType );
var
    y,x : TTreeType ;
begin
    if ( z^.Left = nil ) or ( z^.Right = nil )
        then y := z
        else y := TreeSuccessor( z );
    if y^.Left <> nil then x := y^.Left
              else x := y^.Right ;
        if x <> nil then x^.Prev := y^.Prev ;
    if y^.Prev = nil then Root := x
             else if y = y^.Prev^.Left then y^.Prev^.Left := x
                           else y^.Prev^.Right := x ;
    if y <> z then z^.key := y^.key ;
end;
 
begin
    Buff := TreeSearch( Root , p );
    DeleteNode( Buff );
end;
 
procedure Solution;
var
    i,Chislo : longint ;
    Query    : char    ;
begin
    Assign( Input , FileIn );
    ReSet( Input );
    ReadLn( N );
    for i:=1 to N do
       begin
        Read( Query );
        ReadLn( Chislo );
        Buff := nil ;
        case Query of
          'I' : TreeInsert( Root , Chislo );
          'D' : TreeDelete( Chislo );
          'S' : if TreeSearch( Root , Chislo ) <> nil
                        then WriteLn( 'YES' )
                        else WriteLn( 'NO' );
        end;
       end;
    Close( Input );
end;
 
begin
    Solution;
end.