Cours du 1 au 5 décembre

3 files changed, 86 insertions, 3 deletions

diff --git a/semestre 3/structures des données/10- Ensemble, partition, file de priorité fusionnable.md b/semestre 3/structures des données/10- Ensemble, partition, file de priorité fusionnable.md
new file mode 100644
index 0000000..32e9a16
--- /dev/null
+++ b/semestre 3/structures des données/10- Ensemble, partition, file de priorité fusionnable.md
@@ -0,0 +1,21 @@
+---
+tags:
+  - sorbonne
+  - informatique
+  - structure-des-données
+semestre: 3
+---
+## Ensemble
+Opérations sur les ensembles :
+- insertion
+- suppression
+- vérification
+- union
+- intersection
+
+On utilise une hash table sans valeur pour représenter un ensemble non ordonnée
+|> permet d'être en $O(1)$ sur la majorité des opérations, l'union est en $O(n)$ et l'intersection en $O(n_1+n_2)$
+|> besoin de réimplémenter la hash table pour enlever la valeur
+
+On peut utiliser des AVL si on cherche à avoir un ordre
+|> plus lent que la hash table (on est 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 d544129..78ef0c9 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
@@ -50,10 +50,73 @@ Lors de la création d'un nœud, on a besoin de calculer la hauteur
 
 Insertion/suppression comme dans un ABR
 |> par contre, si ça déséquilibre, on corrige
-|> pour corriger, on utilise des rotations *voir le diapo*
+|> pour corriger, on utilise des rotations
 -> on ne perd pas en complexité, tout reste en $O(h) = O(\log n)$
 
-*voir le diapo pour le principe précis d'insertion / suppression*
+```mermaid
+flowchart TB
+	r --> g
+	r --> D
+	g --> U
+	g --> V
+```
+rotation vers la droite ->
+```mermaid
+flowchart TB
+	g --> U
+	g --> r
+	r --> V
+	r --> D
+```
+(rotation vers la gauche est dans l'autre sens)
+
+```c title="rotations"
+AVL* rotDroite(AVL* racine) {
+	AVL* r = racine;
+	AVL* g = r->fg; // fils gauche
+	AVL* v = g->fd; // fils droit
+	g->fd = r;
+	r->fg = v;
+	majHauteur(r);
+	majHauteur(g);
+	return g;
+}
+
+AVL* rotGauche(AVL* racine) {
+	AVL* g = racine;
+	AVL* r = g->fg; // fils gauche
+	AVL* v = r->fd; // fils droit
+	g->fd = v;
+	r->fg = r;
+	majHauteur(r);
+	majHauteur(g);
+	return g;
+}
+```
+
+**Insertion**
+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$
+	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$
+	2. on fait une rotation à gauche de $A$
+6. On a fini le traitement
+
+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.
+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)$
 ## Tableau associatif
 Les AVL peuvent être pertinent pour les tableaux associatifs
 
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 621b21e..658c4e1 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
@@ -5,7 +5,6 @@ tags:
   - structure-des-données
 semestre: 3
 ---
-
 Problème de l'AVL
 |> besoin de faire des rotations, ce qui transforme tout le graphe
 |> concurrence impossible, change beaucoup en mémoire -> est très morcelé (donc défaut de page)