ACTION Supprimer

ACTION Supprimer ( Val )

SOIT

Val UN ENTIER ;

Sauv_balance UN ENTIER ;

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

Trouv UN BOOLEEN ;

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

Sens UN ENTIER ;

DEBUT

CREERPILE ( Branche ) ;

P := Avl ;

Q := NIL ;

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 ) ;

Sens := - 1

SINON

P := FD ( P ) ;

Sens := + 1

FSI

FTQ ;

SI Trouv

SI ( FG ( P ) = NIL ) ET ( FD ( P ) = NIL )

SI Q = NIL

Avl := Q ;

/* Bug : AVL:= NIL ne marche pas!!! */

SINON

SI FG ( Q ) = P

AFF_FG ( Q , NIL )

SINON

AFF_FD ( Q , NIL )

FSI

SINON

SI FG ( P ) = NIL

SI Q = NIL

Avl := FD ( P )

SINON

SI FG ( Q ) = P

AFF_FG ( Q , FD ( P ) )

SINON

AFF_FD ( Q , FD ( P ) )

FSI

SINON

SI FD ( P ) = NIL

SI Q = NIL

Avl := FG ( P )

SINON

SI FG ( Q ) = P

AFF_FG ( Q , FG ( P ) )

SINON

AFF_FD ( Q , FG ( P ) )

FSI

SINON

D := FD ( P ) ;

Sens := + 1 ;

Q := P ;

EMPILER ( Branche , P ) ;

TQ FG ( D ) <> NIL

EMPILER ( Branche , D ) ;

Q := D ;

D := FG ( D ) ;

Sens := - 1

FTQ ;

{EMPILER ( Branche , D ) ;}

Sauv_balance := Balance ( P ) ;

AFF_INFO ( P , INFO ( D ) ) ;

APPEL Aff_balance ( P , Sauv_balance ) ;

SI FG ( Q ) = D

AFF_FG ( Q , FD ( D ) )

SINON

AFF_FD ( Q , FD ( D ) )

FSI

FSI ;

SI ( Q <> NIL )

APPEL Equilibrer_sup ( Branche , Sens )

FSI

FSI ;

FIN

ACTION Equilibrer_sup ( Branche , Sens ) ;

SOIT

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

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

Arret UN BOOLEEN ;

Sens UN ENTIER ;

Racine UN ARB DE ( ENTIER , ENTIER ) ;

Stop UN BOOLEEN ;

DEBUT

Arret := FAUX ;

DEPILER ( Branche , R ) ;

{ ECRIRE ( 'R:' , INFO ( R ) ) ;}

APPEL Aff_balance ( R , Balance ( R ) + Sens ) ;

SI PILEVIDE ( Branche )

Parent := NIL

SINON

DEPILER ( Branche , Parent ) ;

FSI ;

SI ( Balance ( R ) = 2 ) OU ( Balance ( R ) = - 2 )

SI Balance ( R ) = 2

APPEL Transf3 ( R , Parent , Racine ) ;

SINON

APPEL Transf4 ( R , Parent , Racine ) ;

FSI ;

R := Racine ;

{ECRIRE ( 'Rapres:' , INFO ( R ) ) ;}

SINON

Arret := ( Balance ( R ) <> 0 )

FSI ;

TQ ( Parent <> NIL ) ET ( NON Arret )

P := Parent ;

{ECRIRE ( 'P:' , INFO ( P ) ) ;}

SI ( FG ( P ) = R )

SI ( Balance ( R ) = 0 )

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

SINON

Arret := VRAI

FSI

SINON

SI ( Balance ( R ) = 0 )

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

SINON

Arret := VRAI

FSI

FSI ;

SI PILEVIDE ( Branche )

Parent := NIL

SINON

DEPILER ( Branche , Parent ) ;

FSI ;

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

SI Balance ( P ) = 2

APPEL Transf3 ( P , Parent , Racine ) ;

SINON

APPEL Transf4 ( P , Parent , Racine ) ;

FSI ;

R := Racine

SINON

SI Balance ( P ) <> 0

Arret := VRAI

SINON

R := P ;

FSI

FTQ ;

FIN

ACTION Transf3 ( A , Parent , Racine ) ;

SOIT

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

DEBUT

ECRIRE ( 'transf3' ) ;

{A doit avoir un fils gauche}

B := FG ( A ) ;

SI ( Balance ( B ) = 1 ) OU ( Balance ( B ) = 0 )

{Rotation droite}

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

AFF_FG ( A , FD ( B ) ) ;

AFF_FD ( B , A ) ;

SI Balance ( B ) = 1

APPEL Aff_balance ( B , 0 ) ;

APPEL Aff_balance ( A , 0 ) ;

SINON

APPEL Aff_balance ( B , - 1 ) ;

APPEL Aff_balance ( A , 1 ) ;

FSI ;

Racine := B ;

SI Parent = NIL

Avl := B

SINON

SI FG ( Parent ) = A

AFF_FG ( Parent , B )

SINON

AFF_FD ( Parent , B )

FSI

SINON

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

{ balance(b) = -1 }

{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 ;

Racine := C ;

SI Parent = NIL

Avl := C

SINON

SI FG ( Parent ) = A

AFF_FG ( Parent , C )

SINON

AFF_FD ( Parent , C )

FSI

FIN

ACTION Transf4 ( A , Parent , Racine ) ;

SOIT

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

DEBUT

ECRIRE ( 'transf4' ) ;

{A doit avoir un fils droit}

B := FD ( A ) ;

SI ( Balance ( B ) = - 1 ) OU ( Balance ( B ) = 0 )

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

{Rotation gauche}

AFF_FD ( A , FG ( B ) ) ;

AFF_FG ( B , A ) ;

SI Balance ( B ) = - 1

APPEL Aff_balance ( B , 0 ) ;

APPEL Aff_balance ( A , 0 ) ;

SINON

APPEL Aff_balance ( B , + 1 ) ;

APPEL Aff_balance ( A , - 1 ) ;

FSI ;

Racine := B ;

SI Parent = NIL

Avl := B

SINON

SI FG ( Parent ) = A

AFF_FG ( Parent , B )

SINON

AFF_FD ( Parent , B )

FSI

SINON

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

{ balance(b) = +1 }

{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 ;

Racine := C ;

SI Parent = NIL

Avl := C

SINON

SI FG ( Parent ) = A

AFF_FG ( Parent , C )

SINON

AFF_FD ( Parent , C )

FSI

FIN