Aller au contenu

2021, Centres étrangers, sujet 1, exercice 3⚓︎

Thème : Arbres binaires de recherche

Squelette d'un ABR

squelette ABR

Un arbre binaire est soit vide, soit un nœud qui a une valeur et au plus deux fils (le sous-arbre gauche et le sous-arbre droit).

  • X est un nœud, sa valeur est X.valeur
  • G1 est le fils gauche de X, noté X.fils_gauche
  • D1 est le fils droit de X, noté X.fils_droit

Un arbre binaire de recherche est ordonné de la manière suivante :


Pour chaque nœud X,

  • les valeurs de tous les nœuds du sous-arbre gauche sont strictement inférieures à la valeur du nœud X
  • les valeurs de tous les nœuds du sous-arbre droit sont supérieures ou égales à la valeur du nœud X

Ainsi, par exemple, toutes les valeurs des nœuds G1, G2 et G3 sont strictement inférieures à la valeur du nœud X et toutes les valeurs des nœuds D1, D2 et D3 sont supérieures ou égales à la valeur du nœud X.

Voici un exemple d'arbre binaire de recherche dans lequel on a stocké dans cet ordre les valeurs :

[26, 3, 42, 15, 29, 19, 13, 1, 32, 37, 30]

L'étiquette d'un nœud indique la valeur du nœud suivie du nom du nœud. Les nœuds ont été nommés dans l'ordre de leur insertion dans l'arbre ci-dessous. '29, noeud04' signifie que le nœud nommé noeud04 possède la valeur 29.

ABR

un ABR

Question 1

On insère la valeur \(25\) dans l'arbre, dans un nouveau nœud nommé noeud11. Recopier l'arbre binaire de recherche étudié et placer la valeur \(25\) sur cet arbre en coloriant en rouge le chemin parcouru.

Préciser sous quel nœud la valeur \(25\) sera insérée et si elle est insérée en fils gauche ou en fils droit, et expliquer toutes les étapes de la décision.

Réponse

insert25

On compare \(25\) et la valeur de la racine \(26\) ; comme \(25\) est inférieure, on va chercher à insérer dans le fils gauche. La valeur de la racine du sous-arbre gauche est \(3\), valeur inférieure à \(25\), on va donc cette fois descendre dans le sous-arbre droit (vers le noeud03), \(15\) étant toujours inférieur à \(25\) on descend encore à droite. Le noeud05 est une feuille, on va insérer sous ce nœud, à droite.

Question 2

Préciser toutes les valeurs entières que l'on peut stocker dans le nœud fils gauche du noeud04 (vide pour l'instant), en respectant les règles sur les arbres binaires de recherche ?

Réponse

Les valeurs sont à gauche d'une racine qui porte la valeur \(29\) les valeurs \(x\) doivent donc vérifier \(x \lt 29\). En même temps, nous sommes dans le sous-arbre droit de l'arbre dont la racine porte la valeur \(26\), donc \(x\) doit vérifier \(26 \geq x\). Le noeud02 n'apporte pas plus d'information : \(x \lt 42\). Ainsi donc les valeurs possibles sont : \(26, 27, 28\).

Voici un algorithme récursif permettant de parcourir et d'afficher les valeurs de l'arbre :

Parcours(A)            # A est un arbre binaire de recherche
    Afficher(A.valeur)
    Parcours(A.fils_gauche)
    Parcours(A.fils_droit)
Question 3a

Écrire la liste de toutes les valeurs dans l'ordre où elles seront affichées.

Réponse

On suppose que la question intègre le fait qu'on a ajouté la valeur 25 ; les valeurs sont alors affichées dans cet ordre :

\[26, 3, 1, 15, 13, 19, 25, 42, 29, 32, 30, 37\]
Question 3b

Choisir le type de parcours d'arbres binaires de recherche réalisé parmi les propositions suivantes : Préfixe, Suffixe, Infixe

Réponse

On traite la racine avant les fils : il s'agit d'un parcours Préfixe.

Question 4

En vous inspirant de l'algorithme précédent, écrire un algorithme Parcours2 permettant de parcourir et d'afficher les valeurs de \(A\) dans l'ordre croissant.

Réponse

Pour obtenir un affichage dans l'ordre croissant, on s'appuie sur la propriété des ABR et on effectue un parcours Infixe :

Parcours2(A)
    Parcours2(A.fils_gauche)
    Afficher(A.valeur)
    Parcours2(A.fils_droit)

Conclusion⚓︎

Sujet assez classique, pas difficile, pas long et sans grosse erreur.