Algorithmique avancé cheatsheet

#Structure

typedef struct node {
    int value;
    struct node *leftSubtree, *rightSubtree;
} Node, *BinaryTree;

#Complexités

• Recherche o(h)
• Insertion o(h)
• Suppression o(h)

#Inconvénients

• Il peut être dégénéré
  • Les complexités deviennent :
    • Recherche o(n)
    • Insertion o(n)
    • Suppression o(n)

#Pseudo-codes

• Suppression

1) Recherche le noeud n où se toruve k
2) Si n est une feuille, supprimer n
3) Si n n'a pas de fils gauche
   -> Recoller le fils droit
4) Si n n'a pas de fils droit
   -> Recoller le fils gauche
5) Sinon
   a) Aller chercher le max à gauche de n
   b) Le supprimer 
   c) remplacer la valeur de n par le max

#Définitions

#Propriétés

Un arbre est rouge noir si :

• Chaque noeud est soit rouge, soit noir
• Tous les noeuds NULL ainsi que la racine sont noirs;
• Un noeud rouge n'a pas d'enfant rouge;
• Tous les chemins d'un noeud à ses descendants NULL traversent le même nombre de sommets noirs (C'est la hauteur noire)

#Structure

typedef struct rbnode {
    int value;
    int color;
    struct rbnode *leftSubtree, *rightSubtree;
    struct rbnode *father ;
} RBNode, *RBBinaryTree;

#Complexités

• Recherche o(log n)
• Insertion o(log n)
• Suppression o(log n)

#Pseudo-code

• Insertion

1) On insère le noeud comme un ABR classique (il aura la couleur rouge)
2) On regarde si la racine est rouge -> On la change à noire
3) On rééquilibre le noeud que nous venons d'ajouter

• Rééquilibrage d'un noeud

Le noeud que nous devons rééquilibrer est noté n
1) On regarde si le parent de n est rouge et si n est rouge
    a) Si l'oncle de n est rouge : 
        aa) L'oncle devient noir
        ab) Le parent de n devent noir
        ac) Le parent du parent de n devient rouge
        ad) On rééquilibre le parent du parent de n
    b) Si l'oncle de n est noir
        ba) Si le noeud inséré est full à gauche ou full à droite
            baa) Si le noeud inséré est full à gauche
                On fait une rotation droite à partir du parent du parent de n
            baa) Si le noeud inséré est full à droite
                On fait une rotation gauche à partir du parent du parent de n
        bb) Sinon
            bba) Si le noeud inséré est gauche puis droite
                On fait une rotation gauche à partir du parent de n
                On rééquilibre le fils gauche de n
            bbb) Si le noeud inséré est droite puis gauche
                On fait une rotation droite à partir du parent de n
                On rééquilibre le fils droit de n

Exemples de rééquilibrage de noeud dans le cours

#Définitions

Rotation :

Comme un ABR classique mais on ajoute de l'aléa aux algorithmes d'insertion et de suppression pour éviter les arbres dégénérés

#Structure

typedef struct node {
    int value;
    struct node *leftSubtree, *rightSubtree;
    int size;
} Node, *BinaryTree;

#Complexités

• Recherche o(log n)
• Insertion o(log n)
• Suppression o(log n)

#Fonction split

K est le nombre à partir duquel on veut splitter notre arbre.

3 manières de splitter :

• Si K = racine(Arbre)

• Si K > racine(Arbre)

• Si K < racine(Arbre)

#Insertion

L'insertion utilise la fonction split et se déroule comme suit :

Insertion(arbre, k)
    taille <- la taille de l'arbre (le nombre de noeud)
    hasard <- calcul d'un nombre au hasard entre 0 et 1
    si hasard < 1/taille + 1 alors
        on insère k à la racine de arbre
            arbreGauche, arbreDroit = split(arbre, k)
            on ajoute k à la racine de arbreDroit
    sinon 
        si k > arbre.valeur
            Insertion(arbre.partieDroite, k)
        sinon
            Insertion(arbre.partieGauche, k)
        fin
    fin

#Fonction join

Nous voulons join l'arbre vert et l'arbre rouge suivant :

On tire p, un nombre au hasard entre 1 et taille de l'arbre vert + taille de l'arbre rouge

Si p < taille a, la fonction retourne

Si p > taille a, la fonction retourne

#Fonction suppression

Pour supprimer, on utilise cette fonction :

Suppression(Arbre A, k)
    Si racine(A) = k
        Retourne Join(Arbre.arbreGauche, Arbre.arbreDroit)
    Sinon
        Si racine(A) < k 
            copie = copie(a)
            copie.arbreDroit = supprimer(copie.arbreDroit, k)
            retourne copie
        Sinon
            copie = copie(a)
            copie.arbreGauche = supprimer(copie.arbreGauche, k)
            retourne copie
        Fin
    Fin