SUPpression dans un TAs MAX                     (c)~/2A env.- Création: 1999.10.24

                                                                       MàJ:   28/10/2009 / Hao Nguyen-Phu

                                                                                                        

                CORRIGE PARTIEL  (Version récursive)

 

Rappel du problème:

On souhaite toujours détruire la racine dans un tas MAX i.e. un arbre binaire partiellement ordonné dans le sens croissant (ARBRE MAX) où les clés des sous-arbres ne dépassent pas la valeur de celle du noeud courant. En effet, il n'y a AUCUN intérêt de détruire un élément autre que la racine ici à cause des applications dans des files de priorités. Comme exemple, on peut gérer la queue d'impression sur une imprimante commune dans un réseau d'ordinateurs sous UNIX/Linux. Ainsi le 'Typelt2' du  champ 'suite' (cf. cours CG) peut être du type "CHAINE DE CARACTERES" contenant l'information sur l'utilisateur, son terminal, le nom du  fichier à imprimer ainsi que sa taille.  Comme choix de priorités,  plus le fichier est de petite taille, plus il est prioritaire: donc,  la valeur de son champ 'clé' est plus grande...

Par ailleurs, et par définition aussi, un TAS est aussi un arbre PARFAIT (i.e. PRESQUE  PLEIN  i.e. presque rempli par des feuilles au dernier niveau de gauche à droite). Autrement dit, un tas  se présente toujours une forme triangulaire.  De cette façon, la meilleure représentation des tas est un tableau  contigu de P_CART (cf.  cours). Dans la suite de cet exercice,  on va simplifier le P_CART en considérant uniquement le champ 'clé' comme un type 'Entier' simple occupant  quatre octets en mémoire.

 

Analyse:

                                             EXEMPLE I (Suppression 'manuelle')

 

Considérons le Tas Max ci-dessous:

 

                            [1]   (16)

                                  /      \ 

                                 /         \

                     [2] (14)     [3] (7)

                          /     \         /      \

               [4] (2)  [5](8)  (1)[6]  (4) [7]

 

                              (a) Structure initiale du Tas Max

 

Notation adoptée:

On note le rang des noeuds, de gauche à droite et dans l'ordre des niveaux croissants, entre crochets: [Rang];  la valeur du noeud entre parenthèses: (val.).

 

Compte tenu de la propiété de complétude  partielle d'arbres binaires, la SDD la plus appropriée ici est la représentation par un tableau contigu (i.e.  implémentation  notée  ‘ABII’):

 

               [Rang]   1             2             3             4             5             6             7

               (val.)      16           14           7             2             8             1             4

 

Dans cet exemple, l'arbre est un arbre entier (complet au sens strict) car le nombre max. (n=7) des noeuds est ici atteint pour une hauteur (h=3) ce qui vérifie effectivement la relation:

                             

                                             n = 2^h - 1.

                                            

