Cours Algorithmique avance PARTII
Structures des donnes Algorithmique
Hafidi Imad
ENSAK
Arbres
Un arbre est une structure de donnes organises de faon hirarchique, partir dun nud distingu appel racine. Trs importante en informatique!. Arbre de jeux (i.e., Echecs ), systme de fichiers UNIX/Windows, Arbres de tri etc.
Dfinition
Algorithmique Un arbre est une structure de donnes organises de faon hirarchique, partir dun nud distingu appel racine. Un lment quelconque peut avoir plusieurs successeurs, mais un seul prdcesseur. Seul le premier lment na pas de prdcesseur.
noeuds
artes
3
Arbres: dfinitions
Un arbre est un ensemble de Nuds, relis par des Artes. Entre deux nuds il existe toujours un seul chemin.
noeuds
artes
4
Terminologie
Les lments
Un sommet ou nud est un lment quelconque dun arbre. La racine est lunique sommet nayant pas de prdcesseur. Une feuille ou nud terminal est un lment nayant pas de successeur. Le prdcesseur unique dun nud est appel le pre. Les successeurs dun nud sont appels les fils. Les nuds qui ont le mme pre sont appels frres. Le frre place le plus a gauche est laine.
Les chemins
Un arte est un chemin reliant deux nuds Une branche est un chemin reliant la racine a une feuille.
Arbres: dfinitions
Les arbres sont enracins. Une fois la racine dfinit tous les nuds admettent un niveau. Les arbres ont des nuds internes et des feuilles (nuds externes). Chaque nud ( lexception de la racine) a un parent et admet zro ou plusieurs fils.
racine niveau 0 niveau 1 niveau 2 niveau 3 feuilles parent et fils
6
nuds internes
Arbres binaires
Un Arbre Binaire est un arbre o chaque nud admet au plus 2 fils.
Arbres Binaires: dfinitions
Nuds dun arbre contiennent des cls (mots, nombres, etc) Arbre Binaire complet : les feuilles sont toutes situes dans les deux derniers niveaux. Les feuilles du dernier niveau sont toutes gauche.
14
10 8 7 9 11 12 13 15
16 18
8
Arbres Binaires: reprsentation par tableaux
Un arbre binaire complet peut tre reprsent par un tableau A avec un accs en O(1) chaque nud: Mmoriser les nuds squentiellement de la racine aux feuilles et de gauche vers la droite. Fils gauche de A[i] est en A[2i] Fils droit de A[i] est en A[2i + 1] Parent de A[i] est en A[i/2]
1 14 2 10 4 8 8 7 9 10 9 11 13 12 5 6 15 11 3 16 7 18
1 tab A: 14
2 10
4 16 8
6 12
8 9 15 18
10 11 7 9 11 13
10
Arbres Binaires: reprsentation par pointeurs
typedef struct n{ int cl; cl; struct n *fGauche, *fDroit; *fGauche, *fDroit; }nud; typedef nud * Arbre;
11
Parcours : inOrdre
InOrdre est dcrit rursivement : Visiter le sous-arbre gauche en InOrdre Visiter la racine Visiter le sous-arbre droit en InOrdre
12
Parcours : prOrdre
PrOrdre est dcrit rursivement : Visiter la racine Visiter le sous-arbre gauche en PrOrdre Visiter le sous-arbre droit en PrOrdre
13
Parcours: postOrdre
PostOrdre est dcrit rursivement : Visiter le sous-arbre gauche en PostOrdre Visiter le sous-arbre droit en PostOrdre Visiter la racine
14
Arbre Binaire de Recherche
Un Arbre Binaire de Recherche (ABR) est un arbre binaire avec les proprits suivantes :
La cl associe un nud est suprieur aux cls des nuds de son sous-arbre gauche La cl associe un nud est infrieur aux cls des nuds de son sous-arbre droit
15
Arbre Binaire de Recherche: Exemples
racine C A D 10 racine 8 14 11 15 18 16 racine 14
10 8 11 15
16
16
Arbre Binaire de Recherche
ABR est un arbre avec la proprit suivante
Cl.fGauche < Cl.parent < Cl.fDroit NOTER! Le parcours InOrdre visite les cls dans lordre croissant.
void inOrdre(Arbre racine) { inOrdre(racine->fGauche) print(racine->key) inOrdre(racine->fDroit) }
17
ABR: InOrdre
Exemple: InOrdre visites : 14 (8) (10) (11) (14) (15) (16) (18)
10 8 11 15
16 18
18
ABR : Rechercher un lment
rechercher(racine, x) comparer x la cl de racine: - si x = cl return - si x < cl => chercher dans G - si x > cl => chercher dans D chercher de la mme manire dans G ou D
Exemple:
14
10 8 11 15
16
x=8 (oui) x=17 (non)
19
ABR : Rechercher un lment
bool searchABR(Arbre racine; typeCle cl){ searchABR(Arbre if (racine==NULL) return false if (racine->cl==cl) return true; else if (key < racine->cl) return searchABR(racine->fGauche, cl); else return searchABR(racine->fDroit, cl) }
Donner une version itrative ?
20
ABR : Ajout dun lment
Comment ajouter une cl?
La mme procdure que searchABR sapplique: Dterminer la position dinsertion par searchABR. Ajouter la nouvelle cl si la recherche choue.
Exemple:
10
8 3 2 5 9
ajout 4?
4
21
Construction dun ABR
Exemple: ajouter C A B L M (dans lordre!) 3) ajouter B C C A B 4) Ajouter L A B B M
22
1) Ajouter C
2) ajouter A
C A
C L
5) Ajouter M
C A L
Construction dun ABR
LABR est-il unique pour une squence de lettres A B C L M ?
NON! diffrentes squences donnent
diffrents ABR
Ajout de : A B C L M A C B C L M A B L M
23
Ajout de : C A B L M
Trier avec un ABR
Soit un ABR, peut-on afficher les cls dans lordre? Visiter lABR avec un parcours InOrdre: - visiter le sous-arbre gauche - afficher racine - visiter le sous-arbre droit Comment trouver le minimum? Comment trouver le maximum?
Exemple:
C A B L M
InOrdre affichage: A B C L M
24
ABR : supprimer un lment
Pour supprimer un nud contenant x, rechercher x, une fois trouv appliquer lun des trois cas suivants:
CAS A: x est une feuille
p q r q p
x
supprimer x
r On obtient un ABR
25
ABR : supprimer un lment
Cas B: x est un nud interne avec un seul sous-arbre
r x
q q L On obtient un ABR
26
suppr x
ABR : supprimer un lment
Cas C: x est un nud interne avec 2 sousarbres
r r x q W ts Z W t
27
suppr x u q s Z
suppr x
proprit ABR est conserv
ABR : supprimer un lment
Cas C suite: ou encore comme suit
q < x < u
r q W t u s Z
28
q est infrieur au plus petit lment de Z r est suprieur au plus grand lment de W
ABR : Complxit de rechercher
Quelle est la complxit de searchABR ? Dpend de :
la cl x des autres donnes De la forme de larbre
Analyse de la complxit : On est intrss par la complxit dans le meilleur cas, pire cas.
29
ABR : Complxit de rechercher
niveau 0 niveau 1 niveau 2 niveau 3 hauteur dun ABR = niveau max hauteur dun noeud h(x) = 0 si x est la racine h(x) = 1+ h(y), y = pere(x)
(h =3)
hauteur dun ABR B : h(B) = max{h(x), x nud de B}
30
ABR : Complexit de rechercher
Si tout les nuds de larbre existent : ABR plein Si tout les nuds existent sauf ceux du dernier niveau : niveau-min ABR
31
ABR : Complexit de rechercher
Thorme: h+1 Un ABR plein (complet) de hauteur h a 2 - 1 noeuds
Preuve: Par induction Cas de base: un arbre de hauteur 0 a 1 nud (racine) Hypothse inductive: Supposant quun ABR de hauteur h a h+1 2 - 1 noeuds
32
ABR : Complexit de recherche
Etape dinduction: Connecter 2 ABR de hauteur h pour construire un ABR de hauteur h+1. On a besoin dajouter un noeud supplmentaire racine
h+1 h G D
Par hypothse inductive le nouveau nombre de noeuds est (2 - 1) + (2 -1) + 1 = 2
h+1 h+1 h+2
-1
CQFD!
33
ABR : Complexit de rechercher
Lemme 1: pour un ABR ayant n nud et de hauteur h : log2 n <= h <= n -1 Remarque: Un ABR parfait avec n noeuds a pour hauteur h = log2 n
h 2 <= n <= 2 h+1 - 1
34
car
ABR : Complexit de rechercher
Consquence : pour un ABR plein avec N noeuds la complxit de searchABR: meilleur cas O(1) Pire cas O(log N)
35
ABR : complxit de rechercher
Maintenant que nous connaissons la complxit de searchABR que peut-on dire
des autres oprations? Insertion Suppression Trouver le Min Trouver le Max Tri ABR = O(log N) O(log N) O(log N) O(log N) O(N log N)
Pourquoi?
Ide: ABR tri = (Construction de lABR : N insertions) 36 + (Parcourir ABR)
ABR : Complxit de rechercher
En rsum, il est ncessaire davoir un ABR plein ou niveau-min ABR garder un arbre le plus quilibr possible tout moment (Arbre AVL)
37
Arbre AVL
Arbre AVL (Adelson-Velskii et Landis):
Le meilleur ABR maintenant tout moment un arbre raisonnablement quilibr. Ide : si linsertion ou la suppression provoque un dsquilibre de larbre, rtablir lquilibre. Toutes les oprations insertion, suppression, sur un arbre AVL avec N nuds en O(log N) (en moyenne et dans le pire cas!)
38
Arbre AVL
ABR tq. la diffrence des hauteurs du sous-arbre gauche et droite de la racine est dau plus 1 et les sous-arbres gauche et droit sont des AVL.
Exemple:
39
Arbres AVL - exemple
12
16
10
14
Cet arbre est un arbre AVL
Arbres AVL exemple
Ces noeuds violent la condition 12
16
10
14
1 Aprs lajout de 1 ce nest plus un arbre AVL
Arbres AVL - exemple
12
16
10
14
13
Aprs lajout de 13 ce nest plus un arbre AVL
Arbres AVL
Il faut, aprs chaque insertion ou retrait, rtablir lquilibre sil a t rompu par lopration Observation importante: aprs une insertion, seuls les nuds qui sont sur le chemin du point dinsertion la racine sont susceptibles dtre dsquilibrs Deux cas: insertion dans le sous-arbre de gauche du fils gauche ou dans le sous-arbre de droite du fils droit: Simple rotation insertion dans le sous-arbre de droite du fils gauche ou dans le sous-arbre de gauche du fils droit: Double rotation
AVL exemle de simple rotation
12 8 Hauteur = 2 4 10 14 16
Hauteur = 0
AVL exemple de simple rotation
12 8 16
10
14
AVL exemple de simple rotation
12 4 16
14 2 8
10 1 6
AVL exemple de simple rotation
12 4 16
14 2 8
10 1 6
Arbres AVL simple rotation
void RD(Arbre *a){ Arbre aux= (*a)->fg; (*a)->fg = aux->fd; aux->fd= *a; *a= aux; }
void RG(Arbre *a){ Arbre aux= (*a)->fd; (*a)->fd = aux->fg; aux->fg= *a; *a= aux; }
AVL exemple de double rotation
12
16
10
14
6 Nud insr 7
AVL exemple de double rotation
12
16
10
14
AVL exemple de double rotation
12
8 6
16
10
14
AVL exemple de double rotation
12
8 6
16
10
14
AVL exemple de double rotation
12
16
14 4 8
10
AVL implmentation
Algorithme rcursif Une fois le nud insr, en revenant sur notre chemin, il faut vrifier, pour chaque nud parcouru, les diffrences de profondeur des sous-arbres gauche et droite La rotation peut tre requise nimporte quel nud qui se trouve dans le chemin de la racine au point dinsertion Le retrait est passablement plus compliqu que linsertion (mais demeure O(lg N)) Il y a dautres types darbres quilibrs plus facile implmenter et plus efficaces
AVL exemple dtaill
Pour chaque noeud on mettra 0 si ses deux sous-arbres ont la mme profondeur +n si le sous-arbre gauche est plus profond avec une diffrence = n -n si le sous-arbre droit est plus profond avec une diffrence = n
Squence dinsertion: 2 10 12 4 16 8 6 14
AVL exemple dtaill
2 10 12 4 16 8 6 14
AVL exemple dtaill
2 10 12 4 16 8 6 14 2
-1
10
AVL exemple dtaill
2 10 12 4 16 8 6 14 2
-2
10
-1
12
AVL exemple dtaill
2 10 12 4 16 8 6 14 10 2
0
12
Rotation simple
AVL exemple dtaill
2 10 12 4 16 8 6 14 10 2
1
-1
12
AVL exemple dtaill
2 10 12 4 16 8 6 14 10 2
-1 0
12
-1
16
AVL exemple dtaill
2 10 12 4 16 8 6 14 10 2
1
-2
12
-1
-1
16
AVL exemple dtaill
2 10 12 4 16 8 6 14 10 4
0 0
12
-1
16
Rotation simple
AVL exemple dtaill
2 10 12 4 16 8 6 14 10 4
-1 1
12
-1
16
AVL exemple dtaill
2 10 12 4 16 8 6 14 10 4
-1 0
12
-2
16
14
AVL exemple dtaill
2 10 12 4 16 8 6 14 10 4
1
-1
14
12
0
16
0
Rotation double
AVL autre exemple
Voici un exemple o la rotation se fait loin du point dinsertion
10 4
1 -1
14 12
0
2 6
16
0
-1
7
0
Noeud insr
AVL autre exemple
Voici un exemple o la rotation se fait loin du point dinsertion
0
8 4
1 0
10
-1
-1
9
0
14
0
12
16
Aprs rotation double
Arbres Rouge-Noir
Larbre a les proprits suivantes: 1. Chaque nud est soit rouge soit noir 2. La racine est noire 3. Si un nud est rouge, tous ses enfants doivent tre noirs 4. partir de nimporte quel nud, tous les chemins de la racine jusqu un pointeur NULL doivent avoir le mme nombre de nuds noirs Comme la racine est noire et il ne peut y avoir plus de deux nuds rouges conscutifs, la longueur de tout chemin de la racine une feuille ne peut tre suprieure 2 fois le nombre de nuds noirs dans ce chemin
Arbres Rouge-Noir - Exemple
30
15 10 20
70
60 50 65 80
85 90
40
55
Tris par Tas
Ide :
On slectionne les minimums successifs en utilisant une structure de donne particulire : le
tas
Dfinition
Un arbre parfait est un arbre binaire dont les feuilles sont situes sur deux niveaux successifs : lavant dernier niveau est complet, et les feuilles du dernier niveau sont regroupes le plus gauche possible.
Exemple
71
Dfinition
Un arbre parfait partiellement ordonn est un arbre parfait dont les sommets sont tiquets par des lments trier, et tel que llment associ chaque sommet est sommet.
aux lments associs aux fils de ce
Exemple
72
Dfinition
Un tas (heap) est un tableau t reprsentant un arbre parfait partiellement ordonne selon les rgles suivantes : t[1] est la racine t[2i] et t[2i + 1] sont les fils gauche et droite de t[i] (sils existent)
Exemple
73
Proprits simples dun tas
t[i/2] est le pre de t[i] (i 2) Si le nombre de sommets n est pair, alors t[n/2] a un seul fils t[n] Si i > n/2, alors t[i] est une feuille
Ide du tri par tas
1) On construit le tas 2) On enlve successivement le minimum du tas et on reconstruit la structure de tas sur le reste des lments
74
CONSTRUCTION DU TAS
Lessentiel est une procdure AJOUT qui ajoute un lment nouveau un tas. On ajoute cet lment comme une feuille (au dernier niveau), puis on lchange avec son pre tant quil est infrieur celui-ci.
75
Exemple
Rsultat final
76
Complexit en pire cas
La procdure AJOUT fait au plus log(p) comparaisons.
Pourquoi?
Parce que la hauteur dun arbre parfait p sommets est log(p).
77
SUPPRESSION DU MINIMUM ET REORGANISATION DU TAS
La procdure DESTRUCTION remplace la racine du tas par la dernire feuille. Pour rorganiser le tas, on change cet lment avec le plus petit de ses deux fils tant quil est suprieur celui-ci.
78
Exemple
Rsultat final
79
Lalgorithme TRI-TAS
On ajoute successivement chacun des n lments dans le tas
t[1 . . . p], p augmente de 1 aprs chaque adjonction. A la fin on a un tas de taille n. Tant que p > 1, on supprime le minimum du tas, on dcroit p de 1, et on range le minimum la (p + 1)eme place. Puis on rorganise le tas. t[p + 1 . . . n] contient les n p plus petits lments en ordre dcroissant.
80
Exemple
81
Exemple suite
82
83
84
85
86
87
Tableaux associatifs
Un tableau dans lequel un contenu est associ une clef : Un dictionnaire Un annuaire Remarques : Un tableau est un tableau associatif a clefs entires. Comment faire un dictionnaire en C ? Quelle complexit pour la recherche dans cette solution ? Les tableaux associatifs n'ont pas d'ordre (a priori). Souvent, leur implmentation en a un ! Objectif : Accs en temps constant la donne connaissant sa clef.
88
Hash Tables
Une Table de Hachage est une faon d'implmenter un tableau associatif : On se donne un tableau de taille N? Pour un couple clef/contenu a insrer dans le tableau :
1. On calcule un entier significatif de sa clef (son hashCode : i) 2. On place le couple clef/valeur a la place tab[i]
Problmes :
Il faut ncessairement 0< hash(clef) <N Comment choisir la fonction hash ? peu de collisions. Gestion des collisions.
89
Fonctions de hachage
Peu de collisions : le mieux : une distribution uniforme des clefs...
limitation de taille : rsultat du hachage pris modulo N.
Exemple de fonction de hachage pour une chaine :
h(s) = s[0]*B^(n) %m + s[1]*B^(n) %m + ... + s[n] %N (n longueur de s)
En java, pour une chaine de char, la mthode hashCode utilise B=31 (nombre premier pour viter interfrences entre %m et les B^k )
90
Gestion des collisions
Adressage ferm (chainage) :
On arrive directement au bon endroit, reste a lever l'indcision entre les collisions.
91
Importances des collisions
Temps de recherche / insertion augmente avec le nombre de collisions. Le nombre de collisions est li la charge (taux de remplissage) de la table. Ceci s'obtient par des probas. En gnral, on fixe un taux de remplissage max, et la taille de la table augmente pass ce taux. (on replace alors les valeurs et on change la fonction de hash....)
92
