ACTION Inserer ( Val )

   SOIT

       Val UN ENTIER ;

       Doublet UN ( ENTIER , ENTIER ) ;

       P , Q , R DES ARB DE ( ENTIER , ENTIER ) ;

       Trouv UN BOOLEEN ;

       Branche UNE PILE DE ARB DE ( ENTIER , ENTIER ) ;

   DEBUT

       ECRIRE ( 'inserer   >>>' , Val ) ;

       CREERPILE ( Branche ) ;

       SI Avl = NIL

           INIT_STRUCT ( Doublet , [ Val , 0 ] ) ;

           CREERNOEUD ( Avl ) ;

           AFF_INFO ( Avl , Doublet )

       SINON

           P := Avl ;

           Trouv := FAUX ;

           TQ ( P <> NIL ) ET NON Trouv

               SI STRUCT ( INFO ( P ) , 1 ) = Val

                   Trouv := VRAI

               SINON

                   Q := P ;

                   EMPILER ( Branche , P ) ;

                   SI STRUCT ( INFO ( P ) , 1 ) > Val

                       P := FG ( P )

                   SINON

                       P := FD ( P )

                   FSI

               FSI

           FTQ ;

           SI NON Trouv

               INIT_STRUCT ( Doublet , [ Val , 0 ] ) ;

               CREERNOEUD ( R ) ;

               AFF_INFO ( R , Doublet ) ;

               SI Val < STRUCT ( INFO ( Q ) , 1 )

                   AFF_FG ( Q , R )

               SINON

                   AFF_FD ( Q , R )

               FSI ;

               APPEL Equilibrer_ins ( Branche , R ) ;

           FSI ;

       FSI

   FIN

   ACTION Equilibrer_ins ( Branche , R ) ;

   SOIT

       Branche UNE PILE DE ARB DE ( ENTIER , ENTIER ) ;

       P , R , Parent DES ARB DE ( ENTIER , ENTIER ) ;

       Arret UN BOOLEEN ;

   DEBUT

       Arret := FAUX ;

       TQ NON PILEVIDE ( Branche ) ET ( NON Arret )

           DEPILER ( Branche , P ) ;

           SI FG ( P ) = R

               APPEL Aff_balance ( P , Balance ( P ) + 1 )

           SINON

               APPEL Aff_balance ( P , Balance ( P ) - 1 )

           FSI ;

           SI ( Balance ( P ) = 2 ) OU ( Balance ( P ) = - 2 ) OU ( Balance ( P ) = 0 )

               Arret := VRAI

           SINON

               R := P ;

           FSI

       FTQ ;

       SI Arret

           SI Balance ( P ) <> 0

               SI PILEVIDE ( Branche )

                   Parent := NIL

               SINON

                   DEPILER ( Branche , Parent )

               FSI ;

               SI Balance ( P ) = 2

                   APPEL Transf1 ( P , Parent )

               SINON

                   APPEL Transf2 ( P , Parent )

               FSI

           FSI

       FSI

   FIN

   ACTION Transf1 ( A , Parent ) ;

   SOIT

       A , B , C , Parent DES ARB DE ( ENTIER , ENTIER ) ;

   DEBUT

       ECRIRE ( 'transf1' ) ;

      {A doit avoir un fils gauche}

       B := FG ( A ) ;

       SI Balance ( B ) = 1

      {noeud inséré à gauche de B}

      {Rotation droite}

           ECRIRE ( 'Rotation droite autour de ' , STRUCT ( INFO ( B ) , 1 ) ) ;

           AFF_FG ( A , FD ( B ) ) ;

           AFF_FD ( B , A ) ;

           APPEL Aff_balance ( B , 0 ) ;

           APPEL Aff_balance ( A , 0 ) ;

           SI Parent = NIL

               Avl := B

           SINON

               SI FG ( Parent ) = A

                   AFF_FG ( Parent , B )

               SINON

                   AFF_FD ( Parent , B )

               FSI

           FSI

       SINON

           ECRIRE ( 'Rotation gauche suivie par une rotation droite autour de ' , STRUCT ( INFO ( FD ( B ) ) , 1 ) ) ;

          { balance(b) = -1 }

          {noeud inséré à droite de B}

          {soit C le fils droit de B (qui doit exister) }

           C := FD ( B ) ;

          {rotation gauche}

           AFF_FD ( B , FG ( C ) ) ;

           AFF_FG ( C , B ) ;

          {suivie par une rotation droite}

           AFF_FG ( A , FD ( C ) ) ;

           AFF_FD ( C , A ) ;

          {maj balance}

           SI Balance ( C ) = 0

          { C est le nouveau noeud inséré }

               APPEL Aff_balance ( A , 0 ) ;

               APPEL Aff_balance ( B , 0 ) ;

           SINON

               SI Balance ( C ) = 1

                   APPEL Aff_balance ( A , - 1 ) ;

                   APPEL Aff_balance ( B , 0 ) ;

                   APPEL Aff_balance ( C , 0 ) ;

               SINON

                   APPEL Aff_balance ( A , 0 ) ;

                   APPEL Aff_balance ( B , + 1 ) ;

                   APPEL Aff_balance ( C , 0 ) ;

               FSI

           FSI ;

           SI Parent = NIL

               Avl := C

           SINON

               SI FG ( Parent ) = A

                   AFF_FG ( Parent , C )

               SINON

                   AFF_FD ( Parent , C )

               FSI

           FSI

       FSI

   FIN

   ACTION Transf2 ( A , Parent ) ;

   SOIT

       A , B , C , Parent DES ARB DE ( ENTIER , ENTIER ) ;

   DEBUT

       ECRIRE ( 'transf2' ) ;

      {A doit avoir un fils droit}

       B := FD ( A ) ;

       SI Balance ( B ) = - 1

           ECRIRE ( 'Rotation gauche autour de ' , STRUCT ( INFO ( B ) , 1 ) ) ;

          {noeud inséré à droite de B}

          {Rotation gauche}

           AFF_FD ( A , FG ( B ) ) ;

           AFF_FG ( B , A ) ;

           APPEL Aff_balance ( B , 0 ) ;

           APPEL Aff_balance ( A , 0 ) ;

           SI Parent = NIL

               Avl := B

           SINON

               SI FG ( Parent ) = A

                   AFF_FG ( Parent , B )

               SINON

                   AFF_FD ( Parent , B )

               FSI

           FSI

       SINON

           ECRIRE ( 'Rotation droite suivie par une rotation gauche autour de ' , STRUCT ( INFO ( FG ( B ) ) , 1 ) ) ;

          { balance(b) = +1 }

          {noeud inséré à gauche de B}

          {soit C le fils gauche de B (qui doit exister) }

           C := FG ( B ) ;

          {rotation gauche}

           AFF_FG ( B , FD ( C ) ) ;

           AFF_FD ( C , B ) ;

          {suivie par une rotation droite}

           AFF_FD ( A , FG ( C ) ) ;

           AFF_FG ( C , A ) ;

          {maj balance}

           SI Balance ( C ) = 0

          {C est le nouveau noeud inséré }

               APPEL Aff_balance ( A , 0 ) ;

               APPEL Aff_balance ( B , 0 ) ;

           SINON

               SI Balance ( C ) = 1

                   APPEL Aff_balance ( A , 0 ) ;

                   APPEL Aff_balance ( B , - 1 ) ;

                   APPEL Aff_balance ( C , 0 ) ;

               SINON

                   APPEL Aff_balance ( A , + 1 ) ;

                   APPEL Aff_balance ( B , 0 ) ;

                   APPEL Aff_balance ( C , 0 ) ;

               FSI

           FSI ;

           SI Parent = NIL

               Avl := C

           SINON

               SI FG ( Parent ) = A

                   AFF_FG ( Parent , C )

               SINON

                   AFF_FD ( Parent , C )

               FSI

           FSI

       FSI

   FIN