[PDF] INF601 : Algorithme et Structure de données - Cours 2 : TDA

Algorithmique et structure de données 2

Faculté des Mathématiques et de l’informatique Département d’informatique Algorithmique et structure de données 2 Chapitre 1 : Les sous-programmes : Fonctions et Procédures Cours Conçu par Dr Omar TALBI Version 1 0 2019-2020 Public concerné: -Etudiants 1ère LMD –MI Année universitaire 2019-2020

INF601 : Algorithme et Structure de données - Cours 2 : TDA

INF601 : Algorithme et Structure de données Recherche ParcoursenLargueur ParcoursEnLargeur(ARBIN A) Début créer une file vide F SIA est non videALORS Enfiler A dans F TQF non videFRE A < Défiler(F) traitement(A) SIABG de A non videALORS Enfiler ABG de A dans F FSI SIABD de A non videALORS Enfiler ABD de A dans F FSI FTQ FSI détruire F Fin

Algorithmique et Structures de Données 2

2 1 3 L'algorithme de Kruskal 2 1 4 L'algorithme de Prim 2 2 Plus courts chemins à origine unique Le problème consiste dans un graphe G(S;A;w), à trouver pour chaque sommet s2S, le chemin de poids minimal entre un sommet r2Set x Problème similaire au précédent Il existe d'autres problèmes similaires : 11

STRUCTURES DE DONNEES ET ALGORITHMES

3 6 la structure de tableau 46 3 7 la structure de record 48 3 8 la structure de suite 51 chapitre 4 : structures de donnÉes dynamiques 53 4 1 types de donnees recursifs 53 4 2 pointeurs 55 4 3 listes lineaires 57 chapitre 5 : structures de donnees elaborees 62 5 1 type abstrait et structure de donnee 62 5 2 structures lineaires 63

Algorithmique Structures de données

2 de 87 Typesdedonnées Retenir Avoirchoisilesbonstypesdedonnéespermetd’avoirun programme pluslisiblecarautodocumenté plusfacileàmaintenir souventplusrapide

Algorithmique et Structures de Données

Dans le premier chapitre, des notions de base sur la structure globale d’un algorithme sont données, ainsi que les différentes parties qui le composent suivie par les instructions de base les plus élémentaires Le deuxième chapitre décrit en détails les différentes structures de contrôles ( boucles ) qui

COURS DE STRUCTURES DE DONNÉES LICENCE 2 - UNIVERSITÉ CLERMONT 2

COURS DE STRUCTURES DE DONNÉES LICENCE 2 - UNIVERSITÉ CLERMONT 2 MAMADOU MOUSTAPHA KANTÉ Table des matières 1 Niveau de Description 2 1 1 Structure Générale d’un Ordinateur 2 1 2 Mémoire Centrale 3 1 3 Langages 3 2 Algorithmes, Valeurs, Types et Éléments du Langage 4 2 1 Données 5 2 2 Tableaux statiques 5 2 3 La Syntaxe du

Algorithmes et structures de données

[PDF] algorithme et structure de données exercices corrigés pdf PDF Cours,Exercices ,Examens

[PDF] algorithme et structure de données pdf PDF Cours,Exercices ,Examens

[PDF] algorithme et suite à faire mais difficile pour moi à comprendre merci de votre Terminale Mathématiques

[PDF] algorithme et suite math 1ère Mathématiques

[PDF] Algorithme et valeur de x 2nde Mathématiques

[PDF] Algorithme et vecteurs 2nde Mathématiques

[PDF] algorithme euclide 3eme 3ème Mathématiques

[PDF] algorithme exemple PDF Cours,Exercices ,Examens

[PDF] algorithme exercice DM 2nde Mathématiques

[PDF] algorithme exercice et solution PDF Cours,Exercices ,Examens

[PDF] ALgorithme exercice long 2nde Mathématiques

[PDF] Algorithme exercice seconde 2nde Mathématiques

[PDF] algorithme exercices corrigés pdf PDF Cours,Exercices ,Examens

[PDF] algorithme exo long 2nde Mathématiques

[PDF] algorithme fibonacci PDF Cours,Exercices ,Examens

INF601 : Algorithme et Structure de données

Cours 2 : TDA Arbre Binaire

B. Jacob

IC2/LIUM

27 février 2010

INF601 : Algorithme et Structure de données

Plan

