From ecf05510045b2ac78b479ae746a43078e22cee4f Mon Sep 17 00:00:00 2001 From: Anhgelus Morhtuuzh Date: Mon, 8 Dec 2025 14:13:46 +0100 Subject: =?UTF-8?q?Cours=20du=201=20au=205=20d=C3=A9cembre?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- .../6- Arbre binaire de recherche.md" | 67 +++++++++++++++++++++- 1 file changed, 65 insertions(+), 2 deletions(-) (limited to 'semestre 3/structures des données/6- Arbre binaire de recherche.md') diff --git "a/semestre 3/structures des donn\303\251es/6- Arbre binaire de recherche.md" "b/semestre 3/structures des donn\303\251es/6- Arbre binaire de recherche.md" index d544129..78ef0c9 100644 --- "a/semestre 3/structures des donn\303\251es/6- Arbre binaire de recherche.md" +++ "b/semestre 3/structures des donn\303\251es/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 -- cgit v1.2.3