Algorithmique

Cristina Sirangelo, ENS-Cachan

Préparation à l'option Informatique

de l'agrégation de mathématiques
 Plan
1. Analyse et complexité des algorithmes (S.Haddad)
2. Types abstraits et structures de données (suite)
3. Algorithmes de tri
4. Techniques classiques de conception d’algorithmes
5. Algorithmes de graphes
 Types abstraits et structures de données
• Les algorithmes opèrent sur des données (données en input, données auxiliaires)
• Aspect central de l’algorithmique: représentation et manipulation des données
• Deux niveaux de représentation:
‣ niveau abstrait ou logique (type abstrait de données)
‣ implémentation (structure de données)
• Séparation des deux niveaux : modularité et interface
‣ utiliser un objet ou une fonctionnalité par son interface abstraite, indépendamment des
détails de son implémentation
Type abstrait
‣ un ensemble d’objets
‣ des opérations qui les manipulent
Structure de données
‣ Représentation concrète des objets décrits par le type abstrait dans la mémoire d’un
ordinateur
‣ Implémentation des opérations sur cette représentation
Représentation des données: en terme de types élémentaires et d’autres types abstraits
(hiérarchie de types)
 Types abstraits et structures de données
• Piles

• Files

• Listes

• Arbres

• Graphes

• Dictionnaires
‣ Arbres binaires de recherche, tables de hachage, ...
• Files de priorité

• etc
 Dictionnaires et algorithmes de recherche
• Dictionnaire: un type abstrait de données qui permet de représenter et manipuler des
ensembles (typiquement ordonnés).

• Principales opérations: recherche d’un élément, insertion et suppression

• D’autres opérations typiques: fusion, scission

• Éléments de l’ensemble accessibles par un champ clef (identifiant) sur un domaine totalement
ordonné

• D’autres informations associées à chaque élément: schématisées par un seul autre champ
valeur, qui peut être d’un type complexe.
 Dictionnaires
Implémentations possibles
par Tableau (non-trié et trié)
par Liste (non-trié et trié)
par Table de Hachage
par Arbre Binaire de Recherche :
complexité des opérations de recherche/insertion/suppression:
• O(log n) cas moyen
• O(n) cas pire - dû au possible déséquilibre dans l’arbre (cas pire: arbre dégénéré en
une liste)

Arbres de recherche équilibrés:

• arbres de recherche qui respectent des propriétés d'équilibre entre la hauteur des
sous-arbres d’un noeud (évitent que l’arbre dégénère en une liste)
• la hauteur reste logarithmique dans le nombre de noeuds
• complexité de la recherche/insertion/suppression: O(log n) dans le cas pire
• les opérations de mise à jour (insertion/suppression) doivent maintenir la propriété
d'équilibre
 Arbres de recherche équilibrés

• Arbres AVL (Adelson-Velskii et Landis)

• Arbres a-b

• Arbres rouge-noir (ou bicolores)

 Rotations

Rappel: Soit Tclef un domaine totalement ordonné, et Tval un type pour les valeurs:
Arbre binaire de recherche (ABR) sur (Tclef, Tval):
un arbre binaire sur un domaine (Tclef, Tval) tel que pour tout sommet x
clefs dans le sous-arbre gauche de x < x. clef < clefs dans le sous-arbre droit de x
Rotations:

• des opérations de réorganisation “locale” des noeuds d’un ABR, qui préservent la propriété
d’ABR
• briques de base pour les opérations de rééquilibrage dans les ABR équilibrés
 Rotations

x y
rotation gauche
y x

A rotation droite C

B C A B
 Rotations
x z
rotation gauche-droite
y y x

z D

A A B C D

B C

x z
rotation droite-gauche
y x y
A z
D A B C D
B C

Toutes les opérations de rotation sur les arbre binaires peuvent être réalisées en temps O(1)
 Arbres AVL (Adelson-Velskii et Landis)
Pour un arbre binaire A et un sommet x de A :
A(x) : sous-arbre de A de racine x
Ag (x) : sous arbre gauche de A(x)
Ad (x) : sous-arbre droit de A(x)
Equilibre de x :
δ (x) = hauteur( Ag(x) ) - hauteur( Ad(x) )
( par convention la hauteur d’un arbre vide est -1 )

