Algorithmique

Alexandre Duret-Lutz
[email protected]

2 août 2010

A. Duret-Lutz Algorithmique 1 / 60
 Troisième partie III

Structures de données
1 Types abstraits, structures de Tables de hachage
données Fonctions de hachage

Représentations d'ensembles
Hachage avec chaînage
2
Adressage ouvert
Tableaux Arbres binaires de recherche
Listes Arbres rouge et noir
Piles et les Skip lists
Files de priorité Complexités des structures
3 Tableaux associatifs, de recherche présentées
structures de recherche

A. Duret-Lutz Algorithmique 2 / 60
Types abstraits, structures de données
1 Types abstraits, structures de données
2 Représentations d'ensembles
Tableaux
Listes
Piles et les
Files de priorité
3 Tableaux associatifs, structures de recherche
Tables de hachage
Fonctions de hachage

Hachage avec chaînage

Adressage ouvert

Arbres binaires de recherche

Arbres rouge et noir
Skip lists
Complexités des structures de recherche présentées
A. Duret-Lutz Algorithmique 3 / 60
Types abstraits et structures de données

Un type abstrait est une spécication mathématique d'un ensemble

de données et de l'ensemble des opérations qu'on peut y eectuer.
C'est un contrat qu'une structure doit implémenter.
Par exemple le type abstrait  Pile  peut être réalisé (implémenté)
avec une structure de liste simplement chaînée ou avec un tableau.
Pour décrire un algorithme, on peut n'utiliser que des types abstraits.
L'utilisation d'un objet pile spécie clairement les comportements
attendus.
Avant d'implémenter l'algorithme il faudra faire le choix d'une
structure de données pour le type abstrait.
La complexité des opérations sur un type abstrait peut dépendre de
son implémentation.

A. Duret-Lutz Algorithmique 4 / 60
Représentations d'ensembles
1 Types abstraits, structures de données
2 Représentations d'ensembles
Tableaux
Listes
Piles et les
Files de priorité
3 Tableaux associatifs, structures de recherche
Tables de hachage
Fonctions de hachage

Hachage avec chaînage

Adressage ouvert

Arbres binaires de recherche

Arbres rouge et noir
Skip lists
Complexités des structures de recherche présentées
A. Duret-Lutz Algorithmique 5 / 60
Des représentations d'ensembles de valeurs
Séquences
Tableau, vecteur (array, vector )
Liste (list )

Pile (stack )
File (queue )

File de priorité (priority queue ).

File à double entrée (deque, pronounce like deck )
Tableaux associatifs, structures de recherche
Table de hachage (hash table )
Arbre binaire de recherche équilibré (self-balancing binary serach
tree )
Liste à enjambement (skip list )
Diagramme de décision binaire (binary decision diagram )

On choisit une structure de donnée en fonctions des opérations qu'on

a besoin de faire sur l'ensemble représenté et de la complexité des
opérations correspondantes sur la structure de donnée.
A. Duret-Lutz Algorithmique 6 / 60
Des opérations sur les ensembles
v ←Access(S ,k ) Retourne la valeur du k e élément.
p ←Search(S ,v ) Retourne un pointeur (ou indice) sur un élément de
S dont la valeur est v .

Insert(S ,x ) Ajoute l'élément x à S .

Delete(S ,p) Eace l'élément de S à la position (pointeur ou indice)
p.

v ←Minimum(S ) Retourne le minimum de S .

v ←Maximum(S ) Retourne le maximum de S .

p ←Successor(S ,p ) Retourne le successeur (la plus petite valeur

0

supérieure) dans S de l'élément indiqué par p.

p ←Predecessor(S ,p ) Devinez.
0

Bien sûr il nous arrive aussi de vouloir trier une séquence, concaténer
(union) deux ensembles, ou à l'inverse en couper un en deux, etc.
A. Duret-Lutz Algorithmique 7 / 60
Tableaux

On ne les présente plus...

tableau tableau
opération non trié trié
v ←Access(S , k ) Θ(1) Θ(1)
p ←Search(S , v ) O(n ) O(log n )
Insert(S , x ) Θ(1) O(n )
Delete(S , p) Θ(1) 1
O(n )
v ←Minimum(S ) Θ(n) Θ(1)
v ←Maximum(S ) Θ(n) Θ(1)
p ←Successor(S , p ) Θ(1)
0
Θ(n)
p ←Predecessor(S , p ) Θ(1)
0
Θ(n)

1. L'ordre n'important pas on remplace l'élément supprimé par le dernier du

