Chapitre VI. Arbres (définition, parcours, représentation)

Arbres généraux

1

Introduction

•  Les structures arborescentes jouent un rôle important dans l’organisation de données

•  - indexes des Bases de Données sont organisés sous forme des arbres afin de segmenter la mémoire et de réduire le temps d’accès aux données.

•  -dans ce chapitre nous étudions l’objet « arbre » et proposons différentes stratégies de son exploration

2

Arbres(1)

•  Un arbre peut être défini comme un ensemble des points, appelé des nœuds et un ensemble de lignes appelées des arcs, ou un arc relie deux nœuds distincts.

•  Propriétés : •  (1) Il existe un nœud particulier appelé la racine •  (2) Tout nœud c autre que racine est relié par un arc à

un autre nœud p appelé le père de c •  (3) Un arbre est qualifié de connexe car si nous

commençons à n’importe quel nœud n autre que la racine et nous nous déplaçons vers le père de n, puis vers le père du père de n et ainsi de suite, nous atteindrons certainement la racine de l’arbre.

3

Arbres Exemple

Huges Capet 939-996

Adélaïde d’Aquitaine

Robert II 970-1031

Constance de Provence

Henri Ier 1008-1060

Anne de Kiev « Jaroslavna »

Huges le Grand Philippe Ier 1053-1108

Berthe de Hollande

Robert Sans terre

4

La définition récursive des arbres

•  La base : Un nœud seul n est un arbre. On dit que n est la racine de cet arbre à un nœud

•  La récurrence : soit r un nouveau nœud et soient T1, T2, …,Tk des arbres ayant respectivement pour racines c1,c2,…,ck. Nous demandons à ce qu’aucun nœud n’apparaisse plus d’une fois dans les Ti; r étant un nouveau nœud , il ne peut pas apparaître dans un de ces arbres.

•  Nous formons un nouvel arbre T à partir de r et de T1, T2,…,Tk :

•  1. Faire de r la racine de l’arbre T •  2. Ajouter un arc entre r et chacun des c1,c2,…ck, de

manière que chacun de ces nœuds soit un fils de la racine r

5

Chemins, ancêtres et descendants(1)

•  Supposons que m1,m2,…,mk soit une séquence de nœuds telle que m1=père(m2), m2=père(m3)…mk-1=père (mk)

•  Alors m1, m2,…,mk est appelée « chemin depuis m1 jusqu’à mk » dans l’arbre

•  L=k-1 – longueur du chemin •  Illustration graphique

6

Chemins, ancêtres et descendants(2)

•  m1 est l’ancêtre de mk •  mk est descendant de m1 •  Si L(m1, .., mk)>=1 alors m1 est ancêtre propre

de mk et mk est descendant propre de m1 •  Sous-arbre : dans un arbre T un nœud n

accompagné de tous ses descendants propres (si il en possède) est appelé un sous-arbre de T.

•  Si père(ni)=père(nj), ni, nj sont appelé frères. •  Feuille : un nœud d’un arbre qui n’a pas de fils •  Nœuds intérieurs : ceux qui ont au moins un

fils 7

Mesures sur les arbres(1)

•  Le nombre de fils d’un nœud n dans un arbre est appelé le degré de n.

•  L’existence de la racine donne une orientation aux arbres

d(n)=4

8

Mesures sur les arbres (2)

•  La profondeur d’un nœud n p(n) : la longueur du chemin depuis la racine jusqu’à n

•  La hauteur d’un nœud n h(n) : la longueur du plus long chemin depuis n jusqu’à une feuille

r

h(n)=2, p(n)=2 n

9

Mesures sur les arbres (3)

•  p(r)=0 •  p(n)=p(q) +1 si q=père(n) •  La hauteur ou la profondeur d’un arbre

h(T) = max{h(n): n nœud de T}•  La longueur de cheminement

•  La longueur du cheminement externe

•  La longueur du cheminement interne

