diff options
Diffstat (limited to 'semestre 3/structures des données/9- Arbre rouge-noir.md')
| -rw-r--r-- | semestre 3/structures des données/9- Arbre rouge-noir.md | 38 |
1 files changed, 37 insertions, 1 deletions
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 |