Arbre AVL: ABR tel que, pour tout sommet x de l’arbre δ(x) ∈ { -1, 0, 1 }

Proposition
Soit A un arbre AVL ayant n sommets et de hauteur h, alors:
log2 (n+1) ≤ h+ 1 ≤ 1,44 log2 (n+2)
 Hauteur d’un arbre AVL
Preuve.
1) L’arbre binaire de hauteur h ayant plus de sommets est l’arbre complet
#sommets de l’arbre complet: 1 + 2 + ...+ 2h = 2h+1 -1
n ≤ 2h+1 -1 h+ 1 ≥ log2 (n+1)

2) L’ arbre AVL de hauteur h ayant le nombre minimum de sommets (arbre de Fibonacci):

h= -1: arbre vide
h= 0 : arbre composé de la seule racine
h≥ 1: arbre composé d’une racine, un sous arbre de hauteur h-1 ayant un minimum de
sommets, et un sous arbre de hauteur h-2 ayant un minimum de sommets

N(h): nombre minimum de sommets d’un arbre AVL de hauteur h

N(-1) = 0, N(0) = 1, N(h) = 1 + N(h-1) + N(h-2) pour h ≥ 1 ( N(1) = 2 )

On pose F(h) = N(h) +1

F(0) =2, F(1) =3 F(h) = F(h-1) +F(h-2) pour h ≥ 2
 Hauteur d’un arbre AVL
F(0) =2, F(1) =3 F(h) = F(h-1) +F(h-2) pour h ≥ 2

F(h) est le nombre de Fibonacci d’indice h+ 3 , pour tout h ≥ 0

F(h)= 1 ( ph+3 - qh+3 ) >

1 ph+3 -1
p=
1+ √5
q=
1- √5
qh+3 < 1
√5 √5 2 2

1 ph+3 -1
n ≥ N(h) = F(h) -1 n+1 >
√5

h+ 3 < log p (n+2) + log p √5 ≤ (1/ log2 p) · log 2 (n+2) + 2 =1, 44 log 2 (n+2) + 2

h+ 1 < 1, 44 log 2 (n+2)

 Opérations de dictionnaire sur les arbres AVL

Recherche: algorithme habituel de recherche dans un ABR

Complexité O(h), et par la proposition ci-dessus:

➡ La recherche d’une clef dans un arbre AVL se fait en temps O(log n) dans le cas pire

Insertion/ Suppression: algorithme habituel plus rééquilibrage

Pour plus d’efficacité: dans chaque sommet x on stocke h(A(x))

 Insertion dans un arbre AVL
Deux phases:
1) descente de l’arbre (comme dans les ABR), création d’une nouvelle feuille (clef, valeur)

2) rééquilibrage de l’arbre

A: l’arbre avant insertion A’: l’arbre après insertion

δ: l'équilibre avant insertion δ’: l'équilibre après insertion
 Insertion dans un arbre AVL
Rééquilibrage de A’

x
u

Remonter le chemin γ entre la nouvelle feuille s et la racine. Pour chaque sommet v de γ:

• calculer (et stocker) la nouvelle profondeur du sous-arbre A(v) (au plus +1)
• vérifier les conditions AVL pour A(v)

x: le premier sommet de γ (de s vers la racine) tel que A(x) n’est pas AVL ( |δ’(x)| =2 )
u: le fils de x dans γ (supposer u fils gauche, le cas u fils droit est symétrique)
(u est dans A)
 Insertion dans un arbre AVL
Propriétés de A (arbre avant l’insertion) et γ
Lemme A γ
1) Pour tous descendant v de x sur le chemin γ (x exclus): x
δ(v)=0
v
2) Pour x: δ(x) =1

Preuve:

• Soit P le sous arbre plus profond de v dans A et S l’autre sous-arbre

• l’insertion de la nouvelle feuille s (au bout de γ) se fait dans P

(sinon h(A’(v)) =h(A(v)) et donc δ(x) = δ’(x) )

• Donc |δ’(v)| = |δ(v)| +1