1Introduction

2Primitives du TDA Arbin

3Réalisations du TDA Arbin

par cellules chaînées par cellules contiguës par curseurs (faux pointeurs)

Réalisation des Arbres parfaits

4Recherche d"un élément

5Adjonction d"un élément

Adjonction aux feuilles

Adjonction à la racine

6Suppression d"un élément

7Conclusion sur les arbres

INF601 : Algorithme et Structure de données

IntroductionPlan

1Introduction

INF601 : Algorithme et Structure de données

IntroductionMéthodes arborescentes

Cours précédent

si ensemble d"éléments sont dans un TDA Liste triée

!recherche d"un élément enlog(n)comparaisonsProblème: rep résentationcontiguë (liste) mal adaptée lo rsque

l"ensemble évolue dynamiquement !adjonction et suppression peuvent être enO(n)Solution: p ourque les 3 op érations recherche adjonction suppression soient efficaces!structures arborescentes

INF601 : Algorithme et Structure de données

IntroductionMéthodes arborescentes

Elles reposent sur

1une comparaison avec la valeur d"un noeud

2"l"aiguillage" de la poursuite de la recherche dans un

sous-arbre en fonction du résultat de la comparaison La structure fondamentale des méthodes arborescentes !celle de l"arbre binaire de recherche

INF601 : Algorithme et Structure de données

IntroductionDéfinitions informelle

Définition informelle

un arbre = ensemble de sommets tel que :

9un sommet unique appelé racinerqui n"a pas de supérieurTous les autres sommets sont atteints à partir derpar une

branche uniqueDéfinition récursive (et constructive) un arbre = une racinerune liste d"arbres disjointsA1;:::;An(sous-arbres) Un sommet de l"arbre est la racine d"un sous-arbre

INF601 : Algorithme et Structure de données

IntroductionTerminologie

père d"un sommet : le p rédécesseurd"un sommet fils d"un sommet : les successeurs d"un sommet frères : des sommets qui ont le même p ère noeud = sommet racine : no eudsans p ère feuille : no eudsans fils branche : chemin entre 2 no euds

INF601 : Algorithme et Structure de données

IntroductionMesures sur les arbres

Niveau (profondeur) d"un noeud

: la longueur de la b ranche depuis la racineHauteur d"un noeud: la longueur de la plus longue b ranchede ce noeud jusqu"à une feuilleHauteur d"un arbre: la hauteur de la racine

Taille d"un arbre

: nomb rede s essommets

INF601 : Algorithme et Structure de données

IntroductionArbres Binaires

Définition informelle

Dans un arbre binaire tout noeud a au plus deux fils Un arbre binaire possède exactement deux sous-arbres (éventuellement vides)Définition récursive (et constructive)

Un arbre binaire est

Soit vide

Soit composé

d"une racinerde 2 sous arbres binaires ABG et ABD disjoints

ABG : sous Arbre Binaire Gauche

ABD : sous Arbre Binaire Droit

INF601 : Algorithme et Structure de données

IntroductionEléments dans un arbre binaire

Généralement dans un arbre binaire

noeud racine contient un élémentXdans ABG!noeudsXdans ABD!noeuds>XracineX sous-arbre Droit X sous-arbre

Gauche

X

INF601 : Algorithme et Structure de données

IntroductionOrganisation d"un arbre binaireabcdegf

INF601 : Algorithme et Structure de données

IntroductionOrganisation d"un arbre binaireabcdegfracinesous arbre Gauchesous arbre Droit

INF601 : Algorithme et Structure de données

IntroductionOrganisation d"un arbre binaireabcdegfracineracineABGABGABDABD

INF601 : Algorithme et Structure de données

IntroductionArbres binaires particuliers

Arbre binaire dégénéré, filiforme

: Chaque no eudp ossède exactement un fils !à éviterArbre binaire complet (uniforme): Chaque niveau est complètement rempli I.E. Tout sommet est soit une feuille au dernier niveau, soit possède exactement 2 fils !situation idéaleArbre binaire parfait (presque complet): T ousles niveaux sont complètement remplis sauf éventuellement le dernier et dans

ce cas les feuilles sont le plus à gauche possibleArbre binaire équilibré: La différence de hauteur entre 2 frères

ne peut dépasser 1

INF601 : Algorithme et Structure de données

IntroductionArbres particuliers