( ) ( )TNnnhTLC ∈=∑ ,)(

( ) ( ) ( ) ∅=∩∈=∑ ffilsTNffhTLCE ,)(

( ) ( ) ( ) ∅≠∩∈=∑ nfilsTNnnhTLCE ,)(10

Arbres comme structures de données

•  Arbres avec des nœuds étiquetés par des entiers 1,…,N

•  Codage par tableau « père » :taille N

1

2

3

4

56

7

8 9

1 2 3 4 5 6 7 8 9

0 9 1 5 1 1 5 4 4

11

Codage par tableau « père »

•  1. Est-feuille (n)? •  2. p(n)? •  3. h(T)?

12

Représentation des arbres avec des tableaux de pointeurs

info

info

info

info

p1 p2 pbf

pbf : facteur d’arborescence = le nombre maximal de fils que peut avoir un noeud

13

Représentation des arbres avec des tableaux de pointeurs(2)

•  Type PtrNoeud = ^Noeud Enregistrement Noeud

info : TypeInfo enfants : Tableau[1,…bf] de PtrNoeud Fin Enregistrement; Déclaration d’un arbre : MonA : PtrNoeud { pointeur vers la racine} Le temps d’accès au i-ème fils de n’importe quel nœud

en O(1). L’inconvénient : gaspillage de l’espace mémoire.

14

Représentation des arbres avec des tableaux de pointeurs(3)

•  Fils-aîné-frère-droit:

info info info

info

pour un nœud autre que la racine 15

Représentation des arbres avec des tableaux de pointeurs(4)

•  Type PtrNoeud = ^Noeud Enregistrement Noeud

info : TypeInfo fils_ainé : PtrNoeud frere_droit : PtrNoeud Fin Enregistrement;

16

Parcours des arbres (1)

•  Un arbre peut être vu comme

•  T1,…,Tk est un ensemble des arbres disjoints – « forêt »

•  Du fait qu’il y a toujours un nœud (r) un arbre n’est jamais vide

>=< TkTTrT ,....,2,1,

17

Parcours des arbres(2)

•  Procédure Parcours(A: PtrNoeud) •  Var i,nb : entiers •  Début

nb:=NbrFils(A) Si feuille(A) alors TraitementTerminal

sinon TraitementPref {traitement avant de voir les fils} Pour i de 1 à nb faire

Parcours(ième(Liste-Fils),i) Traitement(i) {*} FinPour TraitementSuf{traitement après avoir vu tous les fils} FSi FinParcours

18

Parcours des arbres(3)

•  1. L’ordre prefixe : chaque nœud n’est pris en compte que lors du premier passage: TraitementPref et TraitementTerminal sont actifs, les autres ne font rien.

•  2. L’ordre suffixe : chaque nœud n’est pris en compte que lors du dernier passage : TraitementSuff et TraitementTerminal sont actifs, les autres ne font rien.

19

Parcours des arbres(4)

•  Parcours d’un arbre général

20

Exemple(1) : Affichage de contenu d’un arbre généalogique en

parcours préfixe •  Procédure AffichePref(A: PtrNoeud) Var i,nb : entiers •  Début

nb:=NbrFils(A) Si feuille(A) alors affiche(«info + plus de

descendance ») sinon affiche(info) {TraitementPref : traitement avant de voir les fils} Pour i de 1 à nb faire

AffichePref(ième(Liste-Fils),i) FinPour Fsi FinAffichePref

21

Primitives sur les arbres

•  Type Arbre =PtrNoeud •  Type Forêt = Liste de PtrNoeud •  Signature •  Type Arbre, Forêt •  Opérations •  Cons : PtrNoeud X Forêt ->Arbre •  Racine: Arbre ->PtrNoeud •  List-arbres: Arbre ->Forêt •  Forêt-vide: ->Forêt •  Ième : Forêt X Entier->Arbre •  Nb-arbres : Forêt->Entier •  Insérer : Forêt X EntierXArbre->Forêt, •  …

22

Axiomes •  Précondition •  Insérer (F,i,A) est definie ssi •  Axiomes •  Racine(cons(o,F))=o •  List-arbres(cons(o,F))=F •  Nb-arbres(forêt-vide)=0 •  nb-

arbres(insérer(F,i,A)=nb-arbres(F)+1 •  1<k<i->ième(insérer(F,i,A),k)=ième(F,k) •  K=i->ième(insérer(F,i,A),k)=A •  i+1<k<1+nb-arbres(F)-> •  ième(insérer(F,i,A),k)=ième(F,k-1) {décalage}

)(11 Farbresnbi −+≤≤

⇒−+≤≤ )(11 Farbresnbi

23

Mise en œuvre des primitives

•  Représentation avec les tableau des pointeurs •  Type PtrNoeud = ^Noeud

Enregistrement Noeud info : TypeInfo

enfants : Tableau[1,…bf] de PtrNoeud Fin Enregistrement; Primitive Insérer : Forêt X Entier X Arbre->Forêt Procedure Inserer (ref EnfantsDuNoeud : Tableau [1…bf] de PtrNoeud, i:entier, A : PtrNoeud) Debut Var j:entier Si i>0 et i<bf+1 alors Pour j de i à bf-1

EnfantsDuNoeud[j+1]:=EnfantsDuNoeud[j]; FPour { j pointe sur la première case vide du tableau des pointeurs} EnfantsDuNoeud[i]=A; Fin-Si FinInserer

24

Exemple(2)

•  Supposons arbre généalogique avec l’ordre de la descendance selon primarité

•  Ecrire la procédure d’ajout du fils cadet au dernier représentant de la lignée principale

25

•  Type PtrNoeud = ^Noeud Enregistrement Noeud

info : TypeInfo enfants : Tableau[1,…bf] de PtrNoeud Fin Enregistrement; Procedure AjoutLePlusJeuneLD(Agen : PtrNoeud, FilsCadet : PtrNoeud) Début {Arbre n’est jamais vidé !} Si Agen.^enfants[1]=NIL { Base de récursivité 1 – le dernier descendant de la LD n’a pas de fils} alors

Insérer(Agen.^enfants,1,FilsCadet) sinon {Agen.^enfants[1]<>NIL} Si Agen.^enfants[1].^enfants[1]=NIL {Base de récursivité 2- le dernier descendant de la

LD a des fils} alors

j=1 TQ(j<nbf et Agen.^enfants[j]<>NIL) j:=j+1; FTQ Si (j<nbf) alors { Test de capacité du mémoire réservé} Insérer(Agen.^enfants,j,FilsCadet) FSi sinon AjoutLePlusJeuneL(Agen.^enfants[1],FilsCadet) FSi

FSi FinAjoutLePLusJeuneLD 26

Mise en œuvre des primitives

•  Fils-aîné-frère droit

•  Fonction ième(NFA: PtrNoeud, FD: PtrNoeud, i: entier):PtrNoeud •  Var k : entier •  ptr : PtrNoeud •  Debut •  Si i=1 alors retourner NFA

sinon ptr:=FD; k:=3; Tq ptr<>NIL et k<i faire ptr:=ptr.FD; k++; Ftq FSi Retourner ptr; Fin ième

info

info

info

info

NFA

27