C5.3 : Arbres binaires de recherche ABR

Définition d'un Arbre Binaire de Recherche (ABR)

Un arbre binaire de recherche (ABR) est un arbre binaire tel que :

  • - les valeurs du sous-arbre de gauche sont inférieures ou égales à la valeur de la racine ;
  • - les valeurs du sous-arbre de droite sont strictement supérieures à la valeur de la racine ;
  • - les sous-arbres de gauche et de droite sont eux-mêmes des arbres binaires de recherche.

Q1 : L'arbre ci-dessous est-il un arbre binaire ? Est-il un arbre binaire de recherche ?

Q2 : Construire deux ABR différents avec tous les entiers de 1 à 10.

Q3 : Afficher les valeurs dans l'ordre du parcours infixe. Qu'observez-vous ?

Recherche d'une valeur dans un ABR

Dans cette partie, on souhaite pouvoir rechercher une valeur dans un ABR.

On travaillera avec une implémentation des arbres binaires à l'aide de tuples imbriqués, avec None pour l'arbre est vide.

Algorithme de la recherche d'une valeur dans un ABR

Q4 : Écrire une fonction récursive qui permet de savoir si une valeur est dans un ABR. La fonction prendra deux paramètres : un tuple correspondant à un arbre, la valeur recherchée.

Q5 : Appliquer la fonction à l'arbre ci-dessous en recherchant les valeurs 8, 13 et 17 :

Q6 : Combien de fois se fait l'appel récursif dans le pire cas en fonction de la hauteur de l'arbre ?

ABR équilibré

Q7 : On considère les deux ABR ci-dessous dont les valeurs sont identiques. Dans lequel la recherche sera-t-elle globalement la plus efficace ?

Définition

Un arbre binaire est dit équilibré si :

Q8 : Donner un exemple d'ABR équilibré et un exemple d'ABR non équilibré.

Q9 : L'arbre binaire ci-dessous est-il un ABR ? Est-il équilibré ?

Q10 : Quel peut-être l'intérêt d'un ABR équilibré pour faire une recherche de valeur ?

Ajout d'une valeur dans un ABR

Dans cette partie, on travaillera avec une implémentation des arbres binaires à l'aide de tuples imbriqués, avec None si l'arbre est vide.

Q11 (sur papier) : Ajouter les valeurs 7, 11 et 13 à l'arbre de la question Q5 de façon à conserver son caractère d'ABR.

Q12 : Écrire une fonction qui prend un ABR et une valeur en paramètre et renvoie un ABR correspondant à l'ABR passé en paramètre auquel la valeur a été ajoutée. Si la valeur est déjà dans l'arbre, la fonction doit renvoyer l'ABR sans modification.