On ne supprime que la valeur (16) de la racine [en vue d'un tri par ordre décroissant par exemple] et on doit y mettre le dernier élément (4) à la place pour assurer la complétude. Et la représentation par le tableau contigu devient:

 

               [Rang]   1             2             3             4             5             6             7

               (val.)      4             14           7             2             8             1             NIL

La représentation arborescente sur une feuille de brouillon A4, par exemple, facilitera le raisonnement ci-après.

 

 

                                  ( 4 )

                                 /    \    

                                /      \

                           (14)       (7)

                             /  \      /   \

                       (2)   (8)  (1)   (NIL)

               (b) structure arborescente de l'arbre binaire résultant.

 

Cet arbre résultant ne vérifie plus la propriété du Tas Max (cf. Cours).  Il faut donc le ré-organiser. La manipulation s'appelle aussi 'ENTASSER'  qui consiste à permuter (4) et (14) pour commencer:

 

               [Rang]   1             2             3             4             5             6             7

               (val.)      14           4             7             2             8             1             NIL

 

 

                                  ( 14 )

                                  /    \   

                                 /      \

                            (4)         (7)

                             /  \        /  

                        (2)   (8)  (1) 

 (c) représentation arborescente de l'arbre après cette permutation.

 

On ne permute pas ici (4) et (7) car 4 < 7. Mais le sous-arbre gauche (SAG)  viole toujours la définition d'un tas. Pour rétablir le tas, on se déplace dans le SAG, en comparant le noeud parent avec ses noeuds enfants et en échangeant les éléments non ordonnés jusqu'à ce que le tas soit rétabli.  La figure ci-dessous illustre l'état final:     

 

 

                                  ( 14 )

                                  /     \  

                                 /        \

                              (8)       (7)

                             /  \        /  

                        (2)  (4)  (1) 

               (d) structure finale du tas max après tassement.

 

C'est donc un arbre binaire presque rempli (ou plein au sens large)  qui vérifie aussi la structure partiellement ordonnée d'un tas max.

 

 

                              EXEMPLE II (Autre suppression 'manuelle')

 

Considérons un autre Tas Max ci-après:

                               ( 35 )

                               /     \

                              /        \

                         (16)       (10)

                          /    \       /   \

                         /      \     /     \

                    (14)    (7) (9)   (3)

                     /  \     /   \

                (2)  (8) (1)   (4)

 

[Rang]   1     2   3   4   5   6   7   8   9  10  11   12     13    14     15

(val.)      35 16 10 14   7   9   3   2   8    1    4   NIL  NIL  NIL   NIL

 

                              (a) Structure initiale du Tas Max

 

EXERCICE (A FAIRE ABSOLUMENT):

 

On désire supprimer la racine (35) en mettant le dernier élément (4) à la place. Ré-organiser 'à la main' sur une feuille de brouillon A4 selon la représentation la plus appropriée et montrer que, à partir de certaines étapes, on retrouve la suppression 'manuelle' de l'exemple I afin d'assurer l'entassement du tas résultant final.

 

D'où l'algorithme récursif de "Sup_tas_max_r" [A TERMINER]:

 

STRUCTURE DE DONNEES ADOPTEE:

 

Constante            N_MAX = 15                    /* = taille maximale du tas  */

TYPE TypeC= ENTIER                   /* ou CARACTERE ... */

 

TYPE Tas=          TABLEAU[1 ... N_MAX] DE TypeC

n:                           ENTIER                /* taille effective du tas  <= N_MAX */

                                                            /* déclarée comme variable globale   */

PROC. Entasser_r(D/R  A: Tas, D i: ENTIER)

// A est un tas vu comme un tableau contigu en mode D/R.

// i: indice de la racine courante à partir duquel on doit entasser.

// Etant déclaré comme variable globale, n n'est pas explicité parmi  les arguments de 'Entasser_r'

// NB.: Cette procédure sera ré-utilisée lors de la mise en oeuvre de la méthode de tri par tas [en n.log2(n)]

DEBUT

               g, d: ENTIER       // indices de repérage des filsg et filsd

                              // Rappel: A[2i] = filsg(A[i]);  A[2i+1] = filsd(A[i]);

               max: ENTIER       // indice du noeud courant ayant la val. maximale

               g <-- 2i; d <-- 2i+1

               max <-- i

               SI  g<=n  ET  A[g] > A[i] ALORS

                              max <-- g                                            FSI

               SI  d<=n  ET  A[d] > A[max]           ALORS

                              max <-- d                                            FSI

               SI           max <> i ALORS

                                             ECHANGER(A[i], A[max])  // en Java :   PERMUTER(A[ ], i, max)

                                             Entasser_r(A, max)           // <==> appel récursif

               FSI

FIN

 

FONCTION Sup_tas_max_r(D/R A: Tas, D/R  n: ENTIER): TypeC

// destruction de la racine c-à-d l'élément avec la plus haute valeur 

DEBUT

               item, tmp:             TypeC

               SI (n = 0)              ALORS

                              ECRIRE('Rien à enlever: le tas est VIDE !')

               SINON

                              item <-- A[1]

                              // sauvegarde de la racine du tas pour le retour

                              tmp  <-- A[n] // emploi du dernier noeud pour la MàJ

                              A[1] <-- tmp  // de la racine pour assurer la complétude

                              n    <-- n-1  // la taille se réduit de 1 élément

               // Début du bloc 'ENTASSER'  (récursif ici )

 

                                             //  ...  A COMPLETER ...

 

               // Fin du bloc 'ENTASSER'                           

                              Sup_tas_max_r  <-- item  // Retourne l'élément extrait

               FSI        

FIN

 

Lexique des principales notations:

Tas:                      Type 'TasMax' en représentation contigüe (i.e.  ‘ABII’   cf.  Cours)

TypeC:                 Type Courant (ENTIER ou CARACTERE ...) de 'valeur'

item:                      noeud pour sauvegarder la racine du tas après destruction au retour à l'appelant

N_MAX:             taille maximale autorisée du Tas Max

n:                           taille effective du tas max avant et après destruction de la racine

tmp:                      noeud temporaire pour sauvegarder le dernier noeud du tas

 

 

PROGRAMMATION RECURSIVE [A FAIRE EN TPP...]

Traduire "Sup_tas_max_r" en  Java  avec l'exemple II comme jeu d'essai et trace de sortie en employant une classe 'TasMax'.

 

AUTRES PROCEDURES ET FONCTIONS:

Reprendre la version itérative de 'Insert_tas_max' et la traduire en  Java  (ou en   C++)   en employant une classe 'TasMax'.

 

 

 

SUPTAMAX.txt: SUPpression dans un TAs MAX    (c) \2A env.- Création: 1998.10.19

                                                                                     2009.10.28 / H. Nguyen-Phu

                             

                              CORRIGE PARTIEL  (Version itérative)

 

Analyse            

                              EXEMPLE III:

Considérons le Tas Max ci-dessous:

 

                                                    (90) [1]

                                                    /    \

                                       [2]   (85)   (72) [3]

                                                 /   \

                                  [4] (84)    (80) [5]

 

On adopte toujours la même notation. On note le rang des noeuds, de gauche à droite et dans l'ordre des niveaux croissants, entre crochets:  [node]; la valeur de la clé entre parenthèses: (val). Le type de (val) peut être considéré comme la valeur en code ASCII d'un CARACTERE. D'où:

               [Rang]                  1             2             3             4             5

               ('CAR')                 Z            U            H            T            P

              (val)                       90           85           72           84           80

Dans cet exemple, on doit supprimer la valeur (90 = 'Z') de la racine:

                                  [1]  (  )   ---->   90 à enlever

                                       /      \

                              [2] (85)    (72) [3]

                                   /      \

                       [4] (84)     (xx) [5]  ----> xx=80  à placer dans la racine

               (a) structure initiale du tas max

 

On place le dernier noeud (e.g. le noeud de rang 5) dans la racine (de rang 1):

                                 [1]  (80) 

                                       /    \

                            [2] (85)    (72) [3]

                                   /  

                       [4] (84)         

               (b) structure du tas max après insertion de 80 à la racine

 

Or l'arbre résultant viole la définition d'un tas. Pour rétablir le tas, on se déplace dans le tas, en comparant le noeud parent avec ses noeuds enfants et en échangeant les éléments non ordonnés jusqu'à ce que le tas soit rétabli. L'opération 'ENTASSER' peut être aussi résolue par une approche itérative.  La figure ci-contre illustre l'état final:     

 

                       [1] ( U ) 

                             /   \

                    [2] ( T ) ( H ) [3]

                          /  

                [4] ( P )

 

               (b) structure finale du tas max après tassement.

On reprend la définition de la structure de données par une représentation contigüe e.g. par un tableau de P_CART du cours. D'où l'algorithme:

 

Algorithme adopté (version itérative):

Constante MAX_ELEM= 8            /* taille maximale du tas +1 */

TYPE TypeC=     ENTIER                /* ou CARACTERE ... */

TYPE Typelt=     P_CART(             key:        TypeC,

  /* + autres champs éventuels: TypeC2 ... */                          )

TYPE TasMax= TABLEAU[1 ... MAX_ELEM] DE Typelt

n:                           ENTIER /* taille effective du tas */

                                                                          

FONCTION est_vide(D n: ENTIER): BOOLEEN

DEBUT

               SI (n = 0)              ALORS

                              RETOURNER   Vrai

               SINON  RETOURNER   Faux

               FSI

FIN

 

 

FONCTION sup_tas_max(D/R heap: TasMax, D/R  n: ENTIER): Typelt

/* déstruction de la racine c-à-d l'élément avec la plus haute clé ('key')  d'un tas max */

DEBUT

               parent, enfant:    ENTIER

               item, tmp:             Typelt

               SI (est_vide(n) = VRAI)   ALORS

                              ECRIRE('Rien à enlever: le tas est VIDE !')

               SINON

                              item <-- heap[1] // sauvegarde de la racine du tas

                              tmp  <-- heap[n] //emploi du dernier noeud pour la MàJ du tas

                              n    <-- n-1     // la taille se réduit de 1 élément

               // Début du bloc itératif 'ENTASSER_I'          

                              parent <-- 1

                              enfant <-- 2

 

                              TANTQUE (enfant <= n)

                                             SI((enfant<n) ET (heap[enfant].key<heap[enfant+1].key))

                                                            ALORS enfant <-- enfant +1

                                             // recherche du plus grand enfant du père courant

                                             FSI

                                             SI (tmp.key >= heap[enfant].key) ALORS  RUPTURE             FSI

                              // l'ordre étant rétabli, on peut quitter la boucle via RUPTURE

                              // sinon, on effectue une recherche sur le prochain niveau

                                             heap[parent] <-- heap[enfant]        // en s'éloignant de

                                             parent <-- enfant                              // la racine.

                                             enfant <-- enfant x 2 // MàJ du nouvel enfant

                              FTQUE                

                              heap[parent] <-- tmp         // MàJ finale du tas

               // Fin du bloc 'ENTASSER_I'                       

                              sup_tas_max  <-- item      // Retourne l'élément extrait

               FSI        

FIN

EXERCICE: Extraire le bloc 'ENTASSER_I' précédent pour former une procédure

--------------

 

Lexique des principales notations:

heap:                    Type 'TasMax'   (cf. Cours)

key:                       champ 'clé'           (cf. Cours)

TypeC:                 Type de la clé du noeud Courant (ENTIER ou CARACTERE ...)

Typelt:                 type du noeud courant e.g. un P_CART contenant au moins une clé ...

parent:                  indice ENTIER pour localiser le noeud 'père'

enfant:                  indice ENTIER pour localiser le noeud 'filsg'

enfant+1:             valeur de l'indice enfant ('filsg') + 1 pour localiser le noeud   'filsd'

item:                      noeud pour sauvegarder la racine du tas après destruction au retour à l'appelant

MAX_ELEM:     taille maximale autorisée du Tas Max + 1

n:                           taille du tas max avant et après destruction de la racine

tmp:                      noeud temporaire pour sauvegarder le dernier noeud du tas              

 

AUTRES PROCEDURES ET FONCTIONS [A COMPLETER pour vérifier l'algorithme]

 

 

Jeu d'essai (A TERMINER)

Reprendre l'exemple du tas max précédent. Effectuer une exécution pas à pas en explicitant toutes les valeurs des variables utilisées dans la fonction  'sup_tas_max'.

 

PARTIE PROGRAMMATION  (cf. TPP …)

1. Traduire cette version de l'opération 'ENTASSER' en Java (ou C++)  en employant   une classe 'TasMax'.

2. Ecrire et traduire en Java (ou C++)  une autre version de 'sup_tas_max' nommée 'EXTRAIRE_TAS_MAX' qui utilise 'ENTASSER' pour traiter une  file de priorité afin de gérer une imprimante commune.

3. Comparer les durées d'exécution entre les deux versions itérative  et récursive en Java (ou  C++)  [A TERMINER].