From 42e9569176360b5e1881d317c74ce8522a2af6d1 Mon Sep 17 00:00:00 2001 From: Anhgelus Morhtuuzh Date: Tue, 20 Jan 2026 13:55:21 +0100 Subject: Derniers cours du S3 --- .../9- Arbre rouge-noir.md" | 38 +++++++++++++++++++++- 1 file changed, 37 insertions(+), 1 deletion(-) (limited to 'semestre 3/structures des données/9- Arbre rouge-noir.md') diff --git "a/semestre 3/structures des donn\303\251es/9- Arbre rouge-noir.md" "b/semestre 3/structures des donn\303\251es/9- Arbre rouge-noir.md" index 658c4e1..58629f8 100644 --- "a/semestre 3/structures des donn\303\251es/9- Arbre rouge-noir.md" +++ "b/semestre 3/structures des donn\303\251es/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 -- cgit v1.2.3