Arbres de recherche équilibrés

AlgorithmiqueCristina 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 manipulentStructure 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

A

B C

y

x

A B

C

rotation gauche

rotation droite

Rotations

x

z

D

z

x

A B

rotation droite-gauchey

A

B C

y

C D

Toutes les opérations de rotation sur les arbre binaires peuvent être réalisées en temps O(1)

x

z

A

z

y

A B

rotation gauche-droite

y

D

B C

x

C D

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

n ≥ N(h) = F(h) -1 ⇒

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)

1√5

F(h)= ( ph+3 - qh+3 ) q = 2

1- √5p =

21+ √5

qh+3 < 1>1√5

ph+3 -1

>1√5

ph+3 -1n+1

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

s


Rééquilibrage de A’

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)

s

xu

γ


Propriétés de A (arbre avant l’insertion) et γ

Lemme

1) Pour tous descendant v de x sur le chemin γ (x exclus): δ(v)=0

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

A

x

v

γ


Rééquilibrage de A’, deux cas

1) s inséré dans le sous-arbre gauche de u

A’A:

⇓

A’:

s

xu

h h

h

x

u

h h

rééquilibrage :rotation droite

h

h

x

u

h+1

u

x

h+1

équilibre rétabli h(A’(u)) =h(A(x))


Rééquilibrage de A’, deux cas

2) s inséré dans le sous-arbre droit de u

A:

⇓

A’: rééquilibrage :

rotation gauche-droite

h h-1

h

x

uy

hh h h

u

y

x

h-1

h h-1

h

x

u

h-1

y

A’

s

xu

y peut être éventuellement le nouveau noeud inséré

équilibre rétabli h(A’(y)) =h(A(x))


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

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

sX


Rééquilibrage de A’

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)

A’

s

x

X

γ


Dans A’: plus précisément:

Deux cas:

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

AVL

AVL

h

x

h+2

h

x

u

h+2

h

rééquilibrage :rotation droite

h ou

h+1

h

x

u

h+1

u

x

h+1 h ou

h+1

Si h+1: équilibre rétabli ( h(A’(u)) = h(A(x)) )

Sinon h(A’(u)) = h(A(x))-1


2) Le sous-arbre gauche de u à hauteur 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

rééquilibrage :rotation gauche-droite

h h-1 ou h

h

x

uy

hh h h

u

y

x

h-1 ou h

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


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

8

1 3 6 9

1, v1 2, v2 5, v3 7, v4 9, v5 10, v6 11, v7

10 Un arbre 3-5

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 (parcours linéaire des balises de x)

( i=1 si c ≤ K1

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

x ← racine de Ai(x)

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

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

c, v

Ki-1 Ki

Ai(x)

x

A

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

Ki-1 Ki

ci, vi

Ki-1 Ki

ci, vi

c

c, v

c < ci

Ki-1 Ki

ci, vi

Ki-1 Ki

ci, vi

ci

c, v

c > ci


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

(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

K

d(x) / 2

K

d(x) / 2 d(x) / 2d(x) / 2

x

y

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

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

c, v

y

c, v

y

x

x


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



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

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

K

< b > a

x z

≤ b ≥ a

K

≥ a-1 ≤ b ≥ a ≤ b



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

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

Kx

K

z

+ ≤ b ≤ b

y

a ≤ a ≤


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


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

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

d(x’) ≤ 2b

h1

h2 h2

xA1

A2

ch1

h2

x’

(si h2 est 0 : cas particulier)


CONCATENER ( Arbre A1, Tclef c, Arbre A2 ): Arbre; Supposer h1 ≥ h2

Deuxième phase: O(1+|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

ch1

h2

x’


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

c, v

d2g2

d3

g1 d1

g3


Soit π le chemin de la racine de A à la feuille contenant la clef de scission c

A


Les arbres à gauche de π contiennent les clefs ≤ c

Les arbres à droite de π contiennent les clefs > c

c, v

d2g2

d3

g1 d1

g3


A


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 )


G1

G2

G3

D1

D2

D3

G4 c, v

d2g2

d3

g1 d1

g3

clefs de Gi ≤ gi ≤ clefs Gi+1 clefs de Di+1 ≤ di ≤ clefs Di

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’)


G1

G2

G3

D1

D2

D3

G4 c, v

d2g2

d3

g1 d1

g3

c, v

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

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

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

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


G1

G2

G3

D1

D2

D3

G4

O(h(A))


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

Coût amorti de rééquilibrage pour s : P(s)+E(s)+F(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

Par conséquent

Preuve: Exercice

P(s)+E(s)+F(s)n

≤ 32

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:

6

4 8

3 5 7

2

0 0

0 0 0 0 0

0

1

1

2

1

2

1

1

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


Proposition

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

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 ).

log n ≤ h ≤ 2 log n


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:

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

x

y z

k

k k

x a deux fils rouges

x

y z

k

k k-1

x

y z

k

k-1 k-1

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

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:

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

8

4

5

8

4

5

c x


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

Dans le cas 1) z devient le nouveau noeud courant

z

y

x

z

y

x


2) L’autre fils de z est noir

x et t “éloignés”

x et t “proches”

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

z

y t

x

rotation simple

y

x z

t

kk+1

k+1

k+1

k

k+1

k+1 k+1

+ recoloriage

k+1 noeuds noirs, y compris ww w

z

y t

x

rotation double

x

y z

t

kk+1

k+1

k+1

k

k+1+ recoloriage

k+1 k+1


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 :

(⇒ y noir)

- x noir et y rouge:

- x noir et y noir:

x

y

x

y

y

x

y

+

équilibre rétabli

équilibre rétabli

feuille dégradée

1

1

1


2) x a deux fils non-feuille

• 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)

c

m

x m

m

x

y y


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


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

- z a un fils rouge

- x a un frère rouge

- x est la racine

x z+


Soit x le sommet dégradé courant.

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

père noir

père rouge

y

x zk k+1+

k+2 y

x zk k+1

k+1+

équilibre rétabliy

x zk k+1+

k+2 y

x zk k+1

k+1

y degradé



- x a un frère noir z et z a un fils rouge

x et t éloignés

x et t proches

y

x z

t

k k+1+

k+2 z

y t

x

k+1 k+1

k+2rotation simple

k+1 k équilibre rétabli

équilibre rétabli

y

x z

ut

rotation doublet

y z

u

k+1k

k+1

k+1

k

k+1

x

+

k+2

k

k+2



- x a un frère rouge

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

y

x

k

k+2

k+2

+z

z

y k+2

k+2

+

rotation simple

x

k

équilibre rétablix+

x


• 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.

http://www-igm.univ-mlv.fr/~berstel/Elements/Elements.html

http://www-igm.univ-mlv.fr/~berstel/Elements/Elements.html

Documents

Arbres de recherche équilibrés