3Cours Algorithme 3 .pdf

Cours d’algorithmique et structures
de données
MI2 2005/2006
Fabrice Huet
(fabrice.huet@sophia.inria.fr)

Version étudiants

Unice

Plan
• Algorithmes de recherche
–
–
–
–
–

Recherche Associative, Dictionnaire
Recherche séquentielle dans un tableau
Recherche dichotomique
Arbres, arbre équilibrés
Implémentation d’un dictionnaire avec une table de hachage

• Algorithmes de tri
–
–
–
–

Importance du problème de tri
Borne de complexité optimale
Tri peu efficaces: à bulle et par insertion
Tri optimal en moyenne: quicksort

• Exemples d’algorithmes classiques
– Recherche d’une sous chaîne
– Simplex
– Sécurité et Cryptographie
Version étudiants

Unice

Cours 7
Recherche séquentielle
Recherche dichotomique
Arbres Binaires de Recherche

Version étudiants

Unice

Ensembles dynamiques et dictionnaire
• Les ensembles manipulés par les algorithmes
peuvent croître, diminuer ou subir d’autres
modifications
• De tels ensembles sont dit dynamiques
• Un dictionnaire est un ensemble dynamique qui
supporte
– L’insertion
– La suppression
– La recherche

• D’autres ensembles supportent des opérations plus
complexes, comme la recherche du plus petit
élément.
Version étudiants

Unice

Ensembles dynamiques et dictionnaire
• Pour implémenter un ED, on utilise des objets
• Dans certains cas, l’objet possède un champs
clé
– Il sert a discriminer entre les objets

• Il est aussi possible d’avoir des références
vers d’autres objets de l’ED

Version étudiants

Unice

Opérations sur les ED
• On suppose l’existence d’un ED S
• Rechercher(clé k): retourne une ref. sur l’objet x tel
que x.clé=k, ou NIL si il n’y en a pas
• Insérer(objet x): ajoute à S l’objet x
• Supprimer(objet x): élimine l’objet x de l’ensemble S
• Minimum(): retourne l’objet de S qui a la plus petite
clé
• Maximum(): retourne l’objet de S qui a la plus
grande clé
• Successeur(objet x): retourne le prochain élément
de S plus grand que x ou NIL si x est le plus grand
• Prédécesseur(objet x): retourne le prochain élément
de S plus petit que x ou NIL si x est le plus petit
Version étudiants

Unice

Recherche séquentielle dans un tableau
• Nous allons chercher un élément dans un
ensemble fixe.
• Cet ensemble sera représenté par un tableau
truc tablo[1..N];

• Nous supposerons que le type truc ne
contient pas de clef, i.e. il est la clef

Version étudiants

Unice

Recherche séquentielle dans un tableau
• Comment chercher un élément a dans ce tableau?
• Problèmes:
– truc n’a pas de propriété spéciale
– Le tableau n’est pas ordonné

• Solution: parcourir le tableau pas à pas, c’est une
recherche séquentielle.
• Deux conditions d’arrêt
– On a trouvé l’élément
tablo[i] = a
– On a parcouru tout le tableau sans trouver l’élément

Version étudiants

Unice

Recherche séquentielle dans un tableau
• On a donc l’algorithme suivant
entier i ←1;
tant que ((i ≤ N) et (tablo[i] ≠ a)) {
i ← i+1;
}

• Invariant de boucle:
• Sortie de boucle:

Version étudiants

Unice

Recherche séquentielle dans un tableau
• On trouve l’élément avec le plus petit indice
• La répétition se termine, i est incrémenté, il atteindra
donc N
• Chaque étape nécessite
– Évaluation d’une expression booléenne
– Incrémentation

• Peut-on accélérer la recherche?

Y réfléchir pour la semaine prochaine
Version étudiants

Unice

Recherche dichotomique
• On ne peut pas optimiser sans plus
d’informations sur les données
• On sait que chercher une informations est
plus facile si l’ensemble est ordonné
– Recherche d’un mot dans le dictionnaire
– Recherche dans l’annuaire

• On suppose donc notre tableau ordonné
∀k∈ [2,N] , tablo[k-1] ≤ tablo[k]

• Il faut aussi un ordre total
∀x,y∈ [1,N] , tablo[x] ≤ tablo[y] ou tablo[y] ≤ tablo[x]
Version étudiants

Unice

Recherche dichotomique
exemple
Recherche de l’élément 78
1

3

5

6 10 11 14 25 26 40 41 78

1

3

5

6 10 11 14 25 26 40 41 78

11 ≤ 78

14 25 26 40 41 78

26 ≤ 78

40 41 78

