9 files changed, 159 insertions, 19 deletions
diff --git a/semestre 3/structures des données/3- Hash.md b/semestre 3/structures des données/3- Hash table.md
index d200204..c659419 100644
--- a/semestre 3/structures des données/3- Hash.md
+++ b/semestre 3/structures des données/3- Hash table.md
@@ -76,7 +76,7 @@ On a besoin de stocker le pointeur
 ### Collision par adressage ouvert
 Cherche à résoudre les problèmes des listes chaînées
 
-Maintenant, une case une ne contient qu'un élément
+Maintenant, une case ne contient qu'un élément
 |> quand une case contient déjà un élément, on en cherche une autre à l'aide d'une méthode de *probing*
 
 *Probing* détermine une nouvelle case à partir de l'ancienne
diff --git a/semestre 3/structures des données/5- File de priorité.md b/semestre 3/structures des données/5- File de priorité.md
index b1987a5..acad05f 100644
--- a/semestre 3/structures des données/5- File de priorité.md
+++ b/semestre 3/structures des données/5- File de priorité.md
@@ -5,8 +5,11 @@ tags:
   - structure-des-données
 semestre: 3
 ---
-**Rattraper la définition**
-
+Les files de priorité servent à trouver le minimum/maximum d'un ensemble
+|> clé/valeur avec la clé donnant le niveau de priorité
+|> ajout doit être simple
+|> recherche/extraction du min (resp. max) doit aussi être simple
+## Implémentation naïve
 Implémentation naïve en liste chaînée, son extraction est en $O(n)$ pour récupérer la valeur minimum
 |> utilisation d'une liste chaînée triée permet d'éviter ça, mais on se retrouve à être en $O(n)$ pour l'insertion
 -> on fait sûrement des opérations en trop car à chaque fois on trie tout