• Si |δ(v)| ≠ 0 alors |δ’(v)| >1 contradiction (parce que A’(v) est AVL )

• Pour x: |δ(x)| =1 et s est inséré dans le sous-arbre les plus profond de x

(sinon A’(x) serait AVL )
• L’insertion se fait dans Ag(x) par hypothèse δ(x) =1
 Insertion dans un arbre AVL
Rééquilibrage de A’, deux cas
1) s inséré dans le sous-arbre gauche de u

x A’
A:
x
u u
h

h h
s
⇓

A’: x rééquilibrage : u
rotation droite
x équilibre rétabli
u h(A’(u)) =h(A(x))
h

h h+1 h h

h+1
 Insertion dans un arbre AVL
Rééquilibrage de A’, deux cas
2) s inséré dans le sous-arbre droit de u
x A’
A:
x
u
u
y
h

h h-1 h-1
s
⇓
rééquilibrage :
x y y peut être éventuellement le
A’: rotation gauche-droite
nouveau noeud inséré
u u x équilibre rétabli
y h(A’(y)) =h(A(x))
h
h-1
h h-1 h h h
h
 Insertion dans un arbre AVL
Complexité de l’insertion : O(log n)

Phase de descente: O(log n)

Phase de rééquilibrage O(log n):
on remonte au pire jusqu'à la racine
ensuite une opération de rééquilibrage (O(1))
 Suppression dans un arbre AVL
Deux phases:
1) suppression d’une feuille s (algorithme de suppression ABR modifié):
descente de l’arbre pour trouver le sommet x contenant la clef à supprimer
‣ si x est une feuille il est supprimé
‣ sinon remplacer le contenu de x avec le noeud y contenant le maximum
de Ag(x) ou le minimum de Ad(x)
‣ supprimer y récursivement

Xs

2) rééquilibrage de l’arbre

A: l’arbre avant suppression A’: l’arbre après suppression

δ: l'équilibre avant suppression δ’: l'équilibre après suppression
 Suppression dans un arbre AVL
Rééquilibrage de A’

A’

Xs

Remonter le chemin γ entre le père de s et la racine. Pour chaque sommet v de γ:

• calculer (et stocker) la nouvelle profondeur du sous-arbre A(v)

• vérifier les conditions AVL pour A(v)

x: le premier sommet de γ (de s vers la racine) tel que A(x) n’est pas AVL ( |δ’(x)| =2 )
supposons s dans le sous-arbre droit de x (l'autre cas est symétrique)
 Suppression dans un arbre AVL
Dans A’: x plus précisément: x

u
h h
h+2
AVL
h+2
AVL

Deux cas:
1) Le sous-arbre gauche de u à hauteur h+1

x rééquilibrage : u
rotation droite
x
u
h

h h+1 h h Si h+1: équilibre rétabli

ou ou ( h(A’(u)) = h(A(x)) )
h+1 h+1 h+1
Sinon h(A’(u)) = h(A(x))-1
 Suppression dans un arbre AVL
2) Le sous-arbre gauche de u à hauteur h

rééquilibrage :
x y
rotation gauche-droite

u u x
y h(A’(y)) = h(A(x))-1
h
h-1
h h-1 h ou h h h
ou h h

Si après une étape de rééquilibrage l'équilibre n’est pas rétabli, répéter le rééquilibrage sur le
noeud père, et ainsi de suite, au pire jusqu’à la racine
 Suppression dans un arbre AVL
Complexité de la suppression : O(log n)

Phase de descente: O(log n)

Phase de rééquilibrage: O(log n)
on remonte jusqu'à un noeud de hauteur h’
en suite O(h-h’) rééquilibrages au pire
 Arbres a-b
Pour a ≥ 2, b≥ 2a -1
Un arbre a-b sur (Tclef , Tval) est un arbre A tel que:
1) les feuilles de A ont toutes la même profondeur et contiennent des couples (clef, val)
2) chaque noeud interne x de A a:
- un nombre d(x) de sous-arbres a ≤ d(x) ≤ b, dénotés Ai(x) ( i=1..d(x) )
- une suite de d(x)-1 clefs (dites balises) K1,..., Kd(x)-1 telles que pour tout i
clefs dans Ai(x) ≤ Ki < clefs dans Ai+1(x)
3) à la racine la contrainte sur d(x) est moins forte: 2 ≤ d(x) ≤ b

