name: inverse layout: true class: center, middle, inverse --- # INFORMATIQUE 3 - CM 6 ## Inès de Courchelle ## 2023-2024
--- layout: false # Rappel - ABR ## Définition Un arbre binaire de recherche(ABR) est un arbre binaire dans lequel : - les valeurs du sous arbre de gauche sont inférieur à la racine a - les valeurs du sous arbre de droite sont supérieur à la racine a - tout sous arbre de a est un ABR ## Exemple
--- # Rappel - ABR ## Les opérations 1. Recherche 2. Insertion 3. Minimum 4. Maximum 5. Suppression --- # Rappel - ABR ## La complexité - meilleur : Ο(log n), si l'arbre est équilibré - pire cas : Ο(n), si l'arbre est dégénéré ## En gros Les arbres binaires sont des cas particuliers d'arbre : dans un arbre binaire, on a au maximum 2 branches qui partent d'un élément. --- # Les arbres AVL ## Plan 1. Définition 2. Rééquilibrage 3. La rotation --- # Arbre AVL ## Qu'est ce que c'est ? - C'est un arbre binaire équilibré - Il a été inventé en 1962 par Adelson-Velskii et Landis (AVL) .pull-left[ ##### Georgy Adelson-Velsky
] .pull-right[ ##### Evgenii Landis
] --- # Arbre AVL ## Définition C'est un arbre binaire de recherche (ABR) : - Dont les deux sous-arbres d’un même nœud ont une différence de hauteur d’au plus 1 - Qui est auto-équilibrant sur les opérations d'ajout et de suppression ## Complexité pour toutes les opérations \\[O(log_{2}(n))\\]
--- # Problème ABR ## Illustration .pull-left[
] .pull-right[ - On ne gagne rien au niveau de la recherche - Complexité : O(n) ]
## Solution - Obliger l’arbre à être relativement symétrique - Faire en sorte que le sous-arbre gauche soit proche de la hauter du sous-arbre droit --- # Rééquilibrage ## Illustration .pull-left[ ##### Non-AVL
] .pull-right[ ##### AVL
] --- # Équilibrage ## Objectifs - Optimiser la complexité de calcul - Assurer une symétrie dans l'arbre - Garantir une efficacité dichotomique ## Principe La hauteur du fils droit d'un noeud doit être "sensiblement égale" à celle de son fils gauche --- # Équilibrage ## Facteurs - Pour chaque noeud on cosidère sa hauteur - Lors d'une opération de transformation , la propriété de hauteur peut être modifiée - On calcule : \\[facteur = hauteur (sous-arbre droit) - hauteur(sous-arbre gauche) \\] - Il est recalculé après chaque opération - Il permet de définir si un rééquilibrage est nécessaire --- # Équilibrage ## Facteurs
--- # Équilibrage ## Facteurs
#### Facteur du noeud 24 1 --- # Équilibrage ## Facteurs
#### Facteur du noeud 47 0 --- # La rotation ## Simple - Une rotation ne modifie pas l'ordre des noeuds - Respecte le parcours infixe - Deux sens de rotation : gauche ou droite (selon le déséquilibrage) ## Rappel - parcours infixe - On visite chaque noeud aprèes son fils à gauche et avant son fils à droite - La racine est traitée entre les appels sur les sous-arbres gauches et droits --- # Rappel - parcours infixe ## Illustration
[7,2,1,4,3,5,8,0,12,10,13,6,9,14,15,16] --- # La rotation - Simple Droite ## L'algo ```c FONCTION rotationDroite (a : arbre) : arbre VARIABLE b : arbre DEBUT b <- a.filsG a <- creerArbre(a.val, b.filsD, a.filsD) b <- creerArbre(b.val, b.filsG, a) retourner b FIN ``` ## Illustration
--- # La rotation - Simple Droite ## Illustration
--- # La rotation - Simple Droite ## Illustration
--- # La rotation - Simple Droite ## Illustration
--- # La rotation - Simple Droite ## Illustration
--- # La rotation - Simple Droite ## Illustration
--- # La rotation - Simple Droite ## Illustration
--- # La rotation - Simple Droite ## Illustration
--- # La rotation - Simple Droite ## Illustration
--- # La rotation - Simple Droite ## En général
## Objectif Une rotation droite autour du sommet a d'un arbre binaire de recherche consiste à faire descendre le sommet a et à faire remonter son fils gauche b sans invalider l'ordre des éléments. L'opération inverse s'appelle rotation gauche autour du sommet b. --- # La rotation - Simple Droite ## En général
--- # La rotation - Simple Droite ## En général
--- # La rotation - Simple Droite ## En général
--- # La rotation - Simple Gauche ## L'algo ```c FONCTION rotationGauche (b : arbre) : arbre VARIABLE a : arbre DEBUT a <- b.filsD b <- creerArbre(b.val, b.filsG, a.filsG) a <- creerArbre(a.val, b, a.filsD) retourner a FIN ``` ## Illustration
--- # La rotation - Simple Gauche ## Illustration
--- # La rotation - Simple Gauche ## Illustration
--- # La rotation - Simple Gauche ## Illustration
--- # La rotation - Simple Gauche ## Illustration
--- # La rotation - Simple Gauche ## Illustration
--- # La rotation - Simple Gauche ## Illustration
--- # La rotation - Simple Gauche ## Illustration
--- # La rotation - Simple Gauche ## L'algo ```c FONCTION rotationGauche (b : arbre) : arbre VARIABLE a : arbre DEBUT a <- b.filsD b <- creerArbre(b.val, b.filsG, a.filsG) a <- creerArbre(a.val, b, a.filsD) retourner a FIN ``` ## En général
--- # La rotation ## Exemple On vient d'ajouter 13 à un AVL et on obtient l'arbre ci-dessous
#### Où se situe le déséquilibre ? #### Quel est le sens de rotation ? --- # La rotation ## Illustration
--- # La rotation ## Illustration
--- # La rotation ## Illustration
--- # La rotation ## Illustration
--- # La rotation ## Illustration
--- # La rotation ## Le problème On tourne en rond
## La solution La double rotation --- # La rotation ## Double
--- # La rotation ## Double Droite
--- # La rotation ## Double Gauche
--- # La rotation ## Avec l'exemple Double rotation Gauche ## Illustration
--- # La rotation ## DOUBLE
--- # La rotation ## DOUBLE
--- # Exemple ## Vidéo
--- # Arbre AVL ## Concrétement en C ```c typedef struct noeud { int val; noeud* filsG; int hauteur; noeud* filsD; }noeud; typedef noeud* arbre AVL; ``` --- # Rééquilibrage ## Algorithme #### Equilibrage ```c FONCTION equilibrage(a : AVL) : AVL VARIABLES e:entier DEBUT e <- ecart(a) SI (e=2) ALORS SI (ecart(a.filsG)=1) ALORS a <- rotationDroite(a) SINON a <- rotationGaucheDroite(a) FIN SI SINON SI (e=-2) ALORS SI (ecart(a.filsD)=-1) ALORS a <- rotationGauche(a) SINON a <- rotationDroiteGauche(a) FINSI SINON a.hauteur=1+ max (a.filsG.hauteur, a.filsD.hauteur) FIN SI RETOURNER a FIN ``` --- # Rééquilibrage ## Algorithme #### ECART ```c FONCTION ecart(a : AVL) : entier VARIABLES : res : entier DEBUT SI (a=NULL) ALORS res <-0 SINON res <- (a.filsG.hauteur) - (a.filsD.hauteur) FIN SI RETOURNER res FIN ``` --- # sitographie ## Des Liens
Henri-Garreta
etsmtl
Labri - Bordeaux
LRI