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
extension d'une structure problématique! Déterminer le kième plus petit élément dans un arbre rouge-noir. Exemple: - Trouver la médiane (k = N/2) - Trouver le max (k=N)
Il faut ajouter des informations supplémentaires
dans l’arbre
voir algorithme de selection dia 29!
IMP!!
ex dia 28 a 31
Deux étapes d’insertion d’un nouveau nœud pour la sélection dans l’extension d’une structure
• Chercher la feuille où le nouveau nœud sera inséré
• Les statistiques sont maintenues en ajoutant 1 à la taille de tout les
nœuds traverser
• L’opération est donc en O(log N)
• Ajuster l’arbre : les changements structurels sont causés
par les rotations.
• La rotation est une opération locale
• La taille des deux noeuds impliqués
sera modifié (rotation droite)
Désavantage des arbres de recherche?
Ne tiennent pas compte de la fréquence d’utilisation des informations contenues dans l’arbre.
Caractéristiques des splay trees
– Partage les mêmes caractéristiques que les arbres binaires
de recherche.
– Les opérations d’insertion, de suppression et de recherche
sont implémentés de façon à garder les éléments
fréquemment accédés près de la racine.
– Ce n’est pas un arbre balancé (comme le AVL ou le
rouge-noir) mais les opérations tendent à maintenir un
certain balancement.
opération de base des splay trees
Rotation zig (zag)
Caractéristiques des Rotation zig (zag)
Se produit lorsque le parent du nœud à promouvoir est la racine de l’arbre.
Consiste en une rotation vers la droite (zig) ou vers la gauche (zag).
Caractéristiques des Rotation zig-zig
– Se produit lorsque le nœud à promouvoir est à gauche de son parent et à gauche de
son grand-parent.
– Consiste en deux rotations vers la droite (ou deux rotations vers la gauche pour
zag-zag).
caractéristiques des Rotation zag-zig
– Se produit lorsque le nœud à promouvoir est à droite de son parent et à gauche de
son grand-parent.
– Consiste en une rotation vers la gauche et une rotation vers la droite (et vice-versa
pour un zig-zag).
décrit les opérations de recherche et d’insertion des splay trees
Recherche
– Applique la recherche standard des arbres binaires.
– Applique les rotations nécessaires afin que le nœud
devienne la racine de l’arbre.
– Retourne la racine.
Insertion
– Insère le nœud selon la méthode habituelle.
– Applique les rotations nécessaires afin que le nouveau
nœud devienne la racine de l’arbre.
ex dia 41 a 43
analyse en trois point les splay trees
Arbre non balancé:
→ Insertion et recherche : O(n)
Une analyse sur une séquence d’opérations
démontre que l’arbre à tendance à devenir
balancé
→ Insertion et recherche : O(lg n)
Mais beaucoup plus rapide sur les éléments qui
sont fréquemment accédés!
résume Arbres binaires de recherche
– Arbres balancés donc les opérations s’effectuent en O(lg n)
– Insertion aléatoire mène à une hauteur moyenne de 6.22 lg n – Il y a toujours une possibilité que l’arbre soit complètement débalancé
– Le fait de retirer des nœuds peut mener à un débalancement de l’arbre
résume Arbres rouge-noir et AVL
– Arbres balancés donc les opérations s’effectuent en O(lg n)
– Les arbres AVL ont une structure plus rigide – Insertion et suppression plus lente
– Recherche plus rapide
résume Splay trees
– Aucun algorithme de balancement mais une analyse sur une longue
séquence d’opérations démontre que les rotations ont tendance à
balancer l’arbre automatiquement.
– Particulièrement efficace pour accéder aux éléments fréquemment
utilisés.
