RÉPUBLIQUE DU CAMEROUN FACULTÉ DES SCIENCES

REPUBLIC OF CAMEROON FACULTY OF SCIENCES

----------- -----------
Peace-Work-Fatherland Paix-Travail-Fratrie
----------- -----------

UNIVERSITÉ DE DSCHANG DÉPARTEMENT DE MATHS-INFO

UNIVERSITY OF DSCHANG DEPARTMENT OF MATHS-INFO

theme
Sous supervision de : MR LEONEL

CHAPITRE 2 : Arbres binaires de recherche et Arbre Rouge-Noir

NOMS ET PRENOMS MATRICULES

DJIMRA TELRO CM-UDS-19SCI0303
AVOMO TESSA ROMAEL WILSON CM-UDS-21SCI1450
TCHATCHOUANG FEZZE STEVE CM-UDS-24SCI
ANICET

Option: RSD

SOUS LA SUPERVISION DE : Pr KENGNE VIANNEY T.

ANNEE ACADEMIQUE 2024-

2025
Page 1
 Plan de l’exposé

Introduction

I. Généralités sur les arbres binaires

1. Définition
2. Parcours
a. Parcours infixe
b. Parcours préfixe
c. Parcours suffixe

II. Arbre binaire de recherche

1. Définitions et représentations
2. Opérations sur les arbres binaires de recherche

Maximum et minimum
a. Recherche
b. Insertion
c. Suppression

III. Arbres Rouges et Noires

1. Définitions et représentations
2. Operations sur les arbres rouges et noires

a. Insertion
b. Suppression
c. Rotation

Page 2
 3. Complexité

IV. Arbre binaires de recherche et arbre rouge noire

1. Comparaison
2. Domaine d’application

Introduction

Un arbre binaire de recherche est une structure de données qui permet de

manipuler les données classées au maximum en deux sous arbre (d’où le binaire). En
fonction de la configuration et les méthodes de manipulation de ces données, on
distingue les arbres binaires des recherches, les arbres binaires équilibrés, les arbres
binaires dites rouges et noires, ... Notre travail consiste à parler dans un premier
temps des arbres binaires de recherche d’une manière générale, en suite une
approfondie sur les arbres rouges noires.

I. Généralités sur les arbres

1. Définitions
D’une manière générale, un arbre binaire est une structure de donnes hiérarchique
constituées de deux nœuds. Le nœud initial est appelé racine, chaque nœud peut
posséder jusqu’à deux fils (fils gauche et fils droit) dont il est le père. La racine est le
Seul nœud de niveau 0, le fils d’un nœud de niveau i sont des nœuds de niveau i+1.
le niveau maximal d’un nœud est appelé la hauteur de l’arbre. Un nœud sans fils
est appelé feuille, seule la racine n’a pas de père. Chaque nœud possède une valeur
qui peut être n’importe quel objet (les entiers, les booléens, les chaines de
caractère...).
2. parcours
Le parcours d’un arbre fait aussi parti de l’un des traitements qu’on peut effectuer sur
un arbre. Nous distinguons trois parcours à savoir: Infixe, Préfixe et post fixe.

a. parcours en Infixe
Le parcours en infixe nous permet de parcourir un arbre comme suit.
On affiche le sous arbres gauche, puis la racine puis le sous arbres droit.
b. parcours en préfixe
Dans le parcours en préfixe, on affiche dans un premier temps la racine de l’arbre en
suite son sous fils gauche suivi de son sous fils droit.
c. parcours en Post fixe
Le parcours Post fixe d’un se déroule comme suit: on affiche le sous arbre gauche puis
le sous arbre droit suivi de la racine qui vient en dernier position.

Page 3
II. Arbre binaire de recherche

1. Définitions et représentations
Un arbre binaire de recherche est un arbre binaire dans lequel chaque nœud
possède une clé, telle que chaque nœud du sous arbre gauche ait une clé inférieure
ou égale à celle du nœud considéré, et que chaque nœud du sous arbre droit
possède une clé supérieure ou égale à celle-ci ; Selon la mise en œuvre de l'ABR,
on pourra interdire ou non des clés de valeur égale. Les nœuds que l'on ajoute
deviennent des feuilles de l'arbre.
Un arbre binaire de recherche est dit équilibré si la différence de profondeur de
deux feuilles quelconques est d’au plus 1.
Il existe de nombreux types d'arbres binaires de recherche, parmi lesquels les
arbres rouge-noir et les arbres binaires de recherche optimaux (dont nous
prendrons le soin de bien étudier).
Ci-dessous est un exemple d’arbre binaire de recherche équilibré.