@@ -56,10 +59,13 @@ int indiceFilsDroit(int i){
 Voir le diapo pour les tests d'existence
 
 Pour ajouter un élément, on :
-1. ajoute l'élément tout en bas
-2. tant que l'élément est plus grand que son père, on les échange
+1. ajoute l'élément tout en bas (i.e. le plus au fond du tableau)
+2. tant que l'élément est plus petit (resp. plus grand) que son père, on les échange
 -> elle est en $O(\log_2 n)$ (car au pire on remonte à la racine)
 
 Voir le diapo pour la fonction d'ajout implémenté
 
-Voir le diapo pour l'extraction
-\ No newline at end of file
+Pour extraire le plus petit (resp. max) élément, on :
+1. remplace la racine par son plus grand (resp. plus petit) fils
+2. tant que l'élément est plus grand (resp. plus petit) qu'un de ses fils, on les échange
+-> elle est aussi en $O(\log n)$
+\ No newline at end of file
diff --git a/semestre 3/structures des données/6- Arbre binaire de recherche.md b/semestre 3/structures des données/6- Arbre binaire de recherche.md
index 78ef0c9..5213da7 100644
--- a/semestre 3/structures des données/6- Arbre binaire de recherche.md
+++ b/semestre 3/structures des données/6- Arbre binaire de recherche.md
@@ -15,8 +15,8 @@ On note $h$ sa hauteur
 Il s'agit de la même implémentation que pour les btree.
 
 min et max sont plus simples
-|> pour le min, on regarde à gauche -> $O(\log n)$
-|> pour le max, on regarde à droite -> $O(\log n)$
+|> pour le min, on regarde à gauche -> $O(h)$
+|> pour le max, on regarde à droite -> $O(h)$
 
 **Voir diapo pour toutes les implémentations standards**
 
@@ -37,7 +37,7 @@ Quand on supprime, on doit remonter une valeur
 Cette structure cherche à équilibrer l'ABR pour avoir une relation entre $n$ et $h$
 |> besoin de gérer l'insertion et la suppression -> est compliqué de gérer ça
 
-On a donc créer l'AVL qui est un ABR équilibré
+On a donc créer l'AVL qui esqqqqqqt un ABR équilibré
 |> propriété d'équilibre = la différence des hauteurs des fils gauche et droit de tout nœud ne peut excéder 1
 |> on a donc $h=\log n$
 -> tout devient en $\log n$ 🎉
@@ -98,11 +98,11 @@ AVL* rotGauche(AVL* racine) {
 1. comme dans un ABR
 2. tant que la diff de hauteur entre les fils gauche et droit ne dépassent pas 1, on continue de remonter
 3. on note $A$ le premier ancêtre où cette différence dépasse 1
-4. Si $h(G) - h(D) = 2$, alors
-	1. si $h(G) < h(D)$, on fait une rotation à gauche de $G$
+4. Si $h(G) - h(D) = 2$, alors ($g$ et $d$ sont les sous-arbres de $G$)
+	1. si $h(g) < h(d)$, on fait une rotation à gauche de $G$
 	2. on fait une rotation à droite de $A$
-5. Si $h(G)-h(D)=-2$, alors
-	1. si $h(D) < h(G)$, on fait une rotation à droite de $D$
+5. Si $h(G)-h(D)=-2$, alors ($g$ et $d$ sont les sous-arbres de $G$)
+	1. si $h(d) < h(g)$, on fait une rotation à droite de $D$
 	2. on fait une rotation à gauche de $A$
 6. On a fini le traitement
 
@@ -110,13 +110,15 @@ Insertion est en $O(\log n)$
 
 **Suppression**
 1. comme dans un ABR
-2. Si le nœud supprimé n'a pas été remplacé par un autre nœud, ou s’il a été remplacé par son unique fils, on examine ses ancêtres en remontant jusqu’à la racine
-3. S’il a été remplacé par le max de son fils gauche (ou le min de son fils droit), alors on examine tous les ancêtres de ce dernier en remontant jusqu’à la racine.
+2. Si le nœud supprimé n'a pas été remplacé par un autre nœud, ou s’il a été remplacé par son unique fils, on examine ses ancêtres en remontant jusqu'à la racine
+3. S’il a été remplacé par le max de son fils gauche (ou le min de son fils droit), alors on examine tous les ancêtres de ce dernier en remontant jusqu'à la racine.
 4. Durant la remonté
 	1. si la différence est inférieur ou égal à 1, on met à jour la hauteur
 	2. si la différence est supérieure à 1, on applique les mêmes transformations que pour l'insertion
 
 Suppression est en $O(\log n)$
+
+Étape 2 ou 3 permet de choisir à partir d'où remonter
 ## Tableau associatif
 Les AVL peuvent être pertinent pour les tableaux associatifs
 
diff --git a/semestre 3/structures des données/7- Graphe.md b/semestre 3/structures des données/7- Graphe.md
index 6c2e56b..d817917 100644
--- a/semestre 3/structures des données/7- Graphe.md
+++ b/semestre 3/structures des données/7- Graphe.md
@@ -33,6 +33,4 @@ Deux implémentations classiques
 |> liste d'adjacence -> $O(n)$, mais prend peu de places
 -> d'autres implémentations existent et peuvent être préférables lors de certains algo
 
-**Voir le diapo pour la def de matrices et listes d'adjacence**
-
-:(
-\ No newline at end of file
+**Voir le diapo pour la def de matrices et listes d'adjacence**
+\ No newline at end of file
diff --git a/semestre 3/structures des données/8- Parcours de graphe.md b/semestre 3/structures des données/8- Parcours de graphe.md
index 4bfab39..f813dc1 100644
--- a/semestre 3/structures des données/8- Parcours de graphe.md
+++ b/semestre 3/structures des données/8- Parcours de graphe.md
@@ -95,3 +95,16 @@ Complexité temporelle, chaque ligne de code est exécuté :
 Occupation mémoire est similaire pour itérative et récursive pour des $n$ pas trop grand
 |> par contre, comme récursive n'est pas terminal, elle prendra plus de place pour des $n$ très grands
 ### Parcours en largeur
+```
+L = Liste(r)
+Tant que B(L) n'est pas vide
+	Choisir un sommet s dans B(L) qui est successeur (ou voisin) du premier sommet ouvert de L
+	L = union de L et {s}
+Fin Tant que
+```
+
+Le code *itératif* est similaire au parcours en profondeur
+|> on remplace juste la pile par une file
+
+1. Comme dans un ABR
+2. Si nœud est remplacé par
+\ No newline at end of file
diff --git a/semestre 3/structures des données/9- Arbre rouge-noir.md b/semestre 3/structures des données/9- Arbre rouge-noir.md
index 658c4e1..58629f8 100644
--- a/semestre 3/structures des données/9- Arbre rouge-noir.md
+++ b/semestre 3/structures des données/9- Arbre rouge-noir.md
@@ -15,9 +15,45 @@ Arbre rouge-noir
 |> AVL demandant moins de rotations
 |> racine est noire
 |> fils d'un rouge est noir
-**voir le diapo pour les autres specs**
+|> si un nœud a moins de deux fils, on considère que les fictifs sont noirs
+|> le nombre de nœuds noirs sur un chemin de la racine vers une feuille est toujours le même
+
+Hauteur est toujours en $O(\log n)$ (on l'appelle *hauteur noire*)
+-> les preuves sont sur le diapo
 
 Problème de ces arbres
 |> beaucoup de cas à gérer
+
+```mermaid
+flowchart TB
+	GP[Grand-père] --- P[Père]
+	GP --- O[Oncle]
+	P --- X
+	P --- Frère
+```
+
+**Insertion** -> le nœud est rouge
+1. Si père est noir, on termine
+2. Si c'est la racine, on le met en noir et on termine
+3. Si père est rouge *et* oncle est rouge, alors
+	- père devient noir
+	- oncle devient noir
+	- grand-père devient rouge
+	- on fait un appel récursif sur grand-père
+4. Dans tous les autres cas
+	1. Si père est un fils gauche
+		- seulement si c'est un fils droit, rotation gauche (X et père inversent leurs places)
+		- père devient noir
+		- grand-père devient noir
+		- rotation droite de grand-père
+	2. Si père est un fils droit
+		- seulement si c'est un fils gauche, rotation droite (X et père inversent leurs places)
+		- père devient noir
+		- grand-père devient rouge
+		- rotation gauche de grand-père
+
+Est en $O(\log n)$
+
+**Rattraper la suppression**
 ## Skip lists
 -> ici, on s'occupe des la concurrence
 \ No newline at end of file
diff --git a/semestre 3/structures des données/contenu feuille exam.txt b/semestre 3/structures des données/contenu feuille exam.txt
new file mode 100644
index 0000000..7878e17
--- /dev/null
+++ b/semestre 3/structures des données/contenu feuille exam.txt
@@ -0,0 +1,41 @@
+Hash
+|> complexité
+|> facteur de charge
+
+ABR
+|> vérif rapide
+|> insertion (rapide)
+|> suppression (rapide)
+
+AVL
+|> maj hauteur
+|> insertion (rapide)
+|> suppression
+
+Graphe
+|> defs
+|> parcours
+
+Tas
+|> indices et existence
+|> insertion (rapide)
+|> supression (rapide)
+
+Skip list
+|> insertion (rapide)
+|> supression (rapide)
+
+ARN
+|> insertion
+|> supression (début)
+
+Partition via Hash
+|> principe (rapide)
+
+Forêt
+|> principe (rapide)
+|> heuristique (rapide)
+
+Tas binomial
+|> principe (rapide)
+====================================
diff --git a/semestre 3/structures des données/td/td10/exo1.md b/semestre 3/structures des données/td/td10/exo1.md
new file mode 100644
index 0000000..de1467a
--- /dev/null
+++ b/semestre 3/structures des données/td/td10/exo1.md
@@ -0,0 +1,10 @@
+---
+tags:
+  - sorbonne
+  - informatique
+  - structure-des-données
+  - td
+semestre: 3
+---
+Pour récupérer les compostes connexes naïvement, durant un parcours, on liste par où on passe
+|> à chaque fois qu'on a besoin de régénérer un parcours, on crée une nouvelle composante connexe
+\ No newline at end of file
diff --git a/semestre 3/structures des données/td/td8/exo2.c b/semestre 3/structures des données/td/td8/exo2.c
new file mode 100644
index 0000000..e0cb279
--- /dev/null
+++ b/semestre 3/structures des données/td/td8/exo2.c
@@ -0,0 +1,34 @@
+#include <stdlib.h>
+typedef struct arc {
+    int v;
+    struct arc *suiv;
+} Arc;
+
+typedef struct sommet {
+    int u;
+    Arc *L_succ;
+    Arc *L_prec;
+} Sommet;
+
+typedef struct {
+    int nbsom;
+    Sommet *t_som;
+} Graphe;
+
+void creeGraphe(Graphe *G, int n){
+    G->nbsom = n;
+    G->t_som = (Sommet*) malloc(sizeof(Graphe)*n);
+}
+
+void ajoutArc(Graphe *G, int i, int j){
+    Arc *arcIn = (Arc*) malloc(sizeof(Arc));
+    arcIn->v = i;
+    Arc *arcOut = (Arc*) malloc(sizeof(Arc));
+    arcIn->v = j;
+    Sommet a = G->t_som[i];
+    Sommet b = G->t_som[j];
+    arcIn->suiv = a.L_succ;
+    a.L_succ = arcIn;
+    arcOut->suiv = b.L_prec;
+    a.L_prec = arcOut;
+}