Structures de données Arbres AVL et SPLAY Flashcards
de quoi dépend la suppression d’un noeud pour un arbre rouge/noir, décrire
sa couleur
Rouge:
– Le nombre de nœuds noirs dans la branche ne change
pas.
– Il n’y aura pas deux rouges consécutifs
– Ça ne peut pas être la racine
Noir:
– Peut briser n’importe laquelle des règles d’un arbre
rouge-noir
lister et décrire les règles de suppression pour un arbre rouge/noir
Règle #1: Nœud est une feuille rouge
Le nœud est simplement enlevé
Règle #2: Le nœud à un seul enfant
– Le nœud est forcément noir
– L’enfant est forcément rouge
– Le nœud est remplacé par son enfant et il devient noir.
Règle #3: Le nœud à deux enfants
– Le nœud est remplacé par son prédécesseur
• Si le prédécesseur est rouge, celui-ci est simplement éliminé
• Si le prédécesseur à un seul enfant, la règle #2 est appliquée
• Sinon, appliquer règle 4 pour éliminer le prédécesseur
Règle #4: Le nœud est une feuille noir ou le prédécesseur est une feuille noir
– Ça se complique…
– Il y a 4 cas possibles (plus les versions symétriques)
liste les possibilité de la règle 4
Suppression d’une feuille noir – Il faut remplacer la feuille par un pointeur NULL qui devient un double noir
Il faut ensuite éliminer les nœuds double noir. Le principe est de: – Trouver une paire (rouge, double noir) et la transformer en (noir,noir)
– Comme pour l’insertion, il faut effectuer des changements de couleurs et/ou des rotations
– Une rotation résout un problème local, le changement de couleur se propage
jusqu’à deux niveaux plus haut
– Un peu plus complexe que l’insertio
Règle 4, cas #1: Frère rouge
Changement de couleur:
• Parent devient rouge
• Frère devient noir
• Appliquer une rotation sur le parent afin qu’il vienne prendre la
place du double-noir.
• Appliquer la bonne règle pour un frère noir
Règle 4, cas #2: Frère et enfants du frère noir
Changement de couleur: • frère devient rouge • parent devient noir ou double noir • Le double noir devient simple noir • Si le parent devient un double noir, poursuivre le processus à du partir du parent
Règle 4, cas #3: Frère noir mais
enfant gauche du frère est rouge et
enfant droit noir
•Frère devient rouge, enfant gauche devient noir •Appliquer une rotation droite sur le nœud frère •Devient le cas #4
Règle 4, cas #3:Symétrie: Frère noir mais enfant
droit du frère est rouge et enfant
gauche noir
•Frère devient rouge, enfant droit devient noir •Appliquer une rotation gauche sur le nœud frère •Devient le cas #4
Règle 4, cas #4: Frère noir mais
enfant droit du frère est rouge
• Changements de couleur • Enfant droit du frère devient noir • Frère devient la couleur du parent • Parent devient noir • Appliquer une rotation gauche sur le parent du nœud double noir
Règle 4, cas #4 Cas symétrique : Frère noir mais
enfant gauche du frère est rouge
• Changements de couleur • Enfant gauche du frère devient noir • Frère devient la couleur du parent • Parent devient noir • Appliquer une rotation droite sur le parent du nœud double noir
voir exemple dia 14 a 17
et fait les avec les règles
Caractéristiques et conséquence des arbres AVL
– Arbres de recherche binaires balancés.
– Fonctions spéciales d’insertion et de suppression de nœuds.
– Garantissent que les sous arbres de gauche et de droite de tout nœud
ont la même hauteur à 1 niveau près.
Conséquences:
–Hauteur d’un arbre de N noeuds <= 1.44 log(N)
–Temps de recherche en O ( log(N) )
Arbre AVL =
= arbre balancé:
Différence de hauteur des sous arbres d’un nœud <= 1.
Pour un arbre AVL, A chaque nœud, on associe un facteur d’équilibre BF:
– « / » si sous arbre de gauche + haut que sous arbre de
droite
– « = » si sous arbres sont de même hauteur;
– « \ » si sous arbre de droite + haut que celui de gauche;
Principe générale de l’insertion dans l’arbre AVL
– Effectuer une recherche pour trouver l’emplacement du nouveau nœud. – Insérer le nœud dans l’arbre. – Modifier la structure de l’arbre pour maintenir ses propriétés
différents cas a lire sont dans cheatsheat
Cas #1 : Le nouveau nœud ne brise pas les
propriétés AVL de l’arbre.
Cas #2: On note a le premier nœud de l’arbre qui
brise les propriétés AVL: – Nœud inséré à gauche du sous arbre gauche de a
– Nœud inséré à droite du sous arbre droit de a
Solution: Rotation simple
Cas #3: On note a le premier nœud de l’arbre qui
brise les propriétés AVL: – Nœud inséré à droite du sous arbre gauche de a
– Nœud inséré à gauche du sous arbre droit de a
Solution: Rotation double