Figure : Exemple d’arbre binaire équilibré

Un arbre binaire de recherche de hauteur h permet de mettre en œuvre les

opérations fondamentales d’ensemble dynamique, telles RECHERCHER,
PRÉDÉCESSEUR, SUCCESSEUR, MINIMUM, MAXIMUM,
INSÉRER et SUPPRIMER, avec un temps O(h).

Page 4
 a. Maximum et minimum

On peut toujours trouver un élément d’un arbre binaire de recherche dont la clé est un minimum
en suivant les pointeurs gauches à partir de la racine jusqu’à ce qu’on rencontre NIL. La
procédure suivante retourne un pointeur sur l’élément minimal du sous arbre enracine au nœud 𝑥

Le pseudo code pour recherche le maximum dans un arbre binaire de recherche est symétrique.

b. Recherche
La recherche dans un arbre binaire d'un nœud ayant une clé particulière peut être considéré un
procédé récursif ou itératif. On commence par examiner la racine. Si sa clé est la clé recherchée,
l'algorithme se termine et renvoie la racine. Si elle est strictement inférieure, alors elle est dans
le sous arbre gauche, sur lequel on effectue alors récursivement la recherche. De même si la clé
recherchée est strictement supérieure à la clé de la racine, la recherche continue dans le sous arbre
droit. Si on atteint une feuille dont la clé n'est pas celle recherchée, on sait alors que la clé
recherchée n'appartient à aucun nœud, elle ne figure donc pas dans l'arbre de recherche.
L’algorithme itératif de l’opération rechercher dans l’arbre binaire de recherche peut se donner
comme suit

c. Insertion
L'insertion d'un nœud commence par une recherche : on cherche la clé du nœud à
insérer ; lorsqu'on arrive à une feuille, on ajoute le nœud comme fils de la feuille en
comparant sa clé à celle de la feuille : si elle est inférieure, le nouveau nœud sera à
gauche ; sinon il sera à droite. La procédure suivante montre comment insérer un
élément dans un arbre binaire de recherche.

Page 5
 d. Suppression

Plusieurs cas sont à considérer, une fois que le nœud à supprimer a été trouvé à partir de sa clé :

• Suppression d'une feuille : Il suffit de l'enlever de l'arbre vu qu'elle n'a pas de fils.
• Suppression d'un nœud avec un enfant : Il faut l'enlever de l'arbre en le remplaçant par
son fils.
• Suppression d'un nœud avec deux enfants : Supposons que le nœud à supprimer soit
appelé N (le nœud de valeur 7 dans le graphique ci-dessous). On échange le nœud N
avec son successeur le plus proche (le nœud le plus à gauche du sous arbre droit - ci-
dessous, le nœud de valeur 9) ou son plus proche prédécesseur (le nœud le plus à droite
du sous arbre gauche - ci-dessous, le nœud de valeur 6). Cela permet de garder une
structure d'arbre binaire de recherche. Puis on applique à nouveau la procédure de
suppression à N, qui est maintenant une feuille ou un nœud avec un seul fils. Mais en
général, il est conseillé de faire l’échange avec le successeur, et non avec le
prédécesseur

Page 6
 Figure 3 : Exemple de schéma de suppression

Le pseudo code suivant montre les différents cas de suppression dans un arbre binaire de
recherche

Page 7
III. Arbre Rouges et Noires

1. Définitions et représentations
Un arbre rouge-noir est un arbre binaire de recherche satisfaisant les cinq propriétés suivantes :
1. Chaque nœud est soit rouge, soit noir. *
2. La racine est noire.
3. Chaque feuille (NIL) est noire.
4. Si un nœud est rouge, alors ses deux fils sont noirs.
5. Tous les chemins descendants reliant un nœud donné à une feuille (du sous arbres dont il
est la racine) contiennent le même nombre de nœuds noirs.
Dans un arbre binaire de recherche, la hauteur noire d’un nœud 𝑥 est le nombre de nœuds noirs
d’un chemin partant de ce nœud (le nœud en question n’est pas compté) vers une feuille, et on la
note 𝑏ℎ(𝑥). De toute évidence, la hauteur noire d’un arbre rouge-noir est donc la hauteur noire
de sa racine. Un exemple d’arbre rouge-noir de hauteur noire 3 est représenté à la figure 4.