1 3 6 9 10 Un arbre 3-5

1, v1 2, v2 5, v3 7, v4 9, v5 10, v6 11, v7
 Relation entre la hauteur et la taille
Proposition
Soit A un arbre a-b avec n feuilles et de hauteur h, alors
log n / log b ≤ h ≤ 1 + log (n/2) / log a

Preuve:
n ≤ bh
parce que chaque noeud interne a au plus b fils
n ≥ 2·ah-1
parce que la racine a au moins 2 fils et les autres noeuds internes ont au moins a fils
 Recherche dans les arbres a-b
Recherche d’une clef c dans A: descente dans la profondeur de l’arbre

x ← racine de A
Tant que le sommet courant x n’est pas une feuille
trouver i tel que Ki-1 ≤ c ≤ Ki Ki-1 Ki x
(parcours linéaire des balises de x)
( i=1 si c ≤ K1 Ai(x)

i=d(x) si c > Kd(x)-1)

x ← racine de Ai(x)
c, v

Complexité: O(hauteur) O(log n) dans le cas pire

( Le parcours linéaire d’un noeud interne se fait en temps O(1) )

 Insertion dans les arbres a-b
Insertion de (c,v) (c n’apparaît pas dans l’arbre)
Première phase:

• descente dans la profondeur de l’arbre guidée par les balises (recherche de c)

• soit ci la clef trouvé à la place de c
• Insertion de (c, v) comme nouvelle feuille: Deux cas

c < ci Ki-1 Ki Ki-1 c Ki

ci, vi c, v ci, vi

c > ci Ki-1 Ki Ki-1 ci Ki

ci, vi ci, vi c, v
 Insertion dans les arbres a-b
Deuxième phase (rééquilibrage)

• Si la contrainte d(x) ≤ b est violée sur un noeud x après la première phase:

• éclater x
Règle d'éclatement (équilibré) d’un noeud interne x avec d(x) fils b+1≤d(x)≤2b

y K

x K

d(x) / 2 d(x) / 2 a ≤ d(x) / 2 d(x) / 2 ≤ b

(si x est la racine une nouvelle racine contenant uniquement la clef K est créée)

Observation: d(x) ≥ b+1 ≥ 2 a les deux nouveaux noeuds sont a-b

• Apres l’éclatement de x: le père y de x peut avoir b+1 fils:

répéter l'éclatement sur y et ainsi de suite (au pire) jusqu’à la racine
 Insertion dans les arbres a-b

Complexité:
Première phase: O(log n)
Deuxième phase : O(log n) - chaque opération d'éclatement se fait en temps O(1)

L’insertion dans un arbre a-b à n éléments (feuilles) se fait en temps O(log n) dans le cas pire
 Suppression dans les arbres a-b
Première phase:

• Recherche de la feuille y qui contient la clef c (descente dans la profondeur de l’arbre)

• Suppression de y et de la balise correspondante

c, v

c, v

Apres la suppression de la feuille, le père x peut avoir un nombre insuffisant de fils

 Suppression dans les arbres a-b
Deuxième phase (rééquilibrage): Si le noeud interne x a un nombre insuffisant de fils,
Trois cas:
1) x est la racine (et x a un seul fils)
supprimer x et le remplacer par son fils

Sinon x a un père, a-1 fils et au moins un frère

 Suppression dans les arbres a-b
Deuxième phase (rééquilibrage): Si le noeud interne x a un nombre insuffisant de fils,
Trois cas:
2) x a un frère (gauche ou droit) z qui a plus que a fils: partage entre x et son frère
Règle de partage entre deux noeuds frères: a-1 ≤ d(x) < b a < d(z) ≤ b

x z K

<b >a ≤b ≥a
≥ a-1 ≤b ≥a ≤b

L’arbre est a-b après le partage

 Suppression dans les arbres a-b
Deuxième phase (rééquilibrage): Si le noeud interne x a un nombre insuffisant de fils,
Trois cas:
3) tous les frères de x ont a fils: fusion entre x et son frère gauche ou droit
Règle de fusion entre deux noeuds frères: a ≤ d(x)+d(z) ≤ b

