Embed Size (px)
Citation preview
INF1101
Cours 8 Cours 8 Arbres équilibrésArbres équilibrés
INF1101 – Algorithmes et structures de INF1101 – Algorithmes et structures de donnéesdonnées
INF1101
Cours 7 – Arbres équilibrés
• Analyse des arbres binaires de recherche
• Arbres AVL
• Arbres rouge-noir
• Arbres AA
INF1101
Arbres binaires - analyse• Le prix d’une opération (recherche, insertion, retrait) est
proportionnel au nombre de noeuds visités• Donc, coût proportionnel à 1+profondeur• Meilleur cas: arbre équilibré (les feuilles à peu près toutes
à la même profondeur)– insertion et retrait aléatoire tendent à créer un arbre équilibré– profondeur = lg n
• Pire cas: liste chaînée– par exemple lors de l’insertion d’éléments ordonnés– profondeur = n
• Donc, le coût est O(lg n) dans le meilleur cas et O(n) dans le pire cas
INF1101
Arbres équilibrés – concepts de base• Situation idéale visée: s’assurer que le sous-
arbre de gauche et le sous-arbre de droite sont de même hauteur
• Ce principe s’appliquerait à tous les noeuds de manière récursive
• Si on appliquait ceci à chaque insertion ou retrait, ce serait très coûteux
• Il faut donc établir des conditions plus faibles, mais qui nous assurent des gains en performance
INF1101
Arbres AVL• Définition: arbre de recherche binaire tel que
pour chaque noeud, les hauteurs des ses sous-arbres gauche et droite sont différentes d’au plus 1 (on attribue la valeur -1 pour un sous-arbre vide)
• Avec cette condition, on est assuré de toujours avoir un arbre dont la profondeur est proportionnelle à lg N
INF1101
Arbres AVL - exemple
12
8
4 10
16
2
14
6
Cet arbre est un arbre AVL
INF1101
Arbres AVL – exemple
12
8
4 10
16
2
14
6
Après l’ajout de 1 ce n’est plus un arbre AVL
1
Ces noeuds violentla condition
INF1101
Arbres AVL - exemple
12
8
4 10
16
2
14
6 13
Après l’ajout de 13 ce n’est plus un arbre AVL
INF1101
Arbres AVL• Il faut, après chaque insertion ou retrait, rétablir
l’équilibre s’il a été rompu par l’opération• Observation importante: après une insertion,
seuls les noeuds qui sont sur le chemin du point d’insertion à la racine sont susceptibles d’être déséquilibrés
• Deux cas:– insertion dans le sous-arbre de gauche du fils gauche
ou dans le sous-arbre de droite du fils droit: Simple rotation
– insertion dans le sous-arbre de droite du fils gauche ou dans le sous-arbre de gauche du fils droit: Double rotation
INF1101
AVL – exemle de simple rotation
12
8
4 10
16
2
14
6
1
Hauteur = 2
Hauteur = 0
INF1101
AVL – exemple de simple rotation
12
8 16
144
2 6
1
10
INF1101
AVL – exemple de simple rotation
12
8
16
14
4
2
61
10
INF1101
AVL – exemple de simple rotation
12
8
16
14
4
2
61
10
INF1101
Arbres AVL – simple rotation (fils gauche)
template <class T>void BST<T>::rotateWithLeftChild(Node * & k2) const{
Node *k1 = k2->left;k2->left = k1->right;k1->right = k2;k2 = k1;
}
INF1101
AVL – exemple de double rotation
12
4
16
2
14
6
8
10
7
Noeud inséré
INF1101
AVL – exemple de double rotation
12
4
16
2
14
6
8
10
7
INF1101
AVL – exemple de double rotation
12
4
16
2
146
8
10
7
INF1101
AVL – exemple de double rotation
12
4
16
2
146
8
10
7
INF1101
AVL – exemple de double rotation
12
4
16
2
14
6
8
107
INF1101
AVL – implémentation• Algorithme récursif• Une fois le noeud inséré, en revenant sur notre
chemin, il faut vérifier, pour chaque noeud parcouru, les différences de profondeur des sous-arbres gauche et droite
• La rotation peut être requise à n’importe quel noeud qui se trouve dans le chemin de la racine au point d’insertion
• Le retrait est passablement plus compliqué que l’insertion (mais demeure O(lg N))
• Il y a d’autres types d’arbres équilibrés plus facile à implémenter et plus efficaces
INF1101
AVL – exemple détaillé
Pour chaque noeud on mettra
0 si ses deux sous-arbres ont la même profondeur +n si le sous-arbre gauche est plus profond avec une différence = n
-n si le sous-arbre droit est plus profond avec une différence = n
Séquence d’insertion:
2 10 12 4 16 8 6 14
INF1101
AVL – exemple détaillé2 10 12 4 16 8 6 14
2 0
INF1101
AVL – exemple détaillé2 10 12 4 16 8 6 14
2
10 0
-1
INF1101
AVL – exemple détaillé2 10 12 4 16 8 6 14
2
10
12 0
-1
-2
INF1101
AVL – exemple détaillé2 10 12 4 16 8 6 14
10
122
Rotation simple
00
0
INF1101
AVL – exemple détaillé2 10 12 4 16 8 6 14
10
122
4 0
-1 0
1
INF1101
AVL – exemple détaillé2 10 12 4 16 8 6 14
10
122
4 16 00
-1-1
0
INF1101
AVL – exemple détaillé2 10 12 4 16 8 6 14
10
122
4 16
8 0
-1
-2
0
-1
1
INF1101
AVL – exemple détaillé2 10 12 4 16 8 6 14
10
124
8 162
Rotation simple
0 0 0
-10
0
INF1101
AVL – exemple détaillé2 10 12 4 16 8 6 14
10
124
8 162
6 0
10
-1
0
-1
1
INF1101
AVL – exemple détaillé2 10 12 4 16 8 6 14
10
124
8 162
6 140 0
1
-2
10
-1
0
INF1101
AVL – exemple détaillé2 10 12 4 16 8 6 14
10
144
8 162
6
12
Rotation double
0
1
00
0
0
-1
1
INF1101
AVL – autre exempleVoici un exemple où la rotation se fait loin du point d’insertion
10
144
8 162
6
12
-1
1
0 0
0
1
-1
2
10 9 0
70
Noeud inséré
INF1101
AVL – autre exemple
10
14
4
8
16
2 6
12
-1
0
01
-1
10
9
070
Après rotation double
0
0
0
Voici un exemple où la rotation se fait loin du point d’insertion
INF1101
Arbres Rouge-Noir• L’arbre a les propriétés suivantes:
1. Chaque noeud est soit rouge soit noir2. La racine est noire3. Si un noeud est rouge, tous ses enfants doivent être
noirs4. À partir de n’importe quel noeud, tous les chemins de
la racine jusqu’à un pointeur NULL doivent avoir le même nombre de noeuds noirs
• Comme la racine est noire et il ne peut y avoir plus de deux noeuds rouges consécutifs, la longueur de tout chemin de la racine à une feuille ne peut être supérieure à 2 fois le nombre de noeuds noirs dans ce chemin
INF1101
Arbres Rouge-Noir - Exemple
30
85
80 90
60
5540
50 65
15
20
5
10
70
INF1101
Arbres Rouge-Noir - Exemple
30
85
80 90
60
5540
50 65
15
20
5
10
70
INF1101
Arbres Rouge-Noir – Contre-exemple
30
85
80 90
60
5540
50 65
15
5
10
70
83 95
2 noeuds noirs
4 noeuds noirs
INF1101
Arbres Rouge-Noir - insertion• Un noeud inséré est toujours une feuille• On peut pas le colorier en noir, puisque cela
violerait la condition 4• On colore le noeud en rouge• Si le père est noir, pas de problème• Si le père est rouge, on viole la condition 3. Dans
ce cas, on ajuste l’arbre, par le biais de changements de couleurs et de rotations
INF1101
Premier cas: le frère du noeud parent est noir (on utilise la convention qu’un noeud NULL est noir)
P
X
G
C
Noeud inséré
A B
S
D E
P
X G
CA B S
D E
Rotation simple
INF1101
Premier cas: le frère du noeud parent est noir (on utilise la convention qu’un noeud NULL est noir)
P
X
G
C
Noeud inséré
A
B
S
D E
X
P G
CA B S
D E
Rotation double
INF1101
30
85
80 90
60
5540
50 65
15
20
70
5
3
Noeud inséré
10
(NOIR)
(NOIR)
Rotation simple
Exemple
INF1101
30
85
80 90
60
5540
50 65
15
20
70
5
3
10
(NOIR)(NOIR)
Rotation simple
INF1101
30
85
80 90
60
5540
50 65
15
20
70
5
3
10
(NOIR)(NOIR)
Rotation simple
INF1101
30
85
80 90
60
5540
50 65
15
20
70
5
3 10
(NOIR)(NOIR)
Rotation simple
INF1101
30
85
80 90
60
5540
50 65
15
20
70
5
3 10
(NOIR)(NOIR)
Rotation simple
INF1101
30
85
80 90
60
5540
50 65
15
20
70
5
8
Noeud inséré
10
(NOIR)
(NOIR)
Rotation double
INF1101
30
85
80 90
60
5540
50 65
15
20
70
5
8
10
(NOIR)(NOIR)
Rotation double
INF1101
30
85
80 90
60
5540
50 65
15
20
70
5
8
10
(NOIR)(NOIR)
INF1101
30
85
80 90
60
5540
50 65
15
20
70
5
8
10
(NOIR)(NOIR)
INF1101
Si le frère du parent est rouge
P
X
G
C
Noeud inséré
A B
S
D E
P
X G
CA B S
D E
Ceci cause un problème. Lequel?
INF1101
Si le frère du parent est rouge
P
X
G
C
Noeud inséré
A B
S
D E
P
X G
CA B S
D E
Ceci cause un problème. Lequel?Si le parent de P est rouge, il faudra propager vers le haut les ajustements, ce qui nous fait perdre l’avantagesur AVL
INF1101
Arbres Rouge-Noir – top-down• Pour éviter de devoir propager vers le haut
l’algorithme de rotation, on peut utiliser une approche top-down
• Idée: garantir que, lorsqu’on arrive au point d’insertion, qu’il ne s’agisse pas d’un noeud rouge
• On pourra donc ajouter tout simplement un noeud rouge, sans risque de violer la propriété 3
INF1101
Arbres Rouge-Noir – top-down (suite)• En descendant dans l’arbre, lorsqu’on rencontre un noeud qui a deux
fils rouges, on colore ce noeud rouge et noir ses deux fils:
• Ainsi, le nombre de noeuds noirs dans un chemin demeure inchangé• Par contre, on peut se retrouver avec deux noeuds rouges
consécutifs, si le parent de X est rouge. Dans ce cas, il faudra appliquer une rotation
• Ceci fonctionnera parce qu’on est sur que le noeud frère du parent de X ne peut être que noir.
• Attention: la racine doit toujours demeurer noire
FDFG
X
FDFG
X
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
10
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
10
85
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
10
85
15
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
15
8510
Rotation double
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
15
8510
Ajustement durant le parcours
Attention: la racine ne changepas de couleur
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
15
8510
70
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
15
8510
70
20
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
15
7010
20 85
Rotation simple
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
15
7010
20 85
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
15
7010
20 85
Ajustement durant le parcours
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
15
7010
20 85
60
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
15
7010
20 85
60
30
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
15
7010
30 85
6020
Rotation double
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
15
7010
30 85
6020
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
15
7010
30 85
6020
Ajustement durant le parcours
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
15
7010
30 85
6020
50
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
1570
10
30
856020
50
Rotation double
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
1570
10
30
856020
50
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
1570
10
30
856020
50
Ajustement durant le parcours
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
1570
10
30
856020
50 65
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
15 70
10
30
856020
50 65 80
Remarque: ces noeuds n’ont pas étémodifiés parce qu’il ne sont pas dans lechemin parcouru
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
15 70
10
30
856020
50 65 80 90
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
15 70
10
30
856020
50 65 80 90
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
15 70
10
30
856020
50 65 80 90
Ajustement durant le parcours
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
15 70
10
30
856020
50 65 80 90
40
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
15 70
10
30
856020
50 65 80 90
40
5
INF1101
Arbres Rouge-Noir – Exemple détaillé10 85 15 70 20 60 30 50 65 80 90 40 5 55
15 70
10
30
856020
50 65 80 90
40
5
55
INF1101
Arbres AA• Implémentation plus simple que les autres• Une condition supplémentaire: le fils de gauche
ne peut pas être rouge• Soit le niveau d’un noeud défini ainsi:
– 1 si c’est une feuille– niveau du parent si le noeud est rouge– (1 – niveau du parent) si le noeud est noir
• On construit un arbre équivalent avec cette définition de niveau et on obtient un algorithme plus simple à implémenter (voir livre)
INF1101
Question• Pourquoi les arbres de recherche binaire sont-ils
en général plus efficace qu’une recherche dichotomique dans un tableau trié?
• Peut-on imaginer des situations où il serait préférable d’utiliser une recherche binaire dans un tableau ordonné?