Comme nous l’avons dit plus haut, les opérations de recherche dans un arbre binaire de recherche
sont de l’ordre de 𝑂(ℎ) avec ℎ étant la hauteur de l’arbre. En considérant sa hauteur, le lemme
suivant nous montre pourquoi les arbres rouge-noir sont de bons arbres de recherche

Lemme : Un arbre rouge-noir ayant n nœuds internes à une hauteur au plus égale à 2
log2(𝑛 + 1)

Page 8
Preuve : Commençons par montrer que le sous arbre enraciné en un nœud x quelconque contient
au moins 2𝑏ℎ(𝑥) − 1 nœuds internes. Cette affirmation peut se démontrer par récurrence sur la
hauteur de x. Si la hauteur de x est 0, alors x est obligatoirement une feuille (nil[T]) et le sous arbre
enraciné en x contient effectivement au moins 2𝑏ℎ(𝑥) − 1 = 20 − 1 = 0 nœuds internes. Pour
l’étape inductive, soit un nœud interne x de hauteur positive ayant deux enfants. Chaque enfant a
une hauteur noire 𝑏ℎ(𝑥) ou 𝑏ℎ(𝑥) − 1, selon que sa couleur est rouge ou noire. Comme la hauteur
d’un enfant de x est inférieure à celle de x lui-même, on peut appliquer l’hypothèse de récurrence
pour conclure que chaque enfant a au moins 2𝑏ℎ(𝑥)−1 − 1 nœuds internes. Le sous arbre de racine
x contient donc au moins (2𝑏ℎ(𝑥)−1 − 1) + (2𝑏ℎ(𝑥)−1 − 1) + 1 = 2𝑏ℎ(𝑥) − 1 nœuds internes, ce qui
démontre l’assertion.
Pour compléter la preuve du lemme, appelons h la hauteur de l’arbre. D’après la propriété 4 sur
les arbres rouges noirs, au moins la moitié des nœuds d’un chemin simple reliant la racine à une
feuille, racine non comprise, doivent être noirs. En conséquence, la hauteur noire de la racine doit
valoir au moins ; donc, 𝑛 .
En faisant passer le 1 dans le membre gauche et en prenant le logarithme des deux membres, on
obtient.

, 𝑠𝑜𝑖𝑡 ℎ ≤ 2 log (𝑛 + 1)

Pour simplifier le traitement des conditions aux limites dans la programmation des arbres
rougenoir, on utilise une même sentinelle pour représenter NIL. Pour un arbre rouge-noir T, la
sentinelle nil[T] est un objet ayant les mêmes champs qu’un nœud ordinaire. Son champ couleur
vaut NOIR, et ses autres champs (p, gauche, droite et clé) peuvent prendre des valeurs
quelconques. Comme le montre l’Erreur ! Source du renvoi introuvable. (b), tous les pointeurs
versss NIL sont remplacés par des pointeurs vers la sentinelle nil[T].

Figure 4 : Arbre rouge noir avec des nœuds nil

(a) Chaque feuille, représentée par (NIL), est noire. Chaque nœud non-NIL est étiqueté par sa
hauteur noire ; les NIL ont une hauteur noire égale à 0.

Page 9
 Figure 5 : Arbre rouge noir avec un seul nil

(b) Le même arbre rouge noir, mais où chaque NIL est remplacé par la sentinelle nil[T], qui est
toujours noire, et où les Hauteurs noirs sont omises. Le parent de la racine est aussi la
sentinelle.

Figure 6 : Arbre rouge noir sans nœuds nil

(c) Le même arbre rouge-noir, mais où les feuilles et le parent de la racine ont été entièrement
omis. Nous emploierons ce style de représentation dans le reste du chapitre

Le principal intérêt des arbres rouge-noir est qu’ils offrent la meilleure

garantie sur le temps d’insertion, de suppression et de recherche dans les
cas défavorables. Ceci leur permet non seulement d’être utilisable dans
les applications en temps réel, mais aussi de servir comme fondement
d’autres structures de données à temps d’exécution garanti dans les cas
défavorables, par exemple en géométrie algorithmique (domaine de
l'algorithmique qui traite des algorithmes manipulant des concepts
géométriques). De plus, cette structure est économe en mémoire,
puisqu’elle ne requiert qu’un bit supplémentaire d’informations par
élément par rapport à un arbre binaire classique.

