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

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

Previous PDF

Next PDF

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) SINONquotesdbs_dbs46.pdfusesText_46

[PDF] Les arbres et la neige

[PDF] les arbres rouges de maurice vlaminck

[PDF] les arenes de nimes

[PDF] les arguments de créon pour convaincre antigone

[PDF] les arguments de la dérive des continents

[PDF] lES ARGUMENTS DE WEGENER

[PDF] Les arguments envers les Incas-Espagnols

[PDF] les arguments et les exemples

[PDF] Les arméniens pendant la 1ere Guerre Mondiale

[PDF] Les Armes sont-elles nécessaire

[PDF] Les arrondis au centième et millimètre près

[PDF] les articles en espagnol pdf

[PDF] Les articles indefinis

[PDF] Les artificiers DM

[PDF] les artificiers sont cachés du public par un mur de hauteur 2m