Algorithmique et Analyse d’Algorithmes
Algorithmique et Analyse d’Algorithmes
L3 Info
Cours 7 : Structures de données dynamiques
Benjamin Wack
2017- 2018
1 / 32
Algorithmique et Analyse d’Algorithmes
La dernière fois
I Structures arborescentes
I Type Abstrait Arbre Binaires (et autres)
I Partition Binaire de l’Espace
Aujourd’hui
I Structure dynamique
I Arbre Binaire de Recherche (ABR)
I Opérateurs de base
I Coûts des opérateurs
2 / 32
Algorithmique et Analyse d’Algorithmes
Plan
Notion de structure dynamique
Arbre Binaire de Recherche
Algorithmes pour les opérations des ABR
Analyses de coût
Garantir des coûts logarithmiques
3 / 32
Algorithmique et Analyse d’Algorithmes
Notion de structure dynamique
Motivation
Comportement dynamique
On cherche à construire une structure de données qui permet de :
I ajouter de nouveaux éléments
I retirer des éléments existants
I éventuellement mettre à jour un élément
De plus cette structure doit garantir un certain nombre de propriétés :
I qualitatives (par exemple : données triées, sans doublon...)
I quantitatives (contraintes de complexité)
Exemples
I Annuaire : recherche rapide, éventuellement par numéro
I Réseau social : facilité d’exploration des liens successifs
5 / 32
Algorithmique et Analyse d’Algorithmes
Notion de structure dynamique
Méthodologie
Définition
I On reprend la méthodologie TAD.
I Par commodité, les fonctions d’insertion, suppression, mise à jour
sont souvent des fonctions à effet de bord.
I Les propriétés qualitatives à vérifier sont ajoutées aux axiomes.
Évaluation des coûts
I La « forme » de la structure dépend des opérations subies
dynamiquement.
I Donc le coût des opérations aussi.
Deux possibilités :
I déterminer les caractéristiques moyennes d’une structure et évaluer
le coût d’une opération sur cette base
I OU effectuer une analyse de coût amorti (non traité ici) 6 / 32
Algorithmique et Analyse d’Algorithmes
Arbre Binaire de Recherche
Caractéristiques recherchées
I La structure dynamique voulue doit permettre d’accéder à tout
élément rapidement.
I On dispose d’un ordre total sur le type Element.
Représentation Recherche Insertion Suppression
Tableau non ordonné O(n) O(1) O(1)
Tableau ordonné O(log n) O(n) O(n)
Liste chaînée non ordonnée O(n) O(1) O(1)
Liste chaînée ordonnée O(n) O(n) O(1)
Seul espoir de recherche rapide : maintenir un ensemble trié.
Mais comment assurer également une insertion et une suppression
efficaces ?
I Utilisation d’une structure arborescente pour accéder (et modifier)
rapidement tout point de la structure
8 / 32
Algorithmique et Analyse d’Algorithmes
Arbre Binaire de Recherche
Le principe des Arbres Binaires de Recherche
I La clé de la racine est supérieure à celle de tous les nœuds du fils
gauche.
I La clé de la racine est inférieure à celle de tous les nœuds du fils
droit.
⇒ permet une recherche de type dichotomique : comparer e à la racine
suffit à déterminer dans quel sous-arbre il se trouve.
r
15
9 18
5 11 16 19
2 6 14 24
g d
<r >r
Enfin ce principe s’applique récursivement : le fils gauche et le fils droit
sont tous deux des Arbres Binaires de Recherche.
9 / 32
Algorithmique et Analyse d’Algorithmes
Arbre Binaire de Recherche
Le type abstrait Arbre Binaire de Recherche
Nom ABR (Element)
Utilise Element, bool
Opérations Idem Arbre binaire
Préconditions Idem Arbre binaire
Axiomes Idem Arbre binaire +
∀x ∈ a :
∀y ∈ FilsGauche(x ), Racine(y ) ≤ Racine(x )
∀z ∈ FilsDroit(x ), Racine(x ) ≤ Racine(z)
Ou de façon équivalente :
∀y ∈ FilsGauche(a), Racine(y ) ≤ Racine(a)
∀z ∈ FilsDroit(a), Racine(a) ≤ Racine(z)
FilsGauche(a) est un ABR
FilsDroit(a) est un ABR
∀x ∈ a, Racine(FilsGauche(x )) ≤ Racine(x ) ne suffit pas.
10 / 32
Algorithmique et Analyse d’Algorithmes
Arbre Binaire de Recherche
Opérations supplémentaires : modificateurs
Opérations Rechercher : Element × ABR → ABR
Minimum : ABR → ABR
Insérer : Element × ABR → ABR
Supprimer : Element × ABR → ABR
Préconditions Minimum(a) : ¬ EstArbreVide(a)
Supprimer(e, a) : ¬ EstVide(Rechercher(e, a))
Axiomes
Rechercher(e, ArbreVide()) = ArbreVide()
Rechercher(e, N(g, r , d)) = N(g, r , d) si e = r
= Rechercher(e, g) si e < r
= Rechercher(e, d) si r < e
= ArbreVide() sinon
..
.
Opérations dérivées : on peut les coder à partir des opérations de base.
Mais ce sont elles qui maintiennent les caractéristiques de la structure.
11 / 32
Algorithmique et Analyse d’Algorithmes
Algorithmes pour les opérations des ABR
Rechercher
15
9 18
5 11 16 19
2 6 24
RECHERCHER(e, a)
Données : Une clé e, un ABR a
Résultat : Si possible un nœud de a dont la clé est e, sinon ArbreVide()
if EstVide(a)
return ArbreVide()
else if e = Racine(a)
return a
else if e < Racine(a)
return RECHERCHER(e, FilsGauche(a))
else // e > Racine(a)
return RECHERCHER(e, FilsDroit(a))
Variante : renvoyer une information associée à la clé plutôt que le nœud
13 / 32
Algorithmique et Analyse d’Algorithmes
Algorithmes pour les opérations des ABR
Minimum
15
9 18
5 11 16 19
6 24
MINIMUM(a)
Données : Un ABR a non vide
Résultat : Un nœud de a dont la clé est inférieure à toutes les autres clés
de a
if EstVide(FilsGauche(a))
return a
else
return MINIMUM(FilsGauche(a))
Remarque
Cet algorithme et le précédent s’écrivent aussi bien sous forme impérative
sans pile.
14 / 32
Algorithmique et Analyse d’Algorithmes
Algorithmes pour les opérations des ABR
Insérer
15
9 18
5 11 16 19
2 6 24
INSERER(e, a)
Données : Une clé e, un ABR a
Résultat : Un ABR dont les clés sont : e et les clés de a
if EstVide(a)
return N(ArbreVide(), e, ArbreVide())
else if e ≤ Racine(a)
return N( INSERER(e, FilsGauche(a)), Racine(a), FilsDroit(a))
else // e > Racine(a)
return N( FilsGauche(a), Racine(a), INSERER(e, FilsDroit(a)))
Variante : chaque clé est unique, si e = Racine(a) on met à jour le nœud.
15 / 32
Algorithmique et Analyse d’Algorithmes
Algorithmes pour les opérations des ABR
Supprimer
15
9 18
5 11 16 19
2 6 24
SUPPRIMER(e, a)
Données : Un élément e présent dans a, un ABR a
Résultat : Un ABR contenant les mêmes clés que a sauf e
... comme RECHERCHER mais...
..
.
if e = Racine(a)
return SUPPRIMER_RACINE(a)
..
.
16 / 32
Algorithmique et Analyse d’Algorithmes
Algorithmes pour les opérations des ABR
Supprimer (2)
15
9 18
5 11 16 19
2 6 24
SUPPRIMER_RACINE(x )
if EstVide(FilsGauche(x )) return FilsDroit(x );
else if EstVide(FilsDroit(x )) return FilsGauche(x );
else
m := MINIMUM( FilsDroit(x ) )
return N(FilsGauche(x ), m, SUPPR_MIN(FilsDroit(x )))
SUPPR_MIN(x )
... (presque) comme MINIMUM mais ...
..
.
if EstVide(FilsGauche(x )) return FilsDroit(x );
.. 17 / 32
.
Algorithmique et Analyse d’Algorithmes
Analyses de coût
Premier constat
Il est facile de voir que toutes les opérations sont en O(h) où h est la
hauteur de l’arbre parcouru.
On s’intéresse donc à la hauteur d’un ABR de n nœuds construit par n
insertions successives dans l’arbre vide.
Pire cas
I Au pire h = n (hauteur maximale d’un arbre à n nœuds).
I Concrètement, ce pire cas est atteint quand les données sont
insérées par croissant (ou décroissant).
Meilleur cas
I Au mieux h = blog2 nc (hauteur minimale d’un arbre à n nœuds).
I Concrètement, ce meilleur cas est atteint quand... ?
19 / 32
Algorithmique et Analyse d’Algorithmes
Analyses de coût
Arbre moyen
On détermine maintenant la structure moyenne d’un ABR de n nœuds
construit par n insertions successives dans l’arbre vide.
Hypothèse de répartition des données : les n! permutations des n clés
introduites sont équiprobables.
En particulier la racine de l’ABR (qui est toujours la première clé insérée)
peut porter de façon équiprobable la 1re, la 2e, . . . , la ne clé (par rapport
à la liste triée).
Remarque : si la racine est la i e clé, alors :
I le sous-arbre gauche contient i − 1 nœuds
I le sous-arbre droit contient n − i nœuds
20 / 32
Algorithmique et Analyse d’Algorithmes
Analyses de coût
Profondeur totale des nœuds dans un ABR
Somme des profondeurs
On note P(a) la somme des profondeurs de tous les nœuds de a.
X
P(a) = d(x , racine(a))
x ∈a
Structure récursive
Pour tout arbre a de n nœuds,
Si a = N(g, r , d), alors P(a) = P(g) + P(d) + n − 1.
P P
P(a) = d(x , racine(a)) + d(x , racine(a)) + p(r )
x ∈g x ∈d
P P
= (d(x , racine(g)) + 1) + (d(x , racine(d)) + 1) + 0
x ∈g x ∈d
= P(g) + nb_noeuds(g) + P(d) + nb_noeuds(d)
= P(g) + P(d) + n − 1 21 / 32
Algorithmique et Analyse d’Algorithmes
Analyses de coût
Profondeur moyenne des nœuds dans un ABR
On s’intéresse à Pn la valeur moyenne de P(a) pour tous les arbres a de n
nœuds :
I l’équation de récurrence s’applique encore
I l’hypothèse d’équirépartition assure que les n cas de la forme
« i − 1 nœuds dans g, n − i nœuds dans d » sont équiprobables.
On en déduit que :
n
1
(Pi−1 + Pn−i + n − 1)
P
Pn = n
i=1
n n n
1 1 1
n−1
P P P
= n Pi−1 + n Pn−i + n
i=1 i=1 i=1
n−1
2
n−1
P
Pn = n Pi +
i=0
n−2
2 P
de même Pn−1 = n−1 Pi + n−2
i=0
22 / 32
Algorithmique et Analyse d’Algorithmes
Analyses de coût
Profondeur moyenne des nœuds dans un ABR (2)
En éliminant la somme (cf détail au tableau) :
nPn − (n − 1)Pn−1 = 2Pn−1 + n(n − 1) − (n − 1)(n − 2)
Pn Pn−1 n−1
n+1 = n + 2 n(n+1)
Pn Pn−1 4 2
n+1 = n + n+1 − n
n
Pn 4
− 2i )
P
n+1 = ( i+1
i=1
n
Pn 1 2
−4
P
n+1 = 2 i + n+1
i=1
Pn
n+1 = 2 log n + un terme négligeable devant log n
D’où
Pn = O(n log n)
et
la profondeur moyenne d’un nœud est O(log n). 23 / 32
Algorithmique et Analyse d’Algorithmes
Analyses de coût
Conséquences
I Le coût de la recherche d’une clé existant dans l’arbre est
exactement sa profondeur :
Le coût moyen de la recherche est O(log n).
I En l’absence de suppressions, le coût d’insertion de chaque nœud est
exactement sa profondeur :
I INSERTION suit le même chemin que RECHERCHE ;
I les nœuds ne sont pas déplacés par les insertions suivantes.
Le coût total moyen de l’insertion de n nœuds est O(n log n).
Admis : la hauteur moyenne d’un ABR obtenu par insertions successives
de n nœuds en ordre aléatoire est O(log n).
24 / 32
Algorithmique et Analyse d’Algorithmes
Analyses de coût
Une application « évidente »
L’idée initiale de l’ABR était de maintenir une structure triée pour
accélérer la recherche et l’accès d’un élément : comment récupérer
l’ensemble trié ?
PARCOURS_PROFONDEUR_INFIXE(a)
if ¬ EstArbreVide(a)
PARCOURS_PROFONDEUR_INFIXE ( FilsGauche(a) )
Traiter( Racine(a) )
PARCOURS_PROFONDEUR_INFIXE ( FilsDroit(a) )
D’où l’algorithme de tri par ABR :
while Il reste des données
Insérer une donnée dans l’ABR
Parcourir l’ABR en profondeur infixe.
25 / 32
Algorithmique et Analyse d’Algorithmes
Analyses de coût
Complexité du tri par ABR
I Coût du parcours en profondeur infixe : O(n)
I Coût des n insertions successives :
I Au pire : O(n2 )
I Au mieux et en moyenne : O(n log n)
Lien avec le tri rapide
I Le premier élément e1 inséré dans l’arbre est mis à sa place définitive.
Tous les éléments < e1 sont insérés à gauche.
™
I
segmentation
I Tous les éléments > e1 sont insérés à droite.
I La construction des sous-arbres suit récursivement ce processus.
En revanche :
I L’ABR procède de haut en bas, le tri rapide de bas en haut.
I La segmentation du tri rapide peut bouleverser l’ordre d’insertion.
La complexité du tri rapide est au pire en O(n2 ), en moyenne en O(n log n).
26 / 32
Algorithmique et Analyse d’Algorithmes
Garantir des coûts logarithmiques
Marge de progression
Les coûts moyens (et au mieux) de la recherche et de l’insertion sont
logarithmiques, mais le cas pire est linéaire : peut-on l’éviter ?
Il faut (et il suffit) que h = O(log n).
Origine des pires coûts
Déséquilibres de l’arbre, introduits par :
I insertion dans une branche déjà chargée
I suppression dans une branche déjà légère
OU réorganisation malencontreuse suite à la suppression
28 / 32
Algorithmique et Analyse d’Algorithmes
Garantir des coûts logarithmiques
Deux pistes de solutions
Améliorer les opérations
pour rééquilibrer l’arbre au fur et à mesure
I en se basant sur quelle information ? il faut la stocker aussi...
I attention à ne pas payer un coût supplémentaire !
Améliorer la structure
pour qu’il y ait « toujours de la place »
I la hauteur ne change pas, ou alors par la racine ⇒ équilibre parfait
I mais on perd l’aspect binaire
29 / 32
Algorithmique et Analyse d’Algorithmes
Garantir des coûts logarithmiques
Les B-arbres
Structure
Similaire à un ABR mais :
I chaque nœud peut porter i clés k1 < k2 < . . . ki avec t 6 i 6 2t
I un nœud à i clés possède i + 1 fils f0 , f1 , . . . fi
I tels que toute clé de fj est comprise entre kj et kj+1
I tous les sous-arbres ont la même hauteur
Exemple :
J O
C E H M S U
A B D F G I K L N P Q R T VW
30 / 32
Algorithmique et Analyse d’Algorithmes
Garantir des coûts logarithmiques
Insertion
1. Comme dans un ABR, on descend jusqu’à la feuille adaptée pour
accueillir la nouvelle clé. O(h × t)
I (à chaque nœud on parcourt la liste des clés pour trouver le bon fils)
2. On insère la nouvelle clé à sa place dans ce nœud. O(t)
3. Si après cette opération le nœud n’est pas plein (i 6 2t), ok.
4. Sinon (i = 2t + 1), on coupe ce nœud en deux : O(t)
I on obtient deux nœuds de t éléments chacun ;
I la clé médiane est insérée dans le nœud père, où elle sert à
« séparer » ces deux nœuds.
5. Si le nœud père est lui-même plein, on coupe à nouveau, autant de
fois qu’il le faut en remontant vers la racine. O(h × t)
6. La hauteur augmente quand on arrive à une racine pleine : l’arbre
« pousse en largeur d’abord, puis par la racine si nécessaire ».
31 / 32
Algorithmique et Analyse d’Algorithmes
Garantir des coûts logarithmiques
En résumé
Aujourd’hui
I Une structure dynamique est un TAD qui maintient des propriétés
I Un Arbre Binaire de Recherche permet de maintenir un ensemble
trié à moindre coût
I Les coûts de recherche, insertion et suppression restent linéaires au
pire, mais ils sont logarithmiques en moyenne
I On peut garantir un coût logarithmique en enrichissant ou en
généralisant la structure
La prochaine fois
I Arbre partiellement ordonné
I Structure de tas
I Application à la FAP
I Algorithmes gloutons 32 / 32