Page 10
2. Operations sur les arbres rouges noires

a. Insertion
L’insertion d’un nœud dans un arbre rouge noir se fait exactement
comme dans un arbre binaire de recherche simple, a la seule
exception que ce nœud prend la couleur rouge (si ce nœud prenait
la couleur noire, on violerait la propriété 5 qui définit la hauteur
noire dans un arbre rouge-noir.), et deux feuilles nil[T] lui sont
attribuées, afin de ne pas violer la propriété 3 des arbres binaires de
recherche. Ce qui se passe ensuite dépend de la couleur des nœud
‘‘voisins’’ a ce nœud nouvellement inséré. Remarquer qu’à la suite
de cette insertion telle qu’expliqué plus haut, la propriété 2 ou la
propriété 4 des arbres rouge-noir pourraient être violées. Plusieurs
cas de figures sont envisageables tel qu’expliqués ici-bas.
Cas No 1 : le nœud N est la racine de l’arbre.
Dans ce cas ce nœud est simple repeint en noir, et toutes les
propriétés de l’arbre rouge noir sont vérifiées.

Cas No 2 : le Père P de N est noir.

Dans ce cas, l’arbre résultant reste toujours rouge-noir, aucune des
5 propriétés de l’arbre rouge-noir n’étant pas violée.
Dans les cas 3-5, il est supposé et vérifiable que N a un grand parent
G, car son parent étant rouge, ne peut pas être la racine qui est
forcément noir. De plus, N a un oncle que l’on note U (même si ce
nœud peut être une feuille)
Cas No 3 : le père P et l’oncle U de N sont rouges.
Dans ce cas, P et U changent de couleur et deviennent noir, tandis
que G prend la couleur rouge de noir qu’il était, afin de conserver
la propriété 5 (Egalite de la hauteur noire) de l’ABR. G prenant la
couleur rouge pourrait de nouveau violer la propriété 4 concernant
les enfants d’un nœud rouge, ou la propriété 2 (la racine doit
toujours être noire). Si une de ces propriétés est violée, alors on
reprend le cycle en considérant le nœud problématique G, et on se
repère dans l’un des 5 cas présenté pour la résolution du problème.
Cas No 4 : le père P de N est rouge, tandis que l’oncle U de N est
noir, et le nœud N est l’enfant droit de son père P.
Dans ce cas, le nœud problématique N devient son père P, et on
effectue une rotation gauche de l’arbre autour de P, ensuite, le
nouveau père de N prend la couleur N, le grand père G de N prend
la couleur rouge, et une nouvelle rotation droite de l’arbre autour
de G est effectuée. Si un problème se retrouve encore au niveau du
nouveau nœud N, le cycle recommence, et on identifie dans quel
cas on se trouve.

Page 11
 Cas No 5 : le père P de N est rouge, tandis que l’oncle U de N est
noir, et le nœud N est l’enfant gauche de son père P.
Dance ce cas, la couleur de son père P devient noire, celle de son
grand père G devient rouge, et on effectue une rotation droite de
l’arbre autour de du grand-père G de N. Si un problème se retrouve
encore au niveau du nouveau nœud N, le cycle recommence.

Note : Deux cas de figures se présentent encore (Cas No 6 et Cas No 7), qui
sont les symétriques respectifs des Cas No 4 et Cas No 5, chaque gauche
devenant droit, et chaque droit devenant gauche.
Aux exceptions du premier et du second cas (Cas élémentaires),
tous les autres cas de figure expliqués plus haut se retrouvent dans
l’algorithme de correction présenté ci bas

b.

Page 12
Un exemple d’insertion est présenté ici-bas : nous insérons un
nœud avec une clé de 4 dans l’arbre proposé.

Page 13
 Figure 8 : Figure montrant 4 cas d’insertion dans un arbre rouge-noir

b. Suppression
Pour supprimer un élément dans un arbre rouge et noir, on commence par appliquer l’algorithme
de suppression pour les arbres de recherche. Si l’élément supprimé était de couleur rouge, aucune
des propriétés des arbres rouge et noir n’est violée. Par contre, si le nœud supprimé était noir la
propriété 4 (tous les chemins descendants d’un nœud à une feuille contiennent le même nombre
de nœuds noirs) peut être violée. Le code ci-dessous présente l’algorithme de suppression avec

Page 14
utilisation de sentinelles et appel de l’algorithme de correction celui qui répartit les « noirs »
surnuméraires.

