L'arbre binaire de recherche
La propriété d'ordre, la recherche, l'insertion, la suppression dans ses trois cas (feuille, un fils, deux fils), le parcours infixe qui rend les clés triées, la hauteur et la dégénérescence en liste.
- 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
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
Arbre binaire : de quoi s'agit-il ?
Voir la réponse
Structure de nœuds où chacun a au plus deux fils, distingués comme gauche et droit, et où un seul nœud, la racine, n'a pas de père.
Sa hauteur, comptée ici en nœuds sur le plus long chemin de la racine à une feuille, borne le coût de toute descente. Certains cours la comptent en arêtes, soit un de moins.
On insère 50, 30, 70, 20, 40, 60 puis 35 dans un arbre binaire de recherche vide. Où se pose 35 ?
- Fils gauche de 40
- Fils droit de 30
- Fils gauche de 20
- Fils droit de 40
Voir la réponse
Fils gauche de 40
35 < 50 : à gauche. 35 > 30 : à droite, vers 40. 35 < 40 : à gauche, emplacement vide. Le fils droit de 30 est déjà 40.
Dans un arbre binaire de recherche, on descend à … si la clé cherchée est plus petite que celle du nœud, à … si elle est plus grande.
Voir la réponse
Dans un arbre binaire de recherche, on descend à gauche si la clé cherchée est plus petite que celle du nœud, à droite si elle est plus grande.
Chaque comparaison écarte un sous-arbre complet. Une clé égale à celle du nœud signifie que la recherche a réussi.
Arbre binaire de recherche : de quoi s'agit-il ?
Voir la réponse
Arbre binaire où chaque clé est plus grande que toutes celles de son sous-arbre gauche et plus petite que toutes celles de son sous-arbre droit.
À chaque nœud, une comparaison élimine un sous-arbre entier : la recherche coûte la hauteur de l'arbre. La règle vaut pour tout le sous-arbre, pas seulement pour les fils directs.
Un index construit avec un arbre binaire de recherche ordinaire est rempli à partir d'un fichier déjà trié par numéro. Les recherches deviennent aussi lentes qu'un parcours de liste. Quelle est la réparation ?
- Insérer les clés de la plus grande à la plus petite
- Utiliser un arbre équilibré, qui se rééquilibre à chaque insertion
- Remplacer les comparaisons par un parcours infixe à chaque recherche
- Supprimer régulièrement la racine pour raccourcir l'arbre
Voir la réponse
Utiliser un arbre équilibré, qui se rééquilibre à chaque insertion
Des clés triées dégénèrent l'arbre en chaîne : hauteur n. Les insérer à l'envers donne une chaîne penchée de l'autre côté. Un arbre équilibré (AVL, rouge-noir) garde une hauteur de l'ordre de log n quel que soit l'ordre d'arrivée.