PROGRAM AVL(INPUT,OUTPUT);                                  
TYPE TBAL=-1..1;                                            
     REF=^KNOTEN;                                           
     KNOTEN=RECORD                                          
             C:CHAR;                                        
             BAL:TBAL;                                      
             LEFT,RIGHT:REF                                 
            END;                                            
VAR ROOT:REF;Z:CHAR;H:BOOLEAN;                              
                                                            
PROCEDURE PRINT(T:REF;N:INTEGER);                           
BEGIN                                                       
 IF T<>NIL THEN                                             
  BEGIN PRINT (T^.RIGHT,N+1);                               
        WRITELN(T^.C:N*4,T^.BAL);                           
        PRINT (T^.LEFT,N+1);                                
  END                                                       
END;                                                        
                                                            
PROCEDURE INSERT(X:CHAR;VAR P:REF;VAR H:BOOLEAN);           
 VAR P1,P2:REF;                                             
BEGIN                                                       
 IF P=NIL THEN                                              
  BEGIN (*ZEICHEN EINFUEGEN*)                               
   NEW(P);H:=TRUE;                                          
   WITH P^ DO                                               
   BEGIN C:=X;LEFT:=NIL;RIGHT:=NIL;BAL:=0 END;              
  END ELSE                                                  
 IF X<P^.C THEN                                             
  BEGIN INSERT(X,P^.LEFT,H);                                
   IF H THEN (*LINKER AST WURDE GROESSER*)                  
   CASE P^.BAL OF                                           
   -1: BEGIN P^.BAL:=0;H:=FALSE END;                        
    0: P^.BAL:=1;(*H BLEIBT TRUE!*)                         
    1: BEGIN (*AUSGLEICHEN*)                                
        P1:=P^.LEFT;                                        
        IF P1^.BAL=1 THEN (*ROTATION L:P P1   *)            
         BEGIN P^.LEFT:=P1^.RIGHT;P1^.RIGHT:=P;             
               P^.BAL:=0;P:=P1                              
         END                                                
        ELSE                                                
         BEGIN (*DOPPELROTATION L:P1 P2,R:P P2*)            
          P2:=P1^.RIGHT;                                    
          P1^.RIGHT:=P2^.LEFT;P2^.LEFT:=P1;                 
          P^.LEFT:=P2^.RIGHT;P2^.RIGHT:=P;                  
          IF P2^.BAL=1  THEN P^.BAL:=-1                     
                        ELSE P^.BAL:=0;                     
          IF P2^.BAL=-1 THEN P1^.BAL:=1                     
                        ELSE P1^.BAL:=0;                    
          P:=P2                                             
         END;                                               
        P^.BAL:=0;H:=FALSE                                  
       END                                                  
   END(*CASE*)                                              
  END ELSE                                                  
 IF X>P^.C THEN                                             
  BEGIN INSERT(X,P^.RIGHT,H);                               
   IF H THEN (*RECHTER AST WURDE GROESSER*)                 
   CASE P^.BAL OF                                           
    1: BEGIN P^.BAL:=0;H:=FALSE END;                        
    0: P^.BAL:=-1;(*H BLEIBT TRUE!*)                        
   -1: BEGIN (*AUSGLEICHEN*)                                
        P1:=P^.RIGHT;                                       
        IF P1^.BAL=-1 THEN (*ROTATION R:P P1   *)           
         BEGIN P^.RIGHT:=P1^.LEFT;P1^.LEFT:=P;              
               P^.BAL:=0;P:=P1                              
         END                                                
        ELSE                                                
         BEGIN (*DOPPELROTATION R:P1 P2,L:P P2*)            
          P2:=P1^.LEFT;                                     
          P1^.LEFT:=P2^.RIGHT;P2^.RIGHT:=P1;                
          P^.RIGHT:=P2^.LEFT;P2^.LEFT:=P;                   
          IF P2^.BAL=-1 THEN P^.BAL:=1                      
                        ELSE P^.BAL:=0;                     
          IF P2^.BAL=1  THEN P1^.BAL:=-1                    
                        ELSE P1^.BAL:=0;                    
          P:=P2                                             
         END;                                               
        P^.BAL:=0;H:=FALSE                                  
       END                                                  
   END(*CASE*)                                              
  END ELSE                                                  
   BEGIN WRITELN("EXISTIERT !");H:=FALSE END                
 END;(*INSERT*)                                             
                                                            
BEGIN                                                       
 ROOT:=NIL;                                                 
 REPEAT READLN(Z);INSERT(Z,ROOT,H);PRINT(ROOT,0)            
 UNTIL Z="^";                                               
END.