ARBRE_RN_SUPPRESSION(T,x)
1 si gauche(x)=NIL et droit(x) alors
2 si père(x)=NIL alors
3 racine(T)=NIL
4 sinon
5 si x=gauche(père(x)) alors
6 gauche(père(x)) ←NIL
7 sinon droit(père(x)) ←NIL
8 si couleur(x)=noir alors
9 RN_CORRECTION(T,x)
10 sinon si gauche(x)=NIL et droit(x)=NIL alors
11 si gauche(x) NIL alors
12 filsde_x=gauche(x)
13 sinon filsde_x=droit(x)
14 père(filsde_x) ←père(x)
15 si père(x) = NIL alors
16 racine(T )← filsde_x
17 sinon si gauche(père(x)) = x alors
18 gauche(père(x)) ← filsde_x
19 sinon droit(père(x)) ← filsde_x
20 si couleur(x) = NOIR alors
21 RN_CORRECTION(T , filsde_x)
22 sinon
23 min ← ARBRE_MINIMUM(droit(x))
24 clé(y) ←clé(min)
25 ARBRE-RN-SUPPRESSION(T,min)
26 renvoyer racine(T )

RN-CORRECTION(T , x)

1 tant que x 6= racine(T) et couleur(x) = NOIR faire

2 si x = gauche(père(x)) alors
3 w ← droit(père(x))

Page 15
4 si w=NIL alors
5 x=père(x) ;
6 si x=gauche(père(x)) alors
7 w= gauche(père(x))
8 sinon w= droit(père(x))
9 sinon si couleur(w) = ROUGE alors
10 couleur(w) ← NOIR
11 couleur(père(w)) ← ROUGE
12 ROTATION-GAUCHE(T , père(x))
13 w ← droit(père(x))
14 sinon si couleur(gauche(w)) = NOIR et couleur(droit(w)) = NOIR alors
15 couleur(w) ← ROUGE
16 x ← père(x)
17 sinon
18 si couleur(droit(w)) = NOIR alors
19 couleur(gauche(w)) ← NOIR
20 couleur(w) ← ROUGE
21 ROTATION-DROITE(T , w)
22 w ← droit(père(x))
23 couleur(w) ← couleur(père(x))
24 couleur(père(x)) ← NOIR
25 couleur(droit(w))) ← NOIR
26 ROTATION-GAUCHE(T , père(x))
27 x ← racine(T)
28 sinon (même chose que précédemment en échangeant droit et gauche)
couleur(x) ← NOIR

c. Roation
sLorsqu’on exécute les opérations ARBRE-INSÉRER et ARBRE-
SUPPRIMER sur un arbre rouge-noir à n clés (Nous verrons ces
procédures plus bas), prennent un temps O (lg n). Comme elles
modifient l’arbre, le résultat pourrait violer les propriétés d’arbre
rouge-noir énumérées plus haut, Pour restaurer ces propriétés, il
faut changer les couleurs de certains nœuds de l’arbre et également
modifier la chaîne des pointeurs. Pour retrouver les propriétés de
l’arbre rouge-noir, nous utilisons un algorithme rotation.
Les rotations préservent la propriété des arbres de recherche mais
pas la propriété des arbres rouge et noir.

ROTATION
-DROITE (T, y)

ROTATION
-GAUCHE (T, x)

Page 16
 Figure 7 : Rotations sur un arbre binaire de recherche
Les opérations de rotation sur un arbre de recherche binaire.
L’opération ROTATION-GAUCHE (T, x) transforme la
configuration des deux nœuds de gauche pour aboutir à celle de
droite, en modifiant un nombre constant de pointeurs. La
configuration de droite peut être transformée en celle de gauche par
l’opération inverse ROTATION-DROITE (T, y). Les deux nœuds
peuvent se trouver n’importe où dans l’arbre binaire de recherche.
Les lettres A, B et C représentent des sous arbres arbitraires. Une
opération de rotation préserve la propriété d’arbre binaire de
recherche : les clés de A précèdent clé[x], qui précède les clés de
B, qui précède clé[y], B qui précède les clés de C.
Le pseudo code de ROTATION-GAUCHE suppose que
droite[x]≠nil[T] et que le parent de la racine est nil[T].

3. Complexité
Il est important de rappeler que peu importe l’opération que l’on effectue sur les arbres rouges
noires la complexité est fonction de la hauteur h de l’arbre et a été démontré en avant partie.

