diff options
Diffstat (limited to 'semestre 3/structures des données')
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) |