tableau.
A. Duret-Lutz Algorithmique 8 / 60
Tableaux dynamiques (1/2)
Leur taille peut varier.
Besoin de faire realloc() en C quand il n'y a plus de cases libres.
En C++ std::vector fait le realloc() lui-même. La réallocation
d'un tableau demande Θ(n) opérations car il faut le copier.
L'insertion, normallement en Θ(1), devient en Θ(n) quand cette
réallocation est nécessaire.
On veut étudier la complexité amortie d'une insertion dans une
séquence d'insertions.
Lors d'une réallocation, on s'arrange pour allouer plusieurs nouvelles
cases d'un coup an que le surcoût de cette réallocation reste
marginal par rapport au nombre des insertions.
Plusieurs façons de choisir la nouvelle taille d'un tableau sont
possibles et donnent des complexités diérentes.
A. Duret-Lutz Algorithmique 9 / 60
Tableaux dynamiques (2/2)
On considère une insertion qui provoque une réallocation dans un
tableau de taille n, avec deux façons d'agrandir le tableau :
Agrandissement constant de k cases. Il y a donc une réallocation
toutes les k cases : le côut moyen des k dernières insertions est
(k − 1)Θ(1) + 1Θ(n)
= Θ(n)
k

Doublement de la taille du tableau. Depuis la dernière réallocation a

il y a eu n/2 − 1 insertions en Θ(1) puis une insertion en Θ(n). Le
côut moyen des n/2 dernières insertions est
(n/2 − 1)Θ(1) + 1Θ(n) Θ(n) + Θ(n)
= = Θ(1)
n /2 n

On parle de complexité en  Θ(1) amorti  quand l'opération est en

Θ(1) la plupart du temps, et que le surcoût des cas lents peut être
étalé (amorti) sur les cas où l'opération est rapide.
A. Duret-Lutz Algorithmique 10 / 60
Listes
On distingue surtout les liste simplement chaînées (où l'on ne connaît
que l'élément suivant) des listes doublement chaînées (où l'on
connaît aussi l'élément précédent).
liste simpl.ch. liste doubl.ch.
opération non triée triée non triée triée
v ←Access(S , k ) O(n ) O(n ) O(n ) O(n )
p ←Search(S , v ) O(n ) O(n ) O(n ) O(n )
Insert(S , x ) Θ(1) O(n) Θ(1) O(n)
Delete(S , p) O(n) 1 O(n) 1 Θ(1) Θ(1)
v ←Minimum(S ) Θ(n) Θ(1) Θ(n) Θ(1)
v ←Maximum(S ) Θ(n) Θ(1) Θ(n) Θ(1)
p ←Successor(S , p ) Θ(1) Θ(1)
0
Θ(n) Θ(n)
p ←Predecessor(S , p ) Θ(1)
0
Θ(n) O(n ) Θ(n)
1. En vrai on s'arrange pour connaître l'élément précédent et rester en Θ(1).
A. Duret-Lutz Algorithmique 11 / 60
Piles et les
Pile (stack ) Séquence dans laquelle les insertions et suppressions
sont toujours faites à une extrémité (toujours la même). Insert() et
Delete() sont généralement appelés Push() et Pop(). LIFO
Généralement implémentée au dessus d'un tableau. Ajout et
suppression en queue en Θ(1).
File (queue ) Séquence dans laquelle les insertions sont toujours faites
à la même extrémité, et les suppressions à l'autre. Insert() et
Delete() sont généralement appelés Push() et Pop(). FIFO
Généralement implémentée au dessus d'une liste simplement
chaînée. Ajout en queue en Θ(1), suppression en tête en Θ(1).
File à double entrée (deque ) Les insertions et suppressions peuvent
être eectuées à l'une ou l'autre des extrémités.
Peut être implémentée au dessus d'une liste doublement
chaînée. Ajouts et suppressions en Θ(1).
A. Duret-Lutz Algorithmique 12 / 60
Files bornées et tableaux circulaires
Si la taille d'une le (à simple ou double entrée) est bornée, elle peut
être implémentée ecacement par un tampon circulaire.
5 1 3 7 2 8
tail head

Dans ce cas l'accès à la k e se fait en Θ(1) au lieu de Θ(n) sur une

liste.
Access(S , k ) = A[(head + k − 1) mod n]
En contrepartie, Insert() et Erase() au rang r deviennent en
O(min(r , n − r )) au lieu O(1).

Comment étendre ce schéma à des les non bornées ?

A. Duret-Lutz Algorithmique 13 / 60
Files non-bornées et tableaux circulaires
Ajouter un élément dans un tableau circulaire plein.
1re approche Augmenter la taille du tableau. En pratique : nouvelle
allocation plus copie. L'insertion devient en Θ(n) quand cela arrive.
Mais la complexité peut rester en  Θ(1) amorti .
2e approche Gérer un tableau circulaire de tableaux circulaires de
taille constante. Seules les extrémités ne sont pas pleines.
head tail
• • •

5 1 3 7 2 8 2 5 3 9 0 4 9 4 2

tail head tail head head tail

Encore du  Θ(1) amorti  car il faut parfois réallouer l'index, mais
c'est plus rare. C'est l'implémentation de std::deque en C++.
A. Duret-Lutz Algorithmique 14 / 60
Files de priorité
L'élément retiré d'une le est toujours le plus grand. On parle parfois
de  Largest In, First Out  (ne pas confondre avec LIFO = Last In
First Out ).

Si la le de priorité est réalisée à l'aide d'une liste triée, alors on

a Push() en O(n) et Pop() Θ(1).
Si la le de priorité est réalisée à l'aide d'un tas, alors on a
Push() en O(log n) et Pop() O(log n).
On sait faire un Pop() sur un tas : comme dans le tri par tas on
retire la première valeur du tas, on la remplace par la dernière, et
on appelle Heapify() pour rétablir la structure de tas.
Comment faire un Push() ?
A. Duret-Lutz Algorithmique 15 / 60
Files de priorité : Insertion dans un tas

Entrée : Un tableau A[1..m] respectant la propriété de tas, une

valeur v à y insérer,
Sortie : Un tableau A[1..m + 1] respectant la propriété de tas et
contenant v .
HeapInsert(A, m, v )
1 i ←m+1
2 A[i ] ← v
3 while i > 1 and A[Parent (i )] < A[i ] do
4 A[Parent (i )] ↔ A[i ]

5 i ← Parent (i )

Au pire on fait un nombre d'opérations proportionnel à la hauteur du

tas, donc T (n) = O(log n).

A. Duret-Lutz Algorithmique 16 / 60
Tableaux associatifs, structures de recherche
1 Types abstraits, structures de données
2 Représentations d'ensembles
Tableaux
Listes
Piles et les
Files de priorité
3 Tableaux associatifs, structures de recherche
Tables de hachage
Fonctions de hachage

Hachage avec chaînage

Adressage ouvert

Arbres binaires de recherche

Arbres rouge et noir
Skip lists
Complexités des structures de recherche présentées
A. Duret-Lutz Algorithmique 17 / 60
Tableau associatif
Un tableau associatif (ou encore dictionnaire ou table d'association)
est un type abstrait pouvant être vu comme un généralisation de la
notion de tableau à des indices non consécutifs et pas forcément
entiers. Les indices sont ici appelés des clefs. Les clefs peuvent être
associées à des valeurs  satellites , exactement comme dans les tris.
Opérations typiques :
Ajout
Suppression
Recherche (par clef).
Modication (des données satellites).
La présentation des structures ne montre pas les données satellites. Il
faut supposer qu'elles accompagnent la clef mais n'interviennent pas
dans les opérations sur les clefs (e.g. comparaisons).
A. Duret-Lutz Algorithmique 18 / 60
Tables de hachage
Le but : représenter un ensemble F d'éléments quelconques (les
clefs), disons un sous-ensemble d'un domaine K. On veut tester
rapidement l'appartenance à cet ensemble.
Si K = N, alors on peut utiliser un tableau pour représenter F . Par
exemple n ∈ F ssi A[n] 6= 0 (le premier indice du tableau A est 0).
Cependant si max(F) est grand le tableau va occuper beaucoup de
place même si |F| est petit.
On s'inquiète aussi du cas où K est autre chose que N.
L'idée : pour F ⊆ K quelconque, on se donne une fonction
f : K 7→ [[0, m ]]. On teste alors l'appartenance avec x ∈ F ssi

A[f (x )] 6= 0.

Ce test est correct si la fonction f est injective (de telles fonctions

n'existent que si m − 1 ≥ |K|).
Ces tests l'appartenance sont en Θ(1).
A. Duret-Lutz Algorithmique 19 / 60
Injectivité dans K ou dans F
Soit F = {"chat", "chien", "oie", "poule"} à ramener dans
[[0, 30]].
Prenons comme fonction f (mot ) = (mot [2]−'a').
Cette fonction distingue les mots de F par leur i []
A i

troisième lettre. 0 chat

f (chat) = 0 1 /
f (chien) = 8 2 /
f (oie) = 4 3 /
f (poule) = 20 4 oie
Mais elle n'est pas injective dans K : ..
. /
f (loup) = 20 8 chien
On s'en sort en représentant l'élément dans le tableau : ..
x ∈ F ssi A[f (x )] = x .
. /
Pour l'injectivité dans F on veut donc seulement 20 poule
..
m ≥ |F|. . /
A. Duret-Lutz Algorithmique 20 / 60
Rareté des fonctions injectives
Les fonction f injectives ne sont pas faciles à trouver  par hasard .
Soit un ensemble F de n = 30 éléments qu'on cherche à représenter
dans un tableau de m = 40 entrées.
Il existe 4030 ≈ 1048 fonctions de F dans [[0, m − 1]]. Parmi ces
fonctions, seules 40 · 39 · · · 11 = 40!/10! ≈ 2.1041 sont injectives. On
a donc une chance sur 5 millions de trouver une fonction injective
pour cet exemple.
Exemple typique de la rareté des fonctions injective : le paradoxe des
anniversaires. Il sut de réunir 23 personne pour avoir plus d'une
chance sur deux que deux de ces personnes soient nées le même jour.
Pourtant la fonction anniversaire a 365 choix possibles !
http://fr.wikipedia.org/wiki/Paradoxe_des_anniversaires

A. Duret-Lutz Algorithmique 21 / 60
GPerf

Lorsque l'ensemble F est connu à l'avance, il est possible de trouver

(algorithmiquement) une fonction f qui transforme F en [[0, m]] avec
m − 1 ≥ F sans doublons. On parle de fonction de hachage parfaite.

Une telle fonction est minimale si m − 1 = |F|.

L'outil GNU gperf est dédié à cette tâche pour des ensembles de
chaînes. Il prend en entrée une liste de mots à reconnaître, une valeur
m , et fournit en sortie un chier C contenant la fonction f et le

tableau A avec les éléments dans l'ensemble rangés aux places

indiquées par f .
D'autres outils existent, p.ex. CMPH (C Minimal Perfect Hashing
Library).

A. Duret-Lutz Algorithmique 22 / 60
Hachage avec chaînage
Lorsqu'une fonction de hachage parfaite n'est pas disponible (par
exemple m est trop petit, ou bien l'ensemble F est sans cesse
modié) deux éléments peuvent devoir être rangés au même indice et
l'on doit gérer ces collision.
i []
A i
Comme dans le tris par paquet, la façon la plus 0 chat
simple et de conserver une liste de valeurs 1 /
possibles pour chaque indice du tableau. 2 /
Reprenons F = {"chat", "chien", "oie", 3 /
"poule", "loup"}.
4 oie
..
Alors x ∈ F ssi Search(A[f (x )], x ) 6= 0. . /
La recherche ne se fait plus en Θ(1) parce qu'il 8 chien
..
faut parcourir une liste. Dans le pire des cas, la . /
liste fait n = |F| éléments, dans le meilleur on 20 poule, loup
espère n/m éléments. ..
A. Duret-Lutz Algorithmique
. / 23 / 60
Hachage avec chaînage : hachage uniforme

On parle de hachage uniforme simple lorsqu'on suppose que la

fonction de hachage f répartit les clefs uniformément dans [[0, m − 1]].
Sous l'hypothèse de hachage uniforme, la recherche se fait en
Θ(1 + n/m).

Si l'on s'arrange pour que la taille m de la table de hachage soit

proportionelle à n. Alors n = O(m), n/m = O(1), et la recherche se
fait en Θ(1).
L'insertion se fait alors en Θ(1) amorti (car réallocation) et la
suppression en Θ(1). La réallocation demande de changer de fonction
de hachage (puisque m change) et de déplacer tous les éléments de
F à leur nouvelle place dans le tableau.

A. Duret-Lutz Algorithmique 24 / 60
Exemples de fonctions de hachage : La division
f (x ) = x mod m
On évitera une puissance de deux telle que m = 256 car cela revient
à ignorer les 8 bits les plus faibles de x , souvent ceux qui varient le
plus. On conseille de prendre pour m un nombre premier assez éloigné
d'une puissance de 2.
Par exemple pour représenter 3000 éléments avec une moyenne de
deux éléments par liste, on peut choisir m = 1543.
Une implémentation de table de hachage par cette méthode contient
typiquement une liste de nombres premiers à utiliser au fur et à
mesure que la table s'agrandit. Par exemple si on double la taille de
la table chaque fois qu'on la réalloue : 53, 97, 193, 389, 769, 1543,
3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, etc.
La classe std::hash_map du C++ fait cela avec la fonction
f (x ) = g (x ) mod m où g est fournie par l'utilisateur (pour convertir

n'importe quel type en entier) et m suit la liste ci-dessus.

A. Duret-Lutz Algorithmique 25 / 60
Ex. de fonctions de hachage : La multiplication
f (x ) = bm(xa mod 1)c où xa mod 1 = xa − bxac et 0 < a < 1.
On vise un choix de a qui distribue bien les valeurs de xa mod 1
dans [[0, 1[[.
Ici le choix de m n'a pas d'importance, autrement dit on peut faire
croître la taille du tableau sans contrainte.
Choisir m = 2p permet de faire des calculs entiers. Si la machine
possède des entiers de w bits, on calcule ba · 2w c × k , ce qui nous
donne un résultat de 2w bits dont la deuxième moitié représente la
partie fractionnaire. On garde les p premiers bits de cette moitié.
Peut être vu comme une généralisation de la division : a = 1/b, mais
en pratique plus rapide (multiplication moins coûteuse).
Choix de a ? Knuth suggère une valeur de a pas trop√ éloignée d'un
nombre irrationnel (par exemple le nombre d'or ( 5 − 1)/2) et tel
que a · 2w et 2w soit premiers entre eux.
A. Duret-Lutz Algorithmique 26 / 60
Eet d'avalanche pour les fonctions d'hachage
L'eet d'avalanche est une propriété désirable en cryptographie, mais
elle est aussi utile pour une table de hachage.
Si y = f (x ) est la valeur de hachage pour x , on souhaite qu'une
petite modication de x induise une grande modication de y .
Le critère d'avalanche stricte (Strict Avalanche Criterion) :  pour
toute inversion d'un seul bit en entrée alors chaque bit en sortie a une
chance sur deux d'être modié .
MD5 est une fonction de hachage (coûteuse) qui respecte ce critère.
~ % echo "Bonjour tout le monde" | md5sum -
52e1281d5b6885323e40a9789e1a8c8d -
~ % echo "bonjour tout le monde" | md5sum -
a6fabe06142f2bb0ed6b996a9cd50221 -
Attention, aujourd'hui on sait générer rapidement (quelques secs sur une

machine de bureau) une paire de messages qui ont la même clef MD5.
A. Duret-Lutz Algorithmique 27 / 60
Autre exemple de fonction de hachage pour entier

/* sizeof int == 32 */
int wang32_hash(int key)
On peut combiner cette fonction
{ plusieurs fois pour hacher quelque
key += ~(key  15); chose de plus gros. Par exemple
key ^= (key  10);
wh(wh(wh(s[0])^s[1])^s[2])
key += (key  3);
key ^= (key  6); L' avalanche  prend plus de
key += ~(key  11); sens lorsque la fonction est
key ^= (key  16);
return key;
appliquée ainsi plusieurs fois.
}
Comment vérier une telle fonction ? Exercice : tracez les 30000
premières valeurs de y = wh(x ) avec Gnuplot. On voit des motifs de
 zones vierges  apparaître. Tracez y = wh(wh(x )) : ça paraît
beaucoup plus aléatoire.
A. Duret-Lutz Algorithmique 28 / 60
y = wh(x ) et y = wh(wh(x ))

A. Duret-Lutz Algorithmique 29 / 60
Adressage ouvert
Tous les éléments sont stockés dans la table, sans liste ni pointeurs.
Résolution des collisions sans chaînage : on doit juste examiner
plusieurs positions pour trouver la bonne.
Une fonction de hachage pour une clef x prend aussi une itération i .
Pour insérer une valeur, on teste si A[f (x , 0)] est libre, sinon
A[f (x , 1)], sinon A[f (x , 2)], etc. On dit qu'on sonde diérentes

positions.
La fonction f doit être telle que f (x , i ) parcourt [[0, m[[ lorsque i
parcourt [[0, m[[. L'ordre de parcours dépend de la clef x .
La recherche se fait de la même façon jusqu'à ce qu'on tombe sur
une case vide.
Danger à la suppression : pourquoi ne peut-on pas remplacer vider la
case bêtement ?
A. Duret-Lutz Algorithmique 30 / 60
Fonctions de hachage pour adressage ouvert

Sondage linéaire h(x , i ) = (h0 (x ) + i ) mod m

Problème : plus une séquence d'emplacements occupés est longue,
plus elle risque d'être allongée, augmentant les temps de recherche.
(On peut chercher à remplacer +i par +ci si c et m sont premiers
entre eux, mais cela change rien : des séquences de cases espacés
de c occupées seront de plus en plus longues.)
Sondage quadratique h(x , i ) = (h0 (x ) + c1 i + c2 i 2 ) mod m
C'est mieux, mais ici aussi, le premier sondage détermine la
séquence toute entière. h(x , 0) = h(x 0 , 0) =⇒ h(x , i ) = h(x 0 , i ).
Double hachage h(x , i ) = (h1 (x ) + ih2 (x )) mod m
Cette fois-ci h(x , 0) = h(x 0 , 0) ; (x , i ) = h(x 0 , i ).

A. Duret-Lutz Algorithmique 31 / 60
Complexité des recherches dans l'adressage ouvert

Le nombre de sondages attendus dans une recherche infructueuse est

1/(1 − n/m) si l'on suppose le hachage uniforme (i.e., toutes les
séquences de parcours de [[1, m[[ peuvent apparaître avec la même
probabilité).
De même insérer demande 1/(1 − n/m) sondages en moyenne.
Si n/m est constant, on en déduit que l'insertion, la recherche et la
suppression sont en Θ(1). En pratique m n'est bien sûr pas changé
aussi souvent que n.
L'intérêt de l'adressage ouvert sur le chaînage est de supprimer les
pointeurs. Cela donne plus de mémoire et permet de stocker des
tables plus grandes (plus grand m). La contrepartie : c'est plus lent
en pratique.

A. Duret-Lutz Algorithmique 32 / 60
Taille critique des tableaux de hachage

L'étude du paradoxe des anniversaires nous apprend que si la table de

hachage peut représenter N entrées le nombre d'éléments nécessaires
pour avoir une probabilité p de collisions est d'environ
1
s  
( , )≈ 2N ln
1−p
n p N

On retiendra surtout :
√ √
n (0.5, N ) ≈ 1.177 N = Θ( N )
√
C'est-à-dire qu'a partir de N valeurs dans une table de hachage
(hachée uniformément) on a à peu près une chance sur deux d'avoir
une collision.
A. Duret-Lutz Algorithmique 33 / 60
Arbres binaires de recherche
Un arbre binaire dont les n÷uds sont étiquetés par des valeur est dit
de recherche si pour un n÷ud r étiqueté par v toutes les étiquettes
du sous-arbre gauche de r sont ≤ v , et toutes celles du du sous-arbre
droit de r sont ≥ v .
4
7 6
8
4 9
7 9
6 8 10 10
Tous les ABR ne sont pas équilibrés. La complexité de la recherche
est O(h) avec h la hauteur de l'arbre. Recherche du minimum et
maximum en O(h) aussi.
A. Duret-Lutz Algorithmique 34 / 60
Ordre inxe
Parcourir l'arbre dans l'ordre inxe permet de visiter les clefs dans
l'ordre.
InxPrint(T , z )
1 if LeftChild(z ) 6= NIL then
2 InxPrint(T , LeftChild (z ))
3 print key (z )
4 if RightChild(z ) 6= NIL then
5 InxPrint(T , RightChild (z ))
PrexPrint(T , z ) SuxPrint(T , z )
1 print key (z ) 1 if LeftChild(z ) 6= NIL then
2 if LeftChild(z ) 6= NIL then 2 InxPrint(T , LeftChild (z ))
3 InxPrint(T , LeftChild (z )) 3 if RightChild(z ) 6= NIL then
4 if RightChild(z ) 6= NIL then 4 InxPrint(T , RightChild (z ))
5 InxPrint(T , RightChild (z )) 5 print key (z )
A. Duret-Lutz Algorithmique 35 / 60
Insérer dans un ABR est facile
Entrée : un ABR T et un enregistrement z à y ajouter
Sortie : l'ABR T contenant z
TreeInsert(T , z )

1 y ← NIL
2 x ← Root (T )
3 while x 6= NIL do

4 y ← x
5 if key (z ) < key (x )

6 then x ← LeftChild (x ) ( ) = O(h)

T h
7 else x ← RightChild (x )

8 Parent (z ) ← y
9 if y = NIL then

10 Root (T ) ← z
11 else

12 if key (z )< key (y )

13 then LeftChild (y ) ← z

14 else RightChild (y ) ← z
A. Duret-Lutz Algorithmique 36 / 60
Suppression (1/2)

Trois cas à considérer :

La suppression d'une feuille de l'arbre : facile.
La suppression d'un n÷ud qui n'a qu'un ls : facile aussi.
La suppression d'un n÷ud avec deux ls : on le remplace par son
successeur, i.e. le minimum de l'arbre droit, qui aura été à son
tour supprimé de sa place plus bas dans l'arbre.

A. Duret-Lutz Algorithmique 37 / 60
Suppression (2/2)
TreeDelete(T , z )
1 x ← NIL
2 if LeftChild (z ) = NIL or RightChild (z ) = NIL
3 then y ← z
4 else y ← TreeSuccessor (z )
5 if LeftChild (y ) 6= NIL
6 then x ← LeftChild (y )
7 else x ← RightChild (y )
8 if x 6= NIL then Parent (x ) ← Parent (y )
9 if Parent (y ) = NIL then
10 Root (T ) ← x

11 else
12 if y = LeftChild (Parent (y ))
13 then LeftChild (Parent (y )) ← x
14 else RightChild (Parent (y )) ← x
15 if y 6= z then key (z ) ← key (y )
A. Duret-Lutz Algorithmique 38 / 60
Le problème des ABR
Insertion, Suppression, Recherche, Prédécesseur, Successeur,
Minimum et Maximum s'eectuent tous en O(h) et
blog nc ≤ h ≤ n
| {z } |{z}
cas équilibré cas déséquilibré

Donc ces algorithmes sont donc en O(n)...

On peut cependant montrer que la hauteur moyenne d'un ABR
construit aléatoirement (on fait la moyenne de tous les ordres
d'insertion possible pour une séquence donnée) est en Θ(log n).
On peut modier les opérations d'insertion et de suppression pour
essayer de préserver la nature équilibrée d'un arbre, et donc améliorer
les performances de ces algorithmes.
A. Duret-Lutz Algorithmique 39 / 60
Arbres rouge et noir
Ce sont des ABR dans lesquels chaque n÷ud possède un bit
indiquant sa couleur : rouge ou noir. Des contraintes sur les couleurs
empêchent qu'une branche soit plus de deux fois plus longue qu'une
autre. L'arbre est alors approximativement équilibré.
Les contraintes :
Chaque n÷ud est soit rouge, soit noir.
La racine et les feuilles (NIL) sont noires.
Les deux ls d'un n÷ud rouge sont noirs.
Tous les chemins reliant un n÷ud à une feuille (de ses
descendants) contient le même nombre de n÷uds noirs.
La hauteur noire d'un n÷ud x , notée hn(x ) est le nombre de n÷uds
noirs entre x (exclu) et une feuille (inclue).
A. Duret-Lutz Algorithmique 40 / 60
Exemple d'ARN

12

7 20

2 10 NIL NIL

NIL 5 8 11

NIL NIL NIL NIL NIL NIL

A. Duret-Lutz Algorithmique 41 / 60
Propriété
Un arbre rouge et noir avec n n÷uds internes possède une hauteur au
plus égale à b2 log(n + 1)c.
Si on fait disparaître les n÷uds rouges, les n÷uds internes noirs
ont entre 2 et 4 ls, et toutes les branches de l'arbre ont toutes
la même longueur h0 .
La hauteur de l'arbre complet est h ≤ 2h0 car il ne peut pas y
avoir plus de n÷uds rouges que de n÷uds noirs sur une branche.
Le nombre de feuilles des deux arbres est n + 1.
On a donc
n +1 ≥ 2 log(n+1) ≥ h0 ≥ h/2 =⇒ h ≤ 2 log(n+1)
h 0
=⇒
D'autre part la longueur minimale d'une branche est log(n + 1)
(moitié de la hauteur). En conséquence, Search, Minimum,
Maximum, Successor et Predecessor sont en Θ(log n). Ce n'est pas
évident pour Insert et Delete.
A. Duret-Lutz Algorithmique 42 / 60
Rotations
Insérer avec TreeInsert ne préserve pas les propriétés des ARN. On
peut rétablir ces propriétés en changeant les couleurs des n÷uds et en
eectuant des rotations localement.

p p

y x
RightRotate
x γ α y

LeftRotate
α β β γ

Ces rotations préservent l'ordre inxe.

A. Duret-Lutz Algorithmique 43 / 60
Rotation gauche
LeftRotate(T , x )
1 y ← RightChild (x )
2 β ← LeftChild (y )
3 RightChild (x ) ← β
4 if β 6= NIL then Parent (β) ← x
5 p ← Parent (x )
6 Parent (y ) ← p
7 if p = NIL ( ) = Θ(1)
T n

8 then Root (T ) ← y
9 else if x = LeftChild (p)
10 then LeftChild (p) ← y
11 else RightChild (p) ← y
12 LeftChild (y ) ← x
13 Parent (x ) ← y
A. Duret-Lutz Algorithmique 44 / 60
Insertion dans un ARN

On insère le n÷ud dans l'arbre avec la couleur rouge. La

propriété  les ls d'un n÷uds rouge sont noirs  peut être
violée chez le père du n÷ud inséré.
On corrige cette violation en la faisant remonter par
recolorations, jusqu'à pouvoir la corriger par rotation (et
peut-être recoloration).

A. Duret-Lutz Algorithmique 45 / 60
Insertion de 9

12

7 20

2 10
5 8 11
9

A. Duret-Lutz Algorithmique 46 / 60
Insertion de 9

12

7 20

2 10
5 8 11
9

A. Duret-Lutz Algorithmique 46 / 60
Insertion de 9

12

10 20

7 11
2 8
5 9

A. Duret-Lutz Algorithmique 46 / 60
Insertion de 9

10

7 12

8 2 11 20
5 9

A. Duret-Lutz Algorithmique 46 / 60
Trois cas à gérer : cas 1
Le père et l'oncle sont tous les deux rouges.
(Dans tous ces cas, les lettres grecques représentent des sous-arbres
avec la même hauteur noire.)

C C

inverser les couleurs

A D A D
de A, C et D
α B δ ε α B δ ε

β γ β γ

Continuer à partir du grand-père si l'arrière grand-père est rouge.

A. Duret-Lutz Algorithmique 47 / 60
Trois cas à gérer : cas 2
Le père est rouge, l'oncle est noir, et le n÷ud courant n'est pas dans
l'axe pèregrand-père.

C C

rotation
A δ B δ

α B A γ

β γ α β
On eectue la rotation qui convient pour aligner ls, père, et
grand-père. Le problème n'est pas résolu, mais on l'a transformé en
 cas 3 .
A. Duret-Lutz Algorithmique 48 / 60
Trois cas à gérer : cas 3

Le père est rouge, l'oncle est noir, et le n÷ud courant est dans l'axe
pèregrand-père.

C B

rotation +
δ
inversion B et C
B A C

A γ α β γ δ

α β
Après cette correction l'arbre est correct.

A. Duret-Lutz Algorithmique 49 / 60
Complexité de l'insertion

On ajoute le n÷ud avec TreeInsert. Θ(h)

On applique le cas 1 au plus h/2 fois. O(h)
On applique le cas 2 au plus 1 fois. O(1)
On applique le cas 3 au plus 1 fois. O(1)
On nal, on eectué Θ(h) = Θ(log n) opérations.

A. Duret-Lutz Algorithmique 50 / 60
RBTreeInsert
RBTreeInsert(T , z )
1 TreeInsert (T , z )
2 Color (z ) ← red
3 while Color (Parent (z )) = red do
4 if Parent (z ) = LeftChild (Parent (Parent (z ))) then
5 uncle ← RightChild (Parent (Parent (z )))

6 if Color (uncle ) = red then



7


Color (Parent (z )) ← black


8 cas 1

Color (uncle ) ← black

9 z ← Parent (Parent (z ))


10


Color (z ) ← red

11 else if z = RightChild (Parent (z )) then


12 cas 2

z ← Parent (z )

13 LeftRotate (T , z )

14 else


15


Color (Parent (z )) ← black
cas 3

16 Color (Parent (Parent (z ))) ← red

17


RightRotate (T , Parent (Parent (z )))

18 else comme le  then , en échangeant  Left  et  Right 
19 Color (Root (T )) ← black
A. Duret-Lutz Algorithmique 51 / 60
La suppression

RBTreeDelete() peut aussi être eectué en Θ(log n).

Si le n÷ud à supprimer est rouge, TreeDelete peut être utilisé.
S'il est noir, une procédure de correction de l'arbre doit être appelée
ensuite : il y a cette fois 4 cas à distinguer.

A. Duret-Lutz Algorithmique 52 / 60
Conclusion sur les ARN
Les arbres rouges et noir permettent d'eectuer toutes ces opérations
en Θ(log n) :
Insert
Delete
Minimum
Maximim
Successor
Predecessor
De plus Search se fait en O(log n).
L'intérêt sur les tables de hachage est surtout que les éléments sont
conservés triés.
Cette structure de donnée est celle utilisée par std::map en C++.
A. Duret-Lutz Algorithmique 53 / 60
Skip list
Skip list = liste à enjambement.
Généralisation de la structure de liste triée.
Il s'agit d'une structure probabiliste, ayant la même complexité en
moyenne que les arbres rouges et noirs (i.e. Θ(log n) en moyenne
pour toutes les opérations), avec de grandes chances d'atteindre
cette moyenne, et plus simple à implémenter.
Exemple de skip list à deux niveaux :
• • •
1 • 2 • 3 • 4 • 5 • 6 7 • 8 • 9
•
On localise d'abord l'intervale de l'élément recherché dans la liste de
plus haut niveau, puis on descend dans la liste inférieure pour aner
la recherche.
A. Duret-Lutz Algorithmique 54 / 60
Skip list a deux niveaux
Où doit-on connecter les deux niveaux ?
On veut un espacement régulier, mais avec quel espacement ?
Si on note t1 et t2 la taille des deux listes. Le temps de recherche
d'un élément dans la skip list est en O(t1 + t2 /t1 ). Cette somme est
minimale lorsque
√ les termes sont égaux : t1 = t2 /t1 autrement dit
quand t1 = t2 .
√
n

• •
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9
√ √ √
n n n
n
√ √
Le coût de recherche est alors de l'ordre de 2 n = O( n ).

A. Duret-Lutz Algorithmique 55 / 60
Skip list à plus de 2 niveaux
√
2 listes : 2 · n
√
3 listes : 3 · n 3

√
k listes : k ·
k
n
√
log n listes : log n · = log n · e ln n
= log n · e ln 2 = 2 log n
1
log n log n
n

•
• •
1 • • 5 • • 9
• 2 • 3 • 4 • • 6 • 7 • 8 •

L'exemple ci-dessus est une skip list idéale. Les recherches y sont
toujours en Θ(log n).
Comment réaliser l'insertion ?
A. Duret-Lutz Algorithmique 56 / 60
Algorithme d'insertion dans une skip list
Soit x à insérer dans une skip list.
Eectuer une recherche pour trouver où insérer x dans la liste du
bas (niveau 0).
Insérer x dans la liste du bas.
Avec une probabilité 1/2, ajouter x à la liste de niveau 1.
Si x a été ajouté au niveau 1, avec une probabilité 1/2, ajouter x
à la liste de niveau 2.
Continuer pour tous les niveaux.
Au nal x apparaît
au niveau 0 avec une probabilité 1
au niveau 1 avec une probabilité 1/2
au niveau 2 avec une probabilité 1/4
au niveau k avec une probabilité 2−k
A. Duret-Lutz Algorithmique 57 / 60
Analyse du coût de la recherche (1/2)
On évalue le côut de la recherche en comptant les déplacement à
partir de la n : à partir du niveau 0, il faut remonter jusqu'au niveau
k en se déplaçant vers la gauche quand on ne peut pas monter.

On note C (k ) le coût de monter de k niveaux et p = 1/2 la

probabilité d'avoir un niveau au dessus dans le n÷ud courant. Deux
cas peuvent se produire :
avec probabilité p on peut monter d'un niveau et il reste à
monter k − 1 niveaux (coût : 1 + C (k − 1) déplacements)
avec une probabilité 1 − p on ne peut pas monter : on se déplace
sur la gauche puis il reste à monter k niveaux (coût : 1 + C (k )
déplacements)
Autrement dit :
C (0) = 0

C (k ) = (1 − p )(1 + C (k )) + p (1 + C (k − 1))

A. Duret-Lutz Algorithmique 58 / 60
Analyse du coût de la recherche (2/2)

C (0) = 0
C (k ) = 1/p + C (k − 1) = k /p

C'est une borne supérieure du coût de monter n niveaux, car si on

atteint la tête de liste en allant trop à gauche la probabilité de
monter devient alors 1.
Notons L(n) la hauteur d'une skip list de n éléments. Le coût pour
remonter au dernier niveau est C (L(n) − 1).
Dans notre cas L(n) = log n. On a donc
(log n) − 1
 
T (n ) = O = O(log n)
p

A. Duret-Lutz Algorithmique 59 / 60
Complexités des structures de recherche présentées

table de arbre
opération hachage R. et N. skip list

p ←Search(S , v ) Θ(1) moy O(log n) O(log n) moy.

Insert(S , x ) Θ(1) am. Θ(log n) O(log n ) moy.
Delete(S , p) Θ(1) am. Θ(log n) Θ(1)
v ←Minimum(S ) Θ(n) Θ(log n) Θ(1)
v ←Maximum(S ) Θ(n) Θ(log n) Θ(1)
p ←Successor(S , p ) Θ(log n) Θ(1)
0
Θ(n)
p ←Predecessor(S , p ) Θ(log n) O(log n ) moy. ou Θ(1)
0
Θ(n)

am. = amorti ; moy. = en moyenne.

A. Duret-Lutz Algorithmique 60 / 60