Arbre Parfait!situation idéalewylbcdefutvagzx

INF601 : Algorithme et Structure de données

IntroductionArbres particuliers

Arbre dégénéré!Pire des situationswylz

INF601 : Algorithme et Structure de données

IntroductionArbres particuliers

Arbre presque parfaitwylbcdefuag

INF601 : Algorithme et Structure de données

IntroductionArbres particuliers

Arbre équilibréwylzxbcdefu

INF601 : Algorithme et Structure de données

PrimitivesPlan

2Primitives du TDA Arbin

INF601 : Algorithme et Structure de données

PrimitivesDéfinitions des primitives

Utilise le TDA ELEMENT

Primitives :Création et destruction

Construction

Primitives de modification d"un arbre non vide

Accès aux caractéristiques des noeuds (aux éléments)

INF601 : Algorithme et Structure de données

RéalisationPlan

3Réalisations du TDA Arbin

par cellules chaînées par cellules contiguës par curseurs (faux pointeurs)

Réalisation des Arbres parfaits

INF601 : Algorithme et Structure de données

Réalisation

par cellules chaînéesPlan

3Réalisations du TDA Arbin

par cellules chaînées par cellules contiguës par curseurs (faux pointeurs)

Réalisation des Arbres parfaits

INF601 : Algorithme et Structure de données

Réalisation

par cellules chaînéesPointeurs sur ABG et ABD Un a rbre binaire est soit un pointeur sur le noeud racine (arbre non vide) le pointeur NULL (arbre vide) Un no eud est une structure à trois champs : Une étiquette (élément) le sous-arbre gauche le sous-arbre droit

Avantages

: Définition récursive, simple à programmer, la plus utilisée

Inconvénients

: consomme de la mémoire dynamique

INF601 : Algorithme et Structure de données

Réalisation

par cellules chaînéesTraduction en C /Definition d "un noeud/ typedef structnoeud {

ELEMENT etiq ;/Etiquette/

structnoeudag ,/ABG/ ad ;/ABD/ } NOEUD; /Definition d "un arbre = un pointeur sur son Noeud racine/ typedefNOEUDARBIN ; /l " arbre vide est le pointeur null/ #defineARBRE_VIDE NULL

INF601 : Algorithme et Structure de données

Réalisation

par cellules chaînéesSchéma réalisation par pointeursacbdfARBINNOEUDetiqadagNULL

INF601 : Algorithme et Structure de données

Réalisation

par cellules contiguësPlan

3Réalisations du TDA Arbin

par cellules chaînées par cellules contiguës par curseurs (faux pointeurs)

Réalisation des Arbres parfaits

INF601 : Algorithme et Structure de données

Réalisation

par cellules contiguësPar tableau Un a rbre est une structure à deux champs :

Un tableau où sont mémorisés les noeuds

Un entier qui donne l"indice de la racine dans le tableau Un no eud est une structure à 3 champs : L"étiquette du noeud Les indices de ses fils gauche et droit (ou 0 si pas de fils)

Inconvénients

: Définition non récursive (arbre6=sous-arbre)Utilisée uniquement si on traite un arbre unique

INF601 : Algorithme et Structure de données

Réalisation

par cellules contiguësTraduction en C /Definition d "un noeud/ typedef structnoeud {

ELEMENT etiq ;/Etiquette/

intfg ,/ABG/ fd ;/ABD/ } NOEUD; /Definition d "un arbre/ typedef struct{

NOEUD tab [TAILLE_MAX] ;

intracine ; } rep ; typedefrepARBIN ;

INF601 : Algorithme et Structure de données

Réalisation

par cellules contiguësSchéma réalisation par tableauabcdftabracine

1234567842623000000

ARBINetiqfdfg

INF601 : Algorithme et Structure de données

Réalisation

par curseurs (faux pointeurs)Plan

3Réalisations du TDA Arbin

par cellules chaînées par cellules contiguës par curseurs (faux pointeurs)

Réalisation des Arbres parfaits

INF601 : Algorithme et Structure de données

Réalisation

par curseurs (faux pointeurs)Simulation pointeurs sur ABG et ABD (même principe que les faux pointeurs dans le TDA Liste) Simulation de la mémoire : les noeuds sont dans un tableau en variable globaleUn arbre = indice de la racine (0 si vide)

Un noeud est une structure à 3 champs

