Arbres binaires de recherche : exercices corrigés de Terminale NSI

8 est la racine, car l'arbre est vide.

3 < 8 : 3 devient fils gauche de 8. 10 > 8 : 10 devient fils droit de 8.

1 < 8 puis 1 < 3 : 1 devient fils gauche de 3. 6 < 8 puis 6 > 3 : 6 devient fils droit de 3.

14 > 8 puis 14 > 10 : 14 devient fils droit de 10.

4 < 8, 4 > 3, 4 < 6 : 4 devient fils gauche de 6. 7 < 8, 7 > 3, 7 > 6 : 7 devient fils droit de 6.

13 > 8, 13 > 10, 13 < 14 : 13 devient fils gauche de 14.

Taille : on compte les nœuds, il y en a 9 (autant que de clés insérées).

Hauteur : le chemin 8, 3, 6, 4 compte 4 nœuds ; le chemin 8, 10, 14, 13 aussi. Aucun chemin n'est plus long : la hauteur est 4.

Clé 7 : on compare à 8, 7 < 8, on va à gauche.

On compare à 3, 7 > 3, on va à droite.

On compare à 6, 7 > 6, on va à droite.

On compare à 7 : égal, la clé est présente. Nœuds examinés : 8, 3, 6, 7, soit 4.

Clé 5 : 8 (gauche), 3 (droite), 6 (gauche), 4 (droite). Le fils droit de 4 est vide : 5 est absente.

Clé 12 : 8 (droite), 10 (droite), 14 (gauche), 13 (gauche). Le fils gauche de 13 est vide : 12 est absente.

Insertion de 5 : le chemin est 8 (gauche), 3 (droite), 6 (gauche), 4 (droite). Le fils droit de 4 est vide : 5 devient fils droit de 4.

Insertion de 2 : 8 (gauche), 3 (gauche), 1 (droite). Le fils droit de 1 est vide : 2 devient fils droit de 1.

Hauteur : le chemin 8, 3, 6, 4, 5 contient 5 nœuds.

Le chemin 8, 3, 1, 2 n'en contient que 4. Le plus long est donc celui qui mène à 5 : hauteur 5.

Préfixe : on écrit 8, puis on parcourt le sous-arbre de racine 3 (3, 1, puis le sous-arbre de 6 : 6, 4, 7), puis celui de 10 (10, puis 14, puis 13).

Résultat préfixe : 8, 3, 1, 6, 4, 7, 10, 14, 13.

Infixe : on descend à gauche jusqu'à 1. Le sous-arbre de 3 donne 1, 3, puis le sous-arbre de 6 donne 4, 6, 7. On écrit alors 8, puis le sous-arbre de 10 : 10, puis celui de 14 qui donne 13, 14.

Résultat infixe : 1, 3, 4, 6, 7, 8, 10, 13, 14.

Postfixe : le sous-arbre de 3 donne 1, 4, 7, 6, 3 (la racine 3 en dernier) ; celui de 10 donne 13, 14, 10 ; la racine 8 vient en dernier.

Résultat postfixe : 1, 4, 7, 6, 3, 13, 14, 10, 8.

Observation : la liste infixe est rangée dans l'ordre croissant.

Le sous-arbre droit de 3 a pour racine 6, qui a un fils gauche, 4.

Le nœud 4 n'a pas de fils gauche : c'est le nœud le plus à gauche du sous-arbre droit, donc le successeur. Sa clé est 4.

Le sous-arbre gauche de 3 est réduit à 1 : le prédécesseur est 1.

On échange 3 et 4. Le nœud portant maintenant la clé 3 est une feuille : on le supprime.

Arbre obtenu : racine 8 ; à gauche 4, qui a 1 à gauche et 6 à droite ; 6 n'a plus que 7 à droite ; à droite de 8, la branche 10, 14, 13 est inchangée.

Vérification : 1 < 4 < 6 < 7 < 8 et la branche de droite n'a pas bougé, donc l'ordre est conservé.

Cas de base de recherche : si arbre is None, la clé est absente, on renvoie False.

Si cle == arbre.cle, on renvoie True.

Si cle < arbre.cle, on rappelle la fonction sur arbre.gauche ; sinon sur arbre.droit.

Code complet :

def recherche(arbre, cle):
    if arbre is None:
        return False
    if cle == arbre.cle:
        return True
    if cle < arbre.cle:
        return recherche(arbre.gauche, cle)
    return recherche(arbre.droit, cle)

Cas de base de hauteur : l'arbre vide vaut 0.

Cas général : on compte la racine (1) et on ajoute la plus grande hauteur des deux sous-arbres.

Code complet :

def hauteur(arbre):
    if arbre is None:
        return 0
    return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droit))

Sur l'arbre de l'exercice 1, la branche gauche donne 3 et la branche droite 3, donc la hauteur de la racine vaut 1 + 3 = 4.

Premier ordre : 4 est la racine ; 2 à gauche, 6 à droite ; 1 et 3 sous 2 ; 5 et 7 sous 6. Tous les niveaux sont remplis : hauteur 3.

Deuxième ordre : 1 est la racine. 2 > 1 va à droite de 1, 3 va à droite de 2, et ainsi de suite.

On obtient une seule branche vers la droite : 1, 2, 3, 4, 5, 6, 7. Hauteur 7.

Recherche de 7 dans le premier arbre : 4, puis 6, puis 7 : 3 nœuds.

Recherche de 7 dans le second arbre : on traverse 1, 2, 3, 4, 5, 6, 7 : 7 nœuds.

Nœud 10 avec ses fils : 5 < 10 et 15 > 10, la relation locale est correcte.

Nœud 5 avec ses fils : 3 < 5 et 12 > 5, la relation locale est aussi correcte.

Mais 12 appartient au sous-arbre gauche de la racine 10, et 12 > 10. Une clé du sous-arbre gauche doit être inférieure à celle de la racine ⁶. La propriété est violée.

L'arbre n'est donc pas un ABR, bien que chaque relation père-fils soit respectée.

Correction : on déplace 12 pour le mettre comme fils gauche de 15, puisque 10 < 12 < 15. Le nœud 5 n'a plus que 3 à gauche, et l'arbre respecte la propriété.

Un niveau $k$ rempli contient $2^{k-1}$ nœuds : 1, 2, 4, 8, ...

Pour $h = 1$ : 1 nœud, soit $2^1 - 1$. Pour $h = 2$ : $1 + 2 = 3 = 2^2 - 1$. Pour $h = 3$ : $1 + 2 + 4 = 7 = 2^3 - 1$.

Il faut $2^h - 1 \geq 1000$, c'est-à-dire $2^h \geq 1001$.

Avec $h = 9$ : $2^9 = 512$, c'est trop petit. Avec $h = 10$ : $2^{10} = 1024 \geq 1001$, cela convient.

La plus petite hauteur possible est donc 10 : une recherche examine au plus 10 nœuds au lieu de 1000.

Dans les deux méthodes, chaque comparaison écarte environ la moitié des valeurs restantes ; la différence est que l'ABR suit des liens tandis que la dichotomie accède directement aux cases d'un tableau ⁶.