41 ≤ 78

78

78 = 78

4 opérations pour trouver le bon élément
Combien pour une recherche séquentielle?
Version étudiants

Unice

Recherche dichotomique - Algorithme
•
•
•
•

On recherche l’élément x
Si tableau vide, fin
Prendre un élément au hasard (ak)
Comparer cet élément à celui recherché
– x == ak : élément trouvé
– x ≤ ak : chercher l’élément avant
– x ≥ ak : chercher l’élément après

Version étudiants

Unice

Recherche dichotomique - Algorithme
entier g ←1;
entier d ← N;
entier indiceTest ←1;
booléen trouve ← faux;
tant que ((g ≤ d) et (~trouve)) {
indiceTest ← (d-g)/2;
si (tablo[indiceTest] = x)
si (tablo[indiceTest] < x)
si (tablo[indiceTest] > x)
}
Version étudiants

Unice

Recherche dichotomique - Algorithme
• Invariant de boucle
(g ≤ d)
et
et
• Sortie de boucle
trouve ou ((g > d)
et
et
• Ce qui implique
Version étudiants

Unice

Recherche dichotomique - Complexité
• Soit un tableau de taille N
• La première moitié du tableau aura pour taille
N/2
• La prochaine recherche se fera sur un tableau
de taille ½ * N/2 = N/2 2
• Le nombre maximum de recherches est donc
le plus grand entier p tel que 2p ≤ N
– « Combien de fois peut-on couper N en 2 ?»

• On en conclut p≈
• D’où une complexité dans le pire des cas en
Version étudiants

Unice

Arbres binaires de recherche - 1
• Chaque nœud de notre arbre est représenté
par un objet
• Chaque nœud possède
– Un champs clé
– Un pointeur vers son fils gauche: gauche
– Un pointeur vers son fils droit: droit
– Un pointeur vers son parent: parent

• L’arbre T est référencé par sa racine
– Si T.racine = NIL l’arbre est vide
Version étudiants

Unice

Arbre binaire de recherche - 2
• Un ABR a la propriété suivante:
Pour chaque nœud x, tous les éléments du sous arbre
gauche (resp. droit) ont des clés inférieures (resp.
supérieurs) ou égales à celle de x.

• Rappels
– La hauteur d’un arbre est la profondeur maximum de ses
nœuds
– Un arbre complet de hauteur h a 2h+1-1 nœuds

• Successeur:
Le successeur de x est le plus petit y tel que y > x
• On cherche dans un ABR en utilisant une méthode
de dichotomie
Version étudiants

Unice

Cherchez l’ABR
• Des arbres suivants, lesquels sont des ABR?
5

7

2

1

7

3

6

2

8

5

1

3

6

5
9

3

Version étudiants

3

2

8

5

2

1

5
7

1

6

5

4

10

1

8

7

6

6

8
Unice

Parcours infixe
• Comment afficher les éléments du plus petit au plus
grand?
parcoursInfix(noeud x) {

si x ≠ NIL
parcoursInfix(x.gauche);
afficher(x);
parcoursInfix(x.droit);
}
• Complexité?
• Autres parcours?
Version étudiants

Unice

Recherche
• La recherche se fait par dichotomie
rechercher(noeud x, clé k) {
si x = NIL ou x.clé = k
alors retourne x;
si k < x.clé
rechercher(x.gauche,k);
sinon
rechercher(x.droit,k);
}

5
2

Rechercher 3: 5 → 2 → 3

7

Rechercher 6: 5 → 7 → 6
1

3

Version étudiants

6

8
Unice

Recherche - 2
• Proposition : la complexité de la recherche
dans un arbre binaire pour le pire des cas est
O(h) avec h hauteur de l’arbre
• Preuve :

Version étudiants

Unice

Insertion - 1
• Permet d’ajouter un nouveau nœud à un arbre
• L’insertion modifie la structure de l’arbre et doit donc
s’assurer de la conservation de sa propriété
5

5
Inserer(15)

2

7

2

7

Inserer(9)
1

3

6

8

1

3

6

8
15
9

Version étudiants

Unice

Insertion - 2
inserer(arbre T, nœud z) {
y ← NIL
x ← T.racine
tant que x ≠ NIL faire
y←x
si z.clé < x.clé
alors x ← x.gauche;
sinon x ← x.droit;
si y = NIL
alors T.racine ← z;
sinon si z.clé < y.clé
alors y.gauche ← z;
sinon y.droit ← z;
Version étudiants

On cherche un nœud qui n’a
pas de fils pour y ajouter z

L’arbre était en fait vide

On ajoute z a la « bonne »
place

Unice

Suppression - 1
• La suppression enlève un nœud à l’arbre
• Elle doit conserver la propriété de l’ABR
5
5
2

1

7

3

6

supprimer(15)

2

8

Supprimer(7)

8

1

3

6

9

15

9

• On distingue 3 cas pour la suppression

Version étudiants

Unice

Suppression - 2
• Suppression d’un nœud sans fils (trivial)

5
5
2

1

7

3

6

supprimer(9)

2

7

8
1

3

6

8

15
15
9
Version étudiants

Unice

Suppression - 3
• Suppression d’un nœud avec un unique fils
(presque trivial)
5
5
2

1

7

3

6

supprimer(15)

2

8

8
1

3

6

9

15

9
Version étudiants

Unice

Suppression - 4
• Suppression d’un nœud ayant 2 fils (non
trivial)
5

6

2

1

8

3

6

9
7

Successeur de 5

Supprimer(5)

2

1

8

3

7

9

15
11

15
11

• On remplace le nœud à supprimer par son successeur
et on supprime le successeur
Version étudiants

Unice

Suppression - 5
supprimer(arbre T, nœud z) {
si z.gauche = NIL ou z.droit = NIL
alors y ← z
sinon y ← successeur(z);
si y.gauche ≠ NIL
alors x ← y.gauche;
sinon x ← y.droit;
si x ≠ NIL
alors x.parent ← y.parent
si y.parent = NIL
alors T.racine ← x
sinon si y = y.parent.gauche
alors y.parent.gauche ← x;
sinon y.parent.droit ← x;
Si y.clé ≠ z.clé
alors copier(z,y);

On cherche le nœud à détacher

Détachement du noeud

Si le successeur a été détaché,
on copie ses données

Retourner y;
Version étudiants

Unice

Analyse de suppression
supprimer(arbre T, nœud z) {
si z.gauche = NIL ou z.droit = NIL
alors y ← z
sinon y ← successeur(z);
si y.gauche ≠ NIL
alors x ← y.gauche;
sinon x ← y.droit;
si x ≠ NIL
alors x.parent ← y.parent
si y.parent = NIL
alors T.racine ← x
sinon si y = y.parent.gauche
alors y.parent.gauche ← x;
sinon y.parent.droit ← x;
Si y.clé ≠ z.clé
alors copier(z,y);

z a 0 ou 1 fils

On relie le fils de y avec son père

y est fils gauche de son père
x devient fils gauche du père de y
On n’a pas supprimé celui qui était
spécifié mais son successeur

Retourner y;
Version étudiants

Unice

Exemple de suppression
supprimer(arbre T, nœud z) {
si z.gauche = NIL ou z.droit = NIL
alors y ← z
sinon y ← successeur(z);
si y.gauche ≠ NIL
alors x ← y.gauche;
sinon x ← y.droit;
si x ≠ NIL
alors x.parent ← y.parent
si y.parent = NIL
alors T.racine ← x
sinon si y = y.parent.gauche
alors y.parent.gauche ← x;
sinon y.parent.droit ← x;
Si y.clé ≠ z.clé
alors copier(z,y);

z

5

2

1

8

3

6

9
7

y
x

15
11

Retourner y;
Version étudiants

Unice

Exemple de suppression
supprimer(arbre T, nœud z) {
si z.gauche = NIL ou z.droit = NIL
alors y ← z
sinon y ← successeur(z);
si y.gauche ≠ NIL
alors x ← y.gauche;
sinon x ← y.droit;
si x ≠ NIL
alors x.parent ← y.parent
si y.parent = NIL
alors T.racine ← x
sinon si y = y.parent.gauche
alors y.parent.gauche ← x;
sinon y.parent.droit ← x;
Si y.clé ≠ z.clé
alors copier(z,y);

z

5

2

1

8

3

6

9
7

y
x

15
11

Retourner y;
Version étudiants

Unice

Exemple de suppression
supprimer(arbre T, nœud z) {
si z.gauche = NIL ou z.droit = NIL
alors y ← z
sinon y ← successeur(z);
si y.gauche ≠ NIL
alors x ← y.gauche;
sinon x ← y.droit;
si x ≠ NIL
alors x.parent ← y.parent
si y.parent = NIL
alors T.racine ← x
sinon si y = y.parent.gauche
alors y.parent.gauche ← x;
sinon y.parent.droit ← x;
Si y.clé ≠ z.clé
alors copier(z,y);

z

5

2

1

8

3

6

9
7

y
x

15
11

Retourner y;
Version étudiants

Unice

Exemple de suppression
supprimer(arbre T, nœud z) {
si z.gauche = NIL ou z.droit = NIL
alors y ← z
sinon y ← successeur(z);
si y.gauche ≠ NIL
alors x ← y.gauche;
sinon x ← y.droit;
si x ≠ NIL
alors x.parent ← y.parent
si y.parent = NIL
alors T.racine ← x
sinon si y = y.parent.gauche
alors y.parent.gauche ← x;
sinon y.parent.droit ← x;
Si y.clé ≠ z.clé
alors copier(z,y);

z

6

2

1

8

3

5

9
7

y
x

15
11

Retourner y;
Version étudiants

Unice

Résumé
• Nous avons étudié 3 opérations
– Recherche
– Ajout
– Suppression

• Toutes ont une complexité en O(h) avec h
hauteur de l’arbre
• Bonne nouvelle: un arbre complet de n
nœuds à une hauteur de log2(n+1)-1…
• … et les arbres qu’on trouve dans la nature?
Version étudiants

Unice

Problème de l’équilibrage
ajouter(5);

ajouter(7);

ajouter(2);

ajouter(6);

ajouter(3);

ajouter(8);

ajouter(1);

ajouter(8);

ajouter(3);

ajouter(7);

ajouter(2);

ajouter(6);

ajouter(1);

ajouter(5);

• Ces deux arbres contiennent les mêmes données
• Mais leur hauteur est très différente
• Il vaut mieux avoir l’arbre gauche (
) que celui de
droite (
)
Version étudiants
Unice

Arbres équilibrés
• Un arbre est dit équilibré si pour chacun de
ses nœuds, les sous arbres diffèrent d’au plus
1 en profondeur

Version étudiants

Unice

Arbres équilibrés - 2
• Pourquoi avoir des arbres équilibrés?
• Parce que dans le pire des cas, la recherche
est en O(log(n))!
• Preuve?
– On a vu que la recherche dans un ABR est O(h)
avec h hauteur de l’arbre dans le pire des cas
– Il nous faut donc montrer que la hauteur d’un
arbre équilibréé est O(log(n))

Version étudiants

Unice

Hauteur d’un arbre équilibré
• On va chercher le nombre minimum de
nœuds (pas feuilles) nécessaire pour
construire un arbre de hauteur h
• Soit Th un arbre équilibré minimal de hauteur
h avec nh nœuds.
• On a

Version étudiants

T0 =

n0 = 0

T1 =

n1 = 1

Unice

Hauteur d’un arbre équilibré - 2
• On considère Th, h≥2. Il doit donc avoir un sous arbre de
profondeur h-1 et un autre de profondeur h-1 ou h-2
• Les 2 cas sont-ils possibles?

Th

Th-1

Version étudiants

Th-1

Th-1

Th-2

Unice

Hauteur d’un arbre équilibré - 3
• On considère Th, h≥2. Il doit donc avoir un sous
arbre de profondeur h-1 et un autre de profondeur
h-1 ou h-2.
• Pour tout k, un arbre de hauteur k a un sous arbre
de hauteur k-1. Donc pour certains nk > nk-1
• Supposons que les deux sous arbres de Th sont Th-1
et Th-1
– alors on pourrait en remplacer un par Th-2 et garder la
propriété d’équilibrage
– on aurait alors moins de nœuds car nh-1 > nh-2
– notre arbre ne serait donc pas minimal:
CONTRADICTION!
Version étudiants

Unice

Hauteur d’un arbre équilibré - 4
• Th a donc a un sous arbre Th-1 et un autre Th-2
Th =

nh = nh-1 + nh-2 +1
Th-1 Th-2

• Ça ressemble étrangement à la suite de
Fibonacci!
• On montre (pas ici) que
1 1+ 5 


nh =
5  2 
Version étudiants

h+2

1 1− 5 


−
5  2 

h+2

−1
Unice

Hauteur d’un arbre équilibré - 5
• Étant donné que
petit

le terme

sera

• Donc
• Comme nh nombre minimal de nœuds pour un arbre
équilibré de hauteur h, tout autre arbre équilibré de
hauteur h aura n nœuds tel que

• Ce qui donne
Version étudiants

Unice

Complexité des opérations
• Nous avons donc montré qu’un arbre équilibré
compose de n nœuds aura une hauteur majorée par
1.44log(n+1)
• On sait que les opérations
d’ajout/recherche/suppression dans un arbre dans le
pire des cas ont une complexité en O(h)
• Conclusion: Dans un arbre binaire équilibré
composé de n noeuds, les opérations d’ajout, de
recherche et de suppression ont une complexité
dans le pire des cas en O(ln(n)).
Version étudiants

Unice