Les arbres équilibrés
Trois arbres qui gardent une hauteur logarithmique : l'AVL (facteur d'équilibre, rotations simples et doubles), le rouge-noir (ses propriétés) et le B-arbre (ordre, nœud plein, éclatement).
- 24 cartes
- 5 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Mises en situation
- Comprendre
Quelques cartes du deck
Arbre auto-équilibré : de quoi s'agit-il ?
Voir la réponse
Arbre de recherche qui se réorganise à chaque insertion ou suppression pour que sa hauteur reste de l'ordre de log n.
Il garantit un coût en O(log n) pour la recherche, l'insertion et la suppression, quel que soit l'ordre d'arrivée des clés.
On insère 40, 20, 60, 10, 30 puis 5 dans un AVL vide. Après le rééquilibrage, quelle est la racine et où se trouve 30 ?
- Racine 20 ; 30 est le fils gauche de 40
- Racine 20 ; 30 reste le fils droit de 20
- Racine 10 ; 30 est le fils droit de 20
- Racine 40 ; 30 reste le fils droit de 20
Voir la réponse
Racine 20 ; 30 est le fils gauche de 40
Après 5, le nœud 40 a un facteur de +2 et 5 est descendu à gauche de son fils gauche 20 : cas gauche-gauche, rotation droite sur 40. 20 monte à la racine et 40 devient son fils droit ; le sous-arbre droit de 20, c'est-à-dire 30, passe en fils gauche de 40, ce qui garde l'ordre 20 < 30 < 40.
Dans un AVL, un déséquilibre « gauche-gauche » se corrige par une rotation …, un déséquilibre « droite-droite » par une rotation ….
Voir la réponse
Dans un AVL, un déséquilibre « gauche-gauche » se corrige par une rotation droite, un déséquilibre « droite-droite » par une rotation gauche.
On fait pivoter le nœud déséquilibré du côté opposé à la branche trop lourde. Les cas « gauche-droite » et « droite-gauche » demandent deux rotations.
Facteur d'équilibre : de quoi s'agit-il ?
Voir la réponse
Différence entre la hauteur du sous-arbre gauche et celle du sous-arbre droit d'un nœud.
Dans un AVL, il vaut −1, 0 ou +1 à chaque nœud. Une valeur de ±2 après une insertion signale un nœud déséquilibré à réparer.
Un index de base de données sur disque doit retrouver une ligne parmi des dizaines de millions en lisant le moins de blocs possible. Quelle structure convient le mieux ?
- Un B-arbre, aux nœuds larges et à la hauteur très faible
- Un AVL, dont chaque nœud porte une seule clé
- Un arbre binaire de recherche ordinaire, plus simple à écrire
- Une liste chaînée triée, pour un parcours séquentiel
Voir la réponse
Un B-arbre, aux nœuds larges et à la hauteur très faible
Sur disque, ce qui coûte, c'est le nombre de blocs lus. Un nœud de B-arbre remplit un bloc de plusieurs centaines de clés : la hauteur tient en trois ou quatre niveaux. Un AVL, binaire, en demanderait des dizaines.