En guise de résumé cette complexité s’exprime comme suit :

, 𝑠𝑜𝑖𝑡 ℎ ≤ 2 log(𝑛 + 1) s
IV Arbre binaire de Recherche et arbre rouge noir

1. Comparaison
Les arbres rouges et noires sont une variante des arbres binaires de recherche. Leur principal intérêt
est qu’ils sont relativement équilibrés. On considère ici des arbres binaires de recherche ou les
nœuds sont portées par les nœuds internes. Les feuilles ne sont pas prises dans la hauteur de l’arbre.

Page 17
 2. Domaine d’application

Enormément d’applications, que ce soit dans le domaine d’informatique ou pas on voit que les
arbres binaires d’une manière générale on une aisance dans la structuration et manipulation des
données.

En informatique, pour implémenter des types des données abstraites tels que des ensembles
dynamiques, des tables de recherche et des files d’attente prioritaire.

Exercices
Comme complément nous proposons une série des exercices sur les arbres binaires de recherche et
arbre rouge noire pour nous édifier davantage dans la compréhension du thème.

Exercice 1
Soit la liste de valeurs L = {0,5,11,16,20,35,38,120,207,1018}.

1. Construire un arbre binaire de recherche contenant la liste de valeurs L en veillant

minimiser sa hauteur.

2. Proposer un algorithme d’ajout d’un élément dans un ABR, puis calculer sa

complexité.

3. Ajouter l’arbre les valeurs A = {1,10,15,618,1011}.

4. Proposer un algorithme de recherche d’un élément dans un ABR, puis calculer sa

complexité.

5. Combien de comparaisons avec les éléments de l’arbre doivent Etre effectués dans la
recherche des valeurs R = {3,16,58} en partant de la racine de l’arbre chaque fois.

6. Supprimer de l’arbre les valeurs S ={207,11,20,35} en partant du nœud qui contient

la valeur chaque fois.

Exercice 2

On considère le dernier ABR de l’exercice précèdent.

1. Proposer des algorithmes récursifs pour les parcours préfixe, infixe et post fixe (ou
suffixe), puis calculer leur complexité.

2. Lister les éléments de l’arbre avec des parcours préfixe, infixe et post fixe.
3. Proposer des algorithmes pour énumérer dans l’ordre croissant/décroissant les
éléments d’un ABR, puis calculer leur complexité.

Page 18
 4. Proposer des algorithmes pour déterminer les valeurs minimale et maximale d’un
ABR, puis calculer leur complexité.

5. Proposer des algorithmes pour déterminer le successeur/prédécesseur d’un élément

d’un ABR dans l’ordre croissant, puis calculer leur complexité.

6. Donner le successeur et le prédécesseur des valeurs 1, 5 et 207 et préciser les nœuds

de l’arbre par lesquels il faut passer pour trouver ces valeurs.

Exercice 3
On considère le dernier ABR de l’exercice 1.

1. Définir les algorithmes de rotation droite et gauche d’un sous arbre.

2. Valeur la complexité de ces algorithmes.
3. Appliquer une suite de rotations pour Equilibrer l’arbre.

Exercice 4
Soit la liste de valeurs L ={0,1,5,10,15,16,38,120,618,1011,1018}.

1. Construire un ABR rouge noir contenant la liste de valeurs L.

2. Proposer un algorithme d’ajout d’un élément dans un ARN, puis calculer sa
complexité.

3. Ajouter l’arbre les valeurs A ={60,150,200}.

Page 19
Travaux pratiques

Comme complément des travaux pratiques nous proposons une implémentation en langage sur le
compilateur C (code block) de nos différentes fonctions déjà écrites en algorithmique pour une
bonne compréhension et obtenir les résultats sur nos machines.

Donc les fonctions d’insertion, de rotation, de suppression, de recherche des arbres binaires de
recherche y compris les arbres rouges noires. En particulier les fonctions de parcours sur les arbres
binaires de recherche et en fin de compte une fonction de rotation sur les arbres rouges noires.

Bibliographie
Algorithme et représentations des données (évaluations, arbres, graphes et analyses
de textes). M. LUCAS
Cours de structures de donnes de : professeur KENGNET VIANNEY (années
2021-2022).
Webographie
https://fr.wikipedia.org/wiki/Arbre_bicolore
https:/www.cs.princeton.edu/~rs/talks/LLRB/RedBlack

Page 20