Upload
adalard-crouzet
View
116
Download
6
Embed Size (px)
Citation preview
Françoise Greffier - IUP GMI - Besançon
LES ARBRES
IUP 2 Génie Informatique
Méthode et Outils pour la Programmation
Françoise Greffier
Françoise Greffier - IUP GMI - Besançon
Définitions et généralités sur les arbres
Arbre binaire
Arbre binaire de recherche (ABR)
Arbre rouge noir
Arbre 2-3
LES ARBRES
Françoise Greffier - IUP GMI - Besançon
EXEMPLES
un graphe
b
an
i r
e
z
un arbre
Un arbre est un graphe - non orienté- connexe : mise à part la racine de l ’arbre, tout nœud possède un père- acyclique : ne comporte pas de cycle
: nœud
racineb
an
i r
e
z
Françoise Greffier - IUP GMI - Besançon
EXEMPLES
(livre(C1((C1.1),(C1.2),(C1.3))),(C2),(C3 ((C3.1),(C3.2))))
livre
C1.2
C1 C2 C3
C1.1 C1.3 C3.2C3.1
table des matières d ’un livre
arbre généalogique d ’une famille
Arbre non vide :: (racine (fils1, fils2, …,filsN))
Françoise Greffier - IUP GMI - Besançon
Arbres : propriétés
Il existe un chemin unique entre la racine de l ’arbre et chaque sommet.
b
an
i r
e
z
: nœud
Un des nœuds de l’arbre est particulieril n ’a pas de père : c’est la racine de l’arbre
racine
Un arbre comprend un nombre fini de sommets (appelés aussi nœud).
Françoise Greffier - IUP GMI - Besançon
Arbres : définitions
Le sous-arbre de racine i est l’arbre composé des descendants de i, enraciné en iOn appelle aussi ce sous-arbre : fils de b
i est le père de n et de an est un descendant de ii est un ascendant de a
b
an
i r
e
z
: nœud
racine
==> algorithmes récursifs
Françoise Greffier - IUP GMI - Besançon
Arbres : définitions
Un nœud sans fils est un nœud externe ou une feuille.Exemples : n,a,e
b
an
i r
e
z
: nœud
racine
Un nœud qui n ’est pas une feuille est un nœud interne.Exemples : b,i,r
Le nombre de fils d ’un nœud x est appelé degré de x.Lorsque chaque nœud doit avoir au plus n fils (n fixé) alors l ’arbre est n-aire.Exemple : si n=2, l’arbre est binaire.
Françoise Greffier - IUP GMI - Besançon
Arbres : profondeur
La profondeur ou niveau d ’un nœud est le nombre de liens sur l ’unique chemin qui conduit de la racine à ce nœud.
b
an
i r
e
z
: nœud
Profondeur 0
Profondeur 1
Profondeur 2
Deux nœuds frères ont la même profondeur.
N étant un nœud de l’arbre :- ou N est racine => niveau=0- ou niveau (N)= niveau (père(N))+1
Françoise Greffier - IUP GMI - Besançon
Arbres : hauteur
La hauteur d ’un arbre est égale au niveau maximum de ses feuilles +1.
b
an
i r
e
z
: nœud
Hauteur = 3
Un arbre est équilibré si pour tout nœud, la valeur absolue de son facteur d ’équilibre est inférieure ou égale à 1.
Facteur d’équilibre d’un nœud dans un arbre binaire =hauteur (sous-arbre droit) - hauteur (sous-arbre gauche)
Françoise Greffier - IUP GMI - Besançon
Arbres : facteur d’équilibre
b
an
i r
e
z
Hauteur = 3 Un arbre est équilibré si pour tout nœud, la valeur absolue de son facteur d ’équilibre est inférieure ou égale à 1.Facteur d ’équilibre d’un nœud dans un arbre de degré deux :hauteur (sous-arbre droit) - hauteur (sous-arbre gauche)
Un arbre est dégénéré si tous les nœuds de cet arbre ont au plus un descendant.
Un arbre dégénéré est équivalent à une liste linéaire
Françoise Greffier - IUP GMI - Besançon
Arbre complet
Un arbre complet est un arbre d’arité k pour lequel toutes les feuilles ont même profondeur (h) et tous les nœuds ont pour degré k. Exemple : k=2 et h = 3.=> nombre de feuilles d ’un arbre complet = kh-1 / k-1
b
an
i r
e z
Un arbre complet
Nombre de nœuds (taille) dans un arbre binaire complet : N = 2H-1
Hauteur H d ’un arbre binaire completayant N nœuds : H = Log2(N)+1
Françoise Greffier - IUP GMI - Besançon
Arbre binaire
b
an
i r
e
t
r
y
gauche
f
droit
Dans un arbre binaire chaque nœuda un degré inférieur ou égal à deux. L ’information de position : gauche, droitcaractérise un arbre binaire.
+
ba
- 4
gauche droit+
ab
- 4
gauche droit
(a-b)+4 (b-a)+4
==
Françoise Greffier - IUP GMI - Besançon
Arbre binaire : définition
Un arbre binaire est un arbre dans lequel chaque nœud a un sous-arbre droit (fils droit) et un sous-arbre gauche (fils gauche).(Un sous-arbres peut-être éventuellement vide)
Définition récursive d’un arbre binaire :Un arbre binaire est :- soit vide- soit (sous-arbre gauche, racine, sous-arbre droit)
b
an
i r
e
t
r
y
gauche
f
droit
Un ABR est défini par : nœud<X>* PtrUn nœud est défini par :
nœud<X>* gauche;nœud<X>* droit;X valeur;
Françoise Greffier - IUP GMI - Besançon
Arbre binaire de recherche (ABR)
Un arbre binaire de recherche (ABR) ordonne totalement les informations qu’il stocke(par clé) :Toutes les clés des valeurs inférieures ou égales à celle de la racine sont stockées dans le descendant gauche de la racine
Toutes les clés des valeurs strictement supérieures à celle de la racine sont stockées dans le descendant droit de la racine
Propriété caractéristique des ABR:Pour chaque nœud n de l’arbre : (1) n.arbreGauche.maxVal<=n.val<n.arbreDroit.minVal
34
3020
23 5O
45
gauche
48
droit
29
Françoise Greffier - IUP GMI - Besançon
Arbre binaire de recherche
ConditionsLa classe Valeur doit disposer d’une fonction de comparaison sur les clésTout ajout, toute suppression de nœud doit maintenir la propriété (1) vraie
Exemple : ajouter la valeur 49 : 49
Remarque :Tout ajout se fait par une feuille.
49
34
3020
23 5O
45
gauche
48
droit
29
Exemple : ajouter la valeur 24 2424
Françoise Greffier - IUP GMI - Besançon
ABR : suppression
une feuille : trivial48
Analyse : l ’algorithme de suppression d ’un nœud présente 3 cas :
34
3020
23 5O
45
gauche
48
droit
29 48
34
3020
23 5O
45
29
Françoise Greffier - IUP GMI - Besançon
ABR : suppression
un nœud simple : on le remplace par son unique fils
50
Deuxième cas de nœud à supprimer34
3020
23 5O
45
gauche
48
droit
29
50
34
3020
23
48
29
45
Françoise Greffier - IUP GMI - Besançon
ABR : suppression
23 un nœud double : on lui donne la valeur minimale de son sous-arbre droit (ex: 29), et on supprime le nœud qui a cette valeur
Troisième cas de nœud à supprimer34
3020
23 5O
45
gauche
48
droit
29
23
5O
34
3020 45
48
29
Françoise Greffier - IUP GMI - Besançon
Parcours dans un ABR
template <class X>class ABR { ...void infixe (void);// les valeurs de IC sont éditées par ordre // croissant sur les clés...}
si (non vide) alorsinfixe du sous-arbre gauchecout << valeur de la racineinfixe du sous-arbre droit
fsi
Parcours infixé:GaucheRacineDroit
Françoise Greffier - IUP GMI - Besançon
3 types de parcours : infixés
Gauche, Racine, DroiteDroite, Racine, Gauche
préfixé Racine, Gauche, Droite Racine, Droite, Gauche
postfixés Gauche, Droite, Racine,Droite, Gauche, Racine
34
3020
23 5O
45
gauche
48
droit
29
Parcours dans un ABR
Françoise Greffier - IUP GMI - Besançon
ABR et algorithmique
Les arbres binaires de recherche présentent deux avantages : • tri efficace car les valeurs sont maintenues ordonnées• recherche efficace par dichotomie
template <class X>class ABR { ...bool rechercher (const X& E);// est retourné : vrai si E est dans ABR, faux sinon
...}
Françoise Greffier - IUP GMI - Besançon
ABR : recherche dichotomique
bool rechercher (const X& E);// est retourné : vrai si E est dans ABR, faux sinon
si vide => retourner fauxsinon si (E = valeur racine) => retourner vrai sinon si (E<valeur racine) => retourner rechercher dans sous-arbre gauche sinon retourner rechercher dans sous-arbre droit fsi fsifsi
Si N est le nombre de nœuds et si l ’ABR est équilibré alorsla complexité de l ’algorithme de recherche dichotomiqueest de l ’ordre de Log 2 (N).Exemple : N=1024 => complexité ~ 10
Françoise Greffier - IUP GMI - Besançon
Conclusions ABR (algorithmique)
Les arbres binaires de recherche sont des structures de données efficaces pour implanter des suites ordonnées dynamiques.Les opérations associées sont:RECHERCHER, MINIMUM,MAXIMUM,SUCCESSEUR, PREDECESSEUR , INSERER et SUPPRIMER . Pour un ABR complet, les opérations de base sur les arbres binaires de recherche ont une complexité de l ’ordre de Log2(N), N étant le nombre de nœuds.Cependant, quand l’arbre est dégénéré : s ’il se réduit par exempleà une liste linéaire chaînée alors les opérations ont une complexitéde l ’ordre de (N).Pour garantir de bonnes performances, il existe une variante des ABR : les arbres rouge et noir.
Françoise Greffier - IUP GMI - Besançon
Un arbre rouge et noir est un arbre binaire de recherche comprenant une donnée supplémentaire par nœud définissant sa couleur : rouge ou noir.
Arbre rouge et noir
En contrôlant les manières dont sont colorés les nœuds on garantit que tout chemin menant de la racine à une feuille n ’est pas plus de deux fois plus long qu’un autre.
Ainsi, un arbre rouge et noir est un arbre binaire de recherche approximativement équilibré.
Françoise Greffier - IUP GMI - Besançon
Dans un arbre rouge et noir : Chaque nœud est soit rouge, soit noirSi un nœud est rouge alors ses deux nœuds fils sont noirsChaque chemin reliant un nœud à une feuille descendante a le même nombre de nœuds noirs.
Arbre rouge et noir : propriétés
26
17 41
30
3819
14 21
26 28
47
11 16
Françoise Greffier - IUP GMI - Besançon
On montre que dans un arbre rouge et noir comportant N nœuds, les opérations rechercher, minimum, maximum
ont une complexité de l’ordre de Log2(N).
Arbre rouge et noir : complexité
En contrôlant les manières dont les nœuds sont colorés on garantit que tout chemin menant de la racine à une feuille n’est pas plus de deux fois plus long qu’un autre.
Un arbre rouge et noir comportant N nœuds a une hauteur au plus égale à : 2 Log2(N+1). H <= 2 Log2(N+1).
Françoise Greffier - IUP GMI - Besançon
Arbre rouge et noir : opérations
Par rapport aux ABR, les opérations : RECHERCHER, MINIMUM, MAXIMUM,SUCCESSEUR et PREDECESSEUR sont inchangées dans un arbre rouge et noir
Par rapport aux ABR, les opérations : INSERER et SUPPRIMER ne sont pas directement supportées dans un arbre rouge et noir
Françoise Greffier - IUP GMI - Besançon
Dans un arbre rouge et noir : Les opérations INSERER et SUPPRIMER modifient l ’arbre. Aussi, pour garantir les propriétés des arbres rouge et noir, il faut changer les couleurs de certains nœuds et changer aussi les chaînages par pointeurs.
On modifie ces chaînages par rotations.
Arbre rouge et noir : insérer/sup
Françoise Greffier - IUP GMI - Besançon
On insère un nœud 4 que l ’on colore au départ en rouge
11
2 14
5
1 7
8
15
4
4
Couleur (x) <- rougeTant que (x<>racine) et (p[x] est rouge) faire si (p[x] = gauche p[p[x]]) alors
y <- droit p[p[x]]si (couleur (y) = rouge) alors //cas 1
couleur (p[x] )<- noircouleur (y) <- noir couleur (p[p[x]] )<- rouge
58
7x<- p[p[x]] //on itère le traitement
… // traitement symétrique à droiteFin tant quecouleur (racine) <- noir
5
7
8
4
x
Arbre rouge et noir : INSERER - cas 1(père de x et oncle de x sont rouges)
Françoise Greffier - IUP GMI - Besançon
Arbre rouge et noir : INSERER - cas 2(x est fils droit et oncle droit noir)
Couleur (x) <- rougeTant que (x<>racine) et (p[x] est rouge) faire si (p[x] = gauche p[p[x]]) alors
y <- droit p[p[x]] //oncle droit si (couleur (y) = rouge) alors // cas 1 (diapo précédente) sinon // cas 2
si (x=droit(p[x] )) alorsx
11
7 14
5
8 152
1
4On fait une rotation pour amenerla situation au cas 3
x <- p[x] // x =2
Rotation gauche (x)
x
5
7
8
4
x
2
1
14
14
2
Françoise Greffier - IUP GMI - Besançon
Arbre rouge et noir : INSERER - cas 2(x est fils droit et oncle droit noir)
7
Couleur (x) <- rougeTant que (x<>racine) et (p[x] est rouge) faire si (p[x] = gauche p[p[x]]) alors
y <- droit p[p[x]] //oncle droit si (couleur (y) = rouge) alors // cas 1 (avant dernière diapo) sinon // cas 2
si (x=droit(p[x] )) alorsx
11
7 14
5
8 152
1
4
5
7
8
4
x
2
1
On fait une rotation pour amenerla situation au cas 3 et nouveau x
Cas 2 : frère du père de x est noir et x est un fils droit
Françoise Greffier - IUP GMI - Besançon
Arbre rouge et noir : INSERER - cas 3(x est un fils gauche et oncle droit noir)
Couleur (x) <- rougeTant que ... faire ... sinon si (x=droit(p[x] )) alors
// cas 2 ...Sinon // cas 3couleur (p[x] ) <- noircouleur (p[p[x]]) <- rouge Rotation droite (p[p[x]]))fsi
x
11
7 14
5
8 152
1
4
7
11
11
7
145 8
15
2
1
4Cas 3 : frère du père de x est noiret x est un fils gauche On a bien un arbre rouge noir
Françoise Greffier - IUP GMI - Besançon
ARBRE 2-3
Quand un ABR est déséquilibré : s’il se réduit par exemple à une liste linéaire chaînée alors les opérations ont une complexité de l ’ordre de (N).
Pour garantir de bonnes performances une deuxième variante des ABR est les arbres 2-3
Françoise Greffier - IUP GMI - Besançon
ARBRE 2-3 : propriétés
Dans un arbre 2-3 :
Chaque nœud interne a exactement 2 ou 3 fils
Tout chemin de la racine à une feuille a une longueur fixe
Françoise Greffier - IUP GMI - Besançon
Un arbre binaire de recherche (ABR) ordonne totalement les informations qu’il stocke(par clé) :A gauche d ’un nœud : valeurs de clés inférieures ou égales à la clé du nœud.A droite : valeurs de clés supérieures strictement.
ARBRE 2-3 : propriétés
Représentation d ’une suite ordonnée dans un arbre 2-3 : Les nœuds internes ont pour valeur les clés les feuilles ont pour valeur les éléments de la suite ordonnée
Françoise Greffier - IUP GMI - Besançon
ARBRE 2-3 : exemple
Relation d ’ordre R :a R b <=> clé(a) R clé(b) 52 7
7 16
5 - 8 12
128
19 -
1916
Représentation d ’une suite ordonnée dans un arbre 2-3 : Un nœud interne a pour valeur :
la clé de l ’élément minimal du deuxième filsla clé de l ’élément minimal du troisième fils
Feuille ont pour valeur les éléments de la suite
Françoise Greffier - IUP GMI - Besançon
ARBRE 2-3 : complexité
Un arbre 2-3 de profondeur k a un nombre de feuilles compris entre 2 k-1 et 3 k-1
La profondeur d ’un arbre 2-3 comprenant N éléments est comprise entre 1+Log 3 (N) et 1+Log 2 (N)Par rapport aux ABR, les opérations : RECHERCHER, MINIMUM, MAXIMUM,SUCCESSEUR et PREDECESSEUR sont triviales dans un arbre 2-3 Par rapport aux ABR, les opérations : INSERER et SUPPRIMER ne sont pas directement supportées dans un arbre 2-3
Françoise Greffier - IUP GMI - Besançon
ARBRE 2-3 : insertion - cas 1
Cas 1 : insérer x=18Cas où le nœud père de x n ’a que deux feuilles. 52 7
7 16
5 - 8 12
128
19 -
1916
52 7
7 16
5 - 8 12
128
18 19
1816 19
Françoise Greffier - IUP GMI - Besançon
ARBRE 2-3 : insertion - cas 2
Cas 2 : insérer x=10La feuille x est un 4ème fils
52 7
7 16
5 - 8 12
128
18 19
16 18 19
Lorsqu’on insère un 4ème fils dans un nœud N , alors on scinde N en deux.
7
8 -
852
7 16
5 - 18 19
16 18 1910
12 -
12
x=10
Françoise Greffier - IUP GMI - Besançon
ARBRE 2-3 : insertion - cas 2
Lorsqu’on insère un 4ème fils dans un nœud N alors on scinde N en deux,Les deux éléments les plus petits restent avec NLes deux plus grands ont pour père un nouveau nœud N1N1 est inséré parmi les pères de N (on itère l ’insertion)
52 7
7 16
5 - 8 -
8
18 19
16 18 1910
12 -
12
N N1
Françoise Greffier - IUP GMI - Besançon
ARBRE 2-3 : insertion - cas 2
52 7
7 16
5 - 8 -
8
18 19
16 18 1910
12 -
12
52 7
10 -
5 - 8 -
8
18 19
16 18 1910
12 -
12
7 - 16 -(12 -) est un 4ème filsde (7 16). on scinde(7 16) en deux nœuds Nouvelle racine 10