K y

x z K

a≤ + ≤b a≤ ≤b

En particulier a-1 + a ≤b

Le noeud y peut ne pas être a-b, après la fusion

Répéter le rééquilibrage sur le noeud y et ainsi de suite (au pire) jusqu’à la racine
 Suppression dans les arbres a-b

Complexité:
Première phase: O(log n)
Deuxième phase : O(log n) - chaque opération de partage ou fusion se fait en temps O(1)

La suppression dans un arbre a-b à n éléments (feuilles) se fait en temps O(log n) dans le cas pire
 Concaténation et scission dans les arbres a-b
Rappel:
Type abstrait dictionnaire: un dictionnaire est un ensemble de couples (clef, valeur)
Opérations typiques dans un dictionnaire:

FUSIONNER ( Dictionnaire D1, Dictionnaire D2 ): Dictionnaire; Retourne D1 ∪ D2

SCINDER ( Dictionnaire D, Tclef c ): ( Dictionnaire, Dictionnaire) ;

Retourne (D1, D2) où D1 = { (c’,v) ∈ D | c’ ≤ c } et D2=D \ D1

CONCATENER: Cas particulier de fusion, pre-condition: max(D1) < min(D2)

Concaténation et scission peuvent être implémentés efficacement (O(log n)) dans les arbres a-b
 Concaténation de deux arbres a-b
On suppose d’abord avoir une clef max(D1) ≤ c < min(D2) et on implémente la fonction
suivante:

pre-conditions:

• A1, A2 sont deux arbres a-b qui représentent les dictionnaires D1 et D2 , respectivement
• max(D1) ≤ c < min(D2)

CONCATENER ( Arbre A1, Tclef c, Arbre A2 ): Arbre;

Retourne un arbre a-b qui représente D1 ∪ D2

Complexité de l'implémentation: O( 1+ |h1 -h2| ) où hi est la hauteur de Ai, i=1,2

 Concaténation de deux arbres a-b
CONCATENER ( Arbre A1, Tclef c, Arbre A2 ): Arbre; Supposer h1 ≥ h2
Première phase: O(1+|h1-h2|)

• Descendre la branche la plus à droite de A1, jusqu'au noeud x dont le sous arbre a hauteur h2

(si h2 est 0 : cas particulier)

A1
h1 x
A2
h2 h2

• Fusionner x avec la racine de A2, en utilisant la clef c (Remarquer que clefs de A(x) ≤ c <
clefs de A2)

c x’
h1
h2

d(x’) ≤ 2b
 Concaténation de deux arbres a-b
CONCATENER ( Arbre A1, Tclef c, Arbre A2 ): Arbre; Supposer h1 ≥ h2
Deuxième phase: O(1+|h1-h2|)

c x’
h1
h2

Si d(x’) > b

• éclatement équilibré de x’ ( possible parce que b+1 ≤ d(x’) ≤ 2b ) ;

en suite, si nécessaire,
• éclatement des ancêtres de x’ (au pire) jusqu’à la racine
 Concaténation de deux arbres a-b
pre-conditions:

• A1, A2 sont deux arbres a-b qui représentent les dictionnaires D1 et D2 , respectivement
• max(D1) < min(D2)
CONCATENER ( Arbre A1, Arbre A2 ): Arbre;
Retourne un arbre a-b qui représente D1 ∪ D2

Implementation:
trouver c = clef maximale dans A1 → O(1+h1)
retourner CONCATENER ( A1, c, A2 ); → O( 1 + |h1-h2| )

Complexité de la concaténation : O( max (h1, h2) ) → O( log(max(|D1|, |D2|)) )

 Scission d’un arbre a-b

Pre-conditions:

• A est un arbre a-b qui représente le dictionnaire D

• La clef c apparaît dans D
SCINDER ( Arbre A, Tclef c ): ( Arbre, Arbre) ;

Retourne un couple d’arbres a-b qui représentent les dictionnaires D1 = { (c’,v) ∈ D | c’ ≤ c }

et D2=D \ D1
 Scission d’un arbre a-b