l"étiquette du noeud indice fils ABG (0 si vide) indice fils ABD (0 si vide)

2 stratégies de gestion des cellules disponibles

1Chaîner entre elles les cellules disponibles

2Marquer les cellules libres et parcourir le tableau pour trouver

la 1re place libre

INF601 : Algorithme et Structure de données

Réalisation

par curseurs (faux pointeurs)Schéma réalisation par faux pointeurs12345678

MémoireA1A2abcdijk

0002300040006817

ARBINARBIN

INF601 : Algorithme et Structure de données

Réalisation

Réalisation des Arbres parfaitsPlan

3Réalisations du TDA Arbin

par cellules chaînées par cellules contiguës par curseurs (faux pointeurs)

Réalisation des Arbres parfaits

INF601 : Algorithme et Structure de données

Réalisation

Réalisation des Arbres parfaitsCas particuliers des arbre parfaits Solution efficace (accès + place mémoire) de réalisation d"un arbre parfaitAdeNétiquettes !un tableau avec :1 : indice de la racine deAT[i] étiquette du père

T[2i] étiquette du fils gauche

T[2i+1] étiquette du fils droit

Attention

: inefficace si N"loin de"n2(siAn"est pas parfait)

INF601 : Algorithme et Structure de données

Réalisation

Réalisation des Arbres parfaitsSchéma Arbre parfait avec tableau SiAest l"abre parfait suivant :abcdegfAlors la réalisation deAest le tableau :dbfcaef

01234567

INF601 : Algorithme et Structure de données

RecherchePlan

4Recherche d"un élément

INF601 : Algorithme et Structure de données

RechercheParcours d"arbres binaires

Recherche d"un élément!parcours d"un arbre

Plusieurs types de parcours (selon application)Parcours en profondeur à main gauche (le + utilisé)

Parcours récursif général

Parcours particuliers (parcours préfixe, infixe, postfixe)

Parcours en largeur (par niveaux)

INF601 : Algorithme et Structure de données

RechercheRecherche en profondeur à main gauche

chemin qui descend toujours le plus à gauche possible dans ce parcours chaque noeud est rencontré 3 fois 1 ierefois: à la descente à gauche dan sABG !on applique au noeud letraitement 1 2 iemefois: quan dABG a été pa rcouru,remontée pa rla gauche descente à gauche dans ABD !on applique au noeud letraitement 2 3 iemeet dernière fois: quand ABG et ABD ont été pa rcourus, en remontant à droite !on applique au noeud letraitement 3 si l"arbre estvide on lui applique un traitement app elé terminaison

INF601 : Algorithme et Structure de données

RechercheRécursif à main gauche

Parcours (ARBIN A)

Début

SI

A e stv ide

A LORS

terminaison (A) SINON traitement1 (A)

Parcours ( sousarbreGauche (A))

traitement2 (A)

Parcours ( sousarbreDroit (A))

traitement3 (A) FSI Fin

INF601 : Algorithme et Structure de données

RechercheCas particuliers

Lorsque le noeud est traité une seule fois

Parcours préfixe

(Racine Gauche Droit) !le noeud racine est traité au premier passage avant le parcours des sous-arbresParcours infixeou symétrique (Gauche Racine Droit) !le noeud racine est traité au second passage après le parcours du sous-arbre gauche et avant le parcours du sous-arbre droitParcours postfixe(Gauche Droit Racine ) !le noeud racine est traité au dernier passage après le parcours des sous-arbres

INF601 : Algorithme et Structure de données

RechercheParcours particuliers

Parcours préfixé R G D

!le noeud racine est traité au premier passage avant le parcours des sous-arbres

Parcours (ARBIN A)

Début

SI

A e stv ide

A LORS

terminaison (A) SINON traitement (A)

Parcours (ABG de A)

Parcours (ABD de A)

FSI Fin

INF601 : Algorithme et Structure de données

RechercheParcours particuliers

Parcours symétrique G R D

!le noeud racine est traité au second passage après le parcours du sous-arbre gauche et avant le parcours du sous-arbre droit

Parcours (ARBIN A)

Début

SI

A e stv ide

A LORS

terminaison (A) SINON

Parcours (ABG de A)

traitement (A)

Parcours (ABD de A)

FSI Fin

INF601 : Algorithme et Structure de données

RechercheParcours particuliers

Parcours postfixé G D R

!le noeud racine est traité au troisième passage après le parcours des sous-arbres gauche et droit

Parcours (ARBIN A)

Début

SI

A e stv ide

A LORS

terminaison (A) SINON

Parcours (ABG de A)

Parcours (ABD de A)

traitement (A) FSI Fin

INF601 : Algorithme et Structure de données

RechercheParcours en Largueur

ParcoursEnLargeur (ARBIN A)

Début

créer une f i l e vide F SI

A e stn onv ide

A LORS

Enfiler A dans F

TQ

F n onv ide

F RE

A traitement (A) SI

A BGd eA n onv ide

A LORS

Enfiler ABG de A dans F

FSI SI

A BDd eA n onv ide

A LORS

Enfiler ABD de A dans F

FSI FTQ FSI détruire F Fin

INF601 : Algorithme et Structure de données

AdjonctionPlan

5Adjonction d"un élément

Adjonction aux feuilles

Adjonction à la racine

INF601 : Algorithme et Structure de données

AdjonctionConstruction d"un arbre

Un arbreAse construit par adjonction successives d"élémentsx

2 méthodes principales :Adjonction aux feuilles :

!ajout de chaquexà une feuille deA !construction "sur place"Adjonction à la racine : !xdevient la nouvelle racine deA !construction "à côté"

INF601 : Algorithme et Structure de données

AdjonctionPréparation

On transforme ELEMENTxen noeud de l"ArbreX

Soit ARBINX:valeur de X xsous arbre gauche de X videsous arbre droit de X vide

INF601 : Algorithme et Structure de données

AdjonctionInsertion à une feuille

ARBIN ArbinAjouterFeuille ( ARBIN A ,ARBIN X)

Début

SI

A e stv ide

A LORS

A X < =A

A LORS

renvoyer ArbinAjouterFeuille ( ABG(A) ,X) SINON renvoyer ArbinAjouterFeuille ( ABD(A) ,X) FSI FSI Fin

INF601 : Algorithme et Structure de données

AdjonctionInsertion à la racine

Ajout à la racine

!ajout à n"importe quel niveau deA !à rapprocher des méthodes auto-adaptatives des listes Méthode pour ajouterXdansA:1CouperAen 2 ARBINGetD

Gcontient tous les éléments deAX

Dcontient tous les éléments deA>X2Former un nouvel ARBINA0dont la racine avec :étiquette de A" XABG(A") GABD(A") D

INF601 : Algorithme et Structure de données

AdjonctionMéthode de coupure

Coupure d"un ELEMENT X dans un ARBIN A en 2 ARBIN G et D Il n"est pas nécessaire de parcourir TOUS les noeuds deA !seulement les noeudsNsitués sur le chemin de recherche deXdansAsi noeudNX:G N+ABG(N) sur le bord droit deGsi noeudN>X:D N+ABD(N) sur le bord gauche deD

INF601 : Algorithme et Structure de données

AdjonctionExemple de coupurealdegfqtiGD

INF601 : Algorithme et Structure de données

AdjonctionExemple de coupurealdegfqtiGD

INF601 : Algorithme et Structure de données

AdjonctionExemple de coupurealdegfqtiGD

INF601 : Algorithme et Structure de données

AdjonctionExemple de coupurealdegfqtiGDqt

INF601 : Algorithme et Structure de données

AdjonctionExemple de coupurealdegfqtiGDqt>=XN

INF601 : Algorithme et Structure de données

AdjonctionExemple de coupurealdegfqtiGDqt

INF601 : Algorithme et Structure de données

AdjonctionExemple de coupurealdegfqtiGDqtad

INF601 : Algorithme et Structure de données

AdjonctionExemple de coupurealdegfqtiGDqtad

INF601 : Algorithme et Structure de données

AdjonctionExemple de coupurealdegfqtiGDqtad

INF601 : Algorithme et Structure de données

AdjonctionExemple de coupurealdegfqtiGDqtadli

INF601 : Algorithme et Structure de données

AdjonctionExemple de coupurealdegfqtiGDqtadli>=XN

INF601 : Algorithme et Structure de données

AdjonctionExemple de coupurealdegfqtiGDqtadli

INF601 : Algorithme et Structure de données

AdjonctionExemple de coupurealdegfqtiGDqtadlie

INF601 : Algorithme et Structure de données

quotesdbs_dbs5.pdfusesText_10