Nouvelle page 1

{

Arbres AVL

Réalisation D.E ZEGOUR

Insertion

Supression

Aout 2006

}

SOIT

Avl UN ARB DE ( ENTIER , ENTIER ) ;

{

// entier 1 : Valeur

// entier 2 : Balance

}

Tab UN VECTEUR (100 ) DE ENTIER ;

Inordre , Inserer , Supprimer DES ACTIONS ;

Balance UNE FONCTION ( ENTIERS ) ;

Aff_balance UNE ACTION ;

Equilibrer_ins , Equilibrer_sup DES ACTIONS ;

Transf1 , Transf2 , Transf3 , Transf4 DES ACTIONS ;

Profondeur UNE FONCTION ( ENTIER ) ;

I UN ENTIER ;

DEBUT

Avl := NIL ;

POUR I := 1 , 100

AFF_ELEMENT ( Tab [ I ] , ALEANOMBRE ( 1000 ) ) ;

APPEL Inserer ( ELEMENT ( Tab [ I ] ) ) ;

APPEL Inordre ( Avl ) }

FPOUR ;

ECRIRE ( 'Parcours Inordre' ) ;

APPEL Inordre ( Avl ) ;

ECRIRE ( 'suppression' ) ;

POUR I := 1 , 100

ECRIRE ( 'Sup de ' , ELEMENT ( Tab [ I ] ) ) ;

APPEL Supprimer ( ELEMENT ( Tab [ I ] ) ) ;

APPEL Inordre ( Avl ) ;

FPOUR ;

{ APPEL Inordre ( Avl ) ;}

FIN ;

FONCTION Balance ( P ) : ENTIER ;

SOIT

P UN ARB DE ( ENTIER , ENTIER ) ;

DEBUT

Balance := STRUCT ( INFO ( P ) , 2 )

FIN

ACTION Aff_balance ( P , V )

SOIT

P UN ARB DE ( ENTIER , ENTIER ) ;

V UN ENTIER ;

DEBUT

AFF_STRUCT ( INFO ( P ) , 2 , V )

FIN

FONCTION Profondeur ( P ) : ENTIER ;

SOIT

P UN ARB DE ( ENTIER , ENTIER ) ;

DEBUT

SI P = NIL

Profondeur := 0

SINON

Profondeur := MAX ( 1 + Profondeur ( FG ( P ) ) , 1 + Profondeur ( FD ( P ) ) )

FSI

FIN

ACTION Inordre ( P ) ;

SOIT

P UN ARB DE ( ENTIER , ENTIER ) ;

Tg , Td , Dif DES ENTIERS ;

DEBUT

SI P <> NIL

APPEL Inordre ( FG ( P ) ) ;

{ ECRIRE ( INFO ( P ) ) ;}

Tg := Profondeur ( FG ( P ) ) ;

Td := Profondeur ( FD ( P ) ) ;

SI Tg >= Td

Dif := Tg - Td

SINON

Dif := Td - Tg

FSI ;

SI Dif > 1

ECRIRE ( 'ERREUR dif=' , Dif )

FSI ;

APPEL Inordre ( FD ( P ) )

FSI

FIN

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

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

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

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

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

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

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

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