Soit π le chemin de la racine de A à la feuille contenant la clef de scission c

A g1 d1

g2 d2

d3

g3

c, v
 Scission d’un arbre a-b
Soit π le chemin de la racine de A à la feuille contenant la clef de scission c

A g1 d1

g2 d2

d3

g3

c, v

Les arbres à gauche de π contiennent les clefs ≤ c

Les arbres à droite de π contiennent les clefs > c
 Scission d’un arbre a-b
Soit π le chemin de la racine de A à la feuille contenant la clef de scission c

G1 g1 d1 D1

G2 g2 d2 D2

d3 D3

G3 g3

G4 c, v

Gi, i ≤ h(A)+1 Di, i ≤ h(A)

Chaque Gi, Di est un arbre a-b (sauf peut-être à la racine)

• clefs de Di+1 ≤ di ≤ clefs Di (parce que Di+1 est dans le sous-arbre gauche de di )
• clefs de Gi ≤ gi ≤ clefs Gi+1 (parce que Gi+1 est dans le sous-arbre droit de gi )
 Scission d’un arbre a-b
clefs de Gi ≤ gi ≤ clefs Gi+1 clefs de Di+1 ≤ di ≤ clefs Di

G1 g1 d1 D1

G2 g2 d2 D2

d3 D3

G3 g3

G4 c, v

CONCATENER (G3, g3, G4) → G3’ CONCATENER (D3, d2, D2) → D2’
CONCATENER (G2, g2, G3’) → G2’ CONCATENER (D2’, d1, D1) → D1’
CONCATENER (G1, g1, G2’) → G1’
si la racine de G1’ (ou D1’) a un seul fils, la supprimer
retourner (G1’, D1’)
 Scission d’un arbre a-b

G1 D1

G2 D2

D3

G3

G4 c, v

CONCATENER (G3, g3, G4) → G3’ O(1+ h(G3) -h(G4) )

CONCATENER (G2, g2, G3’) → G2’ O(1+ h(G2) -h(G3’) ) O(h(A))
CONCATENER (G1, g1, G2’) → G1’ O(1+ h(G1) -h(G2’) )

( h(Gi’) = h(Gi) ou h(Gi’) = h(Gi)+1, par récurrence )

 Scission d’un arbre a-b
Pre-conditions:

• A est un arbre a-b qui représente le dictionnaire D

• La clef c apparait dans D
SCINDER ( Arbre A, Tclef c ): ( Arbre, Arbre) ;

Retourne un couple d’arbres a-b qui représentent les dictionnaires D1 = { (c’,v) ∈ D | c’ ≤ c }

et D2=D \ D1

Complexité de la scission : O( h(A) ) → O( log |D| )

 Coût amorti des arbres a-b
Coût d’une insertion/suppression:
O(h + r)
Où h = hauteur de l’arbre a-b (phase de descente)
r ≤ h : nombre d'étapes de rééquilibrage (éclatement/partage/fusion)

Soit s une suite de n opérations d’insertion et suppression dans un arbre a-b

P(s): nombre totale de partages effectués dans la suite s d’opérations
E(s): nombre totale de éclatements effectués dans la suite s d’opérations
F(s): nombre totale de fusions effectués dans la suite s d’opérations

P(s)+E(s)+F(s)
Coût amorti de rééquilibrage pour s :
n
 Coût amorti des arbres 2-4
Proposition
Sur un suite s quelconque de n opérations d’insertion et suppression dans un arbre 2-4
initialement vide, le coût amorti de rééquilibrage est constant.
Plus précisément, soit i le nombre d’insertions et d le nombre de suppressions dans s, alors

P(s) ≤ d
E(s)+F(s) ≤ n + (i-d-1) / 2

P(s)+E(s)+F(s)
Par conséquent ≤ 3
n 2

Preuve: Exercice
 B-arbres
Quand b=2a -1, un arbre a-b est appelé B-arbre d’ordre a-1 (ordre = nombre de clefs dans un
noeud)

B-arbres:

• Utilisées pour la recherche de clefs en mémoire secondaire (indexes sur les bases de données)

• Un noeud interne = une bloc du disque

• Mesure de complexité: nombre d’ accès au disque

• Informations associées a chaque clef (le champ val) : pointeur au données sur disque

• Complexité de la recherche/modification: O(log n) où n est le nombre de blocs

 Arbres rouge-noir [Guibas-Sedgewick]
Un arbre rouge-noir est

• un arbre binaire de recherche complet A sur un domaine (Tclef, Tval) avec

• une fonction c qui associe à chaque sommet de A une couleur ∈ {rouge, noir}

tels que:
1) seules les noeuds internes (i.e. non-feuille) de A contiennent des couples (clef, valeur)
2) la fonction c satisfait les propriétés suivantes:
a) le feuilles sont noires
b) la racine est noire
c) le père d’un sommet rouge est noir
d) tous les chemins d’un même sommet x vers les feuilles ont le même nombre de sommets
noirs - ce nombre (x exclu) est appelé rang de x
 Arbres rouge-noir - Exemple
Un arbre rouge-noir et sa fonction de rang:

2
6

2 4 8 1

1 3 5 1 1 7
0
1 2
0 0 0 0 0

0 0

(par clarté seulement les clefs, et pas le valeurs, sont représentés)

 Relation entre la hauteur et la taille
Proposition
Si A est un arbre-rouge noir ayant n (n>0) sommets et hauteur h, alors

log n ≤ h ≤ 2 log n

Preuve 1) Borne inférieure: clairement n ≤ 1+2+..+2h |bin(n)| = log n +1 ≤ h+1

2) Borne supérieure:
On montre que pour chaque sommet x de A de hauteur h(x), de rang k et dont le sous-arbre
a n(x) sommets:
h(x) ≤ 2k et 2k ≤ n(x)
De plus, si x est rouge, les inégalités sont strictes.

Preuve par récurrence sur h(x).

• Vrai si x est une feuille ( x est noir; h(x)=0; k=0; n(x)=1 ).

 Relation entre la hauteur et la taille
Preuve (suite). On montre que pour chaque sommet x de A de hauteur h(x), de rang k et dont le
sous-arbre a n(x) sommets: h(x) ≤ 2k et 2k ≤ n(x)
De plus, si x est rouge, les inégalités sont strictes.

• Si x n’est pas une feuille, 3 cas:

x a deux fils rouges x a deux fils noirs x a un fils rouge et un fils noir

k k k
x x x

k y z k k-1 y z k-1 k y z k-1

L'énoncé pour x suit facilement en utilisant l'hypothèse de récurrence sur y et z

 Insertion dans les arbres rouge-noir
Insertion d’un couple (c, v)
Première phase: descente dans la profondeur de l’arbre, guidée par les clefs dans les noeuds
internes. Arrivé sur une feuille, la remplacer par un noeud rouge x ayant deux feuilles noires:

8 8

4 4

5 5

c x

Après insertion, tous les noeuds satisfont les propriétés rouge-noir

sauf peut-être x où les règles b) et c) peuvent être violés:
- si x est la racine, la racine n’est pas noire
- si le père de x est rouge, le père d’un noeud rouge n’est pas noir
 Insertion dans les arbres rouge-noir
Deuxième phase (rééquilibrage)
Soit x le noeud courant
- x est rouge et x viole au plus b) et c) ;
- x est le seul noeud de l’arbre qui ne satisfait pas les conditions rouge-noir,

• x est la racine colorer x noir l’arbre devient rouge-noir

• x n’est pas la racine et x a un père y rouge y a un père z et z est noir. Deux cas:

1) L’autre fils de z est rouge

z z

y y

x x

Dans le cas 1) z devient le nouveau noeud courant

 Insertion dans les arbres rouge-noir
2) L’autre fils de z est noir

k+1 z k+1 y
rotation simple
x et t “éloignés”
k+1 y k t x k+1 z k+1
+ recoloriage

k+1 x w w t k
k+1 noeuds noirs, y compris w

k+1 z k+1 x
rotation double
x et t “proches”
k+1 y k t y k+1 z k+1
+ recoloriage

x k+1 t k

Dans les cas 2) après les rotations l’arbre est rouge-noir

 Insertion dans les arbres rouge-noir
Phase de rééquilibrage:

• Réitérer le rééquilibrage du noeud courant au pire jusqu’à la racine

(jusqu’à l’application d’une règle d'arrêt)

• Complexité O(log n) (chaque étape de rééquilibrage se fait en O(1) )

Complexité de l’insertion: O(log n)

 Suppression dans les arbres rouge-noir
Première phase: descente dans la profondeur de l’arbre (recherche du noeud x de clef c)
et suppression de x:
1) un fils de x est une feuille, soit y l’autre fils
- x rouge : 1
x équilibre rétabli
( y noir)
y

- x noir et y rouge:
x 1 y équilibre rétabli

- x noir et y noir: +
x 1 feuille dégradée

y
 Suppression dans les arbres rouge-noir
2) x a deux fils non-feuille

x c x m

y y
m m

• Remplacer le contenu de x avec le contenu de y (le maximum du sous-arbre gauche)

• Supprimer y avec l’algorithme du cas 1)

Complexité de la première phase O(log n)

 Suppression dans les arbres rouge-noir
Deuxième phase: élimination du sommet dégradé

Propriétés d’un sommet dégradé:

• Le sous-arbre enraciné dans un sommet dégradé est rouge-noir (quand le sommet dégradé est
vu comme un noeud noir habituel)

• Un arbre rouge-noir avec un sommet noir dégradé satisfait toutes les conditions d’un arbre
rouge-noir si le sommet dégradé est vu comme un noeud noir, mais compte comme 2 dans le
calcul du nombre de noeuds noirs sur les chemins

⇓
rang dans un arbre avec un sommet dégradé: le sommet dégradé compte comme 2
 Suppression dans les arbres rouge-noir
Deuxième phase: élimination du sommet dégradé

Soit x le sommet dégradé courant. Cas possibles:

- x a un frère noir z z a deux fils

(sinon la règle sur les rangs n’est pas satisfaite dans le père de x: )
+
- z a deux fils noirs x z
- z a un fils rouge

- x a un frère rouge

- x est la racine
 Suppression dans les arbres rouge-noir
Soit x le sommet dégradé courant.
- x a un frère noir z et z a deux fils noirs

+
père noir y k+2 y k+1 y degradé

+
x k z k+1 x k z k+1

père rouge

y k+2 y k+1 équilibre rétabli

+
x k z k+1 x k z k+1
 Suppression dans les arbres rouge-noir
Soit x le sommet dégradé courant.
- x a un frère noir z et z a un fils rouge
rotation simple
y k+2 z k+2
x et t éloignés
+
x k z k+1 y k+1 t k+1

t k+1 k x équilibre rétabli

rotation double
y k+2 t k+2
x et t proches
+
x k z k+1 y k+1 z k+1

k+1 t u k x u k

équilibre rétabli
 Suppression dans les arbres rouge-noir
Soit x le sommet dégradé courant.
- x a un frère rouge
rotation simple
y k+2 z k+2

+
x k z k+2 y k+2

+
x k

x est dégradé, mais une seule autre étape de rééquilibrage suffit pour rétablir l'équilibre
(toutes les règles telles que le père de x est rouge rentabilisent l'équilibre)
- x est la racine
+
x x équilibre rétabli
 Suppression dans les arbres rouge-noir
• La suppression peut introduire une feuille dégradée

• chaque étape de rééquilibrage:

- augmente de 1 la hauteur du noeud dégradé ou
- rétabli l'équilibre au pire à l'étape suivante;
- quand le noeud dégradé est la racine, l'équilibre est rétabli

⇓
Au plus h+1 étapes de rééquilibrage

Complexité du rééquilibrage: O(log n)

Complexité de la suppression: O(log n)

 Bibliographie
1) A.V. Aho, J.E. Hopcroft, J.D. Ullmann.
Data Structures and Algorithms. Addison-Wesley.

2) Danièle Beauquier, Jean Berstel, Philippe Chrétienne.

Éléments d’Algorithmique.
Masson, 1992. http://www-igm.univ-mlv.fr/~berstel/Elements/Elements.html

3) Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest.

Introduction à l'algorithmique. 2e édition, Dunod, 2002.