L2 MIASHS, Algorithme et Programmation 2, année 2021

Arbre binaire de recherche

Un arbre est un objet abstrait souvent manipulé en informatique dans plein de contextes différents.

Un peu de terminologie

Un arbre est un ensemble de noeuds qui peuvent être soit des nœuds internes soit des feuilles. Un nœud interne a un ensemble d’enfants qui sont eux même des arbres.

De nombreux exemples d’arbres sont présents en informatique. Le plus simple à voir c’est votre système de fichiers avec les noeuds internes qui sont les dossiers et les fichiers les feuilles.

On définit plusieurs notions supplémentaires:

Des arbres en Python

On définit une notion d’arbre dans ce TD de la façon inductive suivante.

  1. Tous les entiers sont des arbres (de taille 1).
  2. Une liste d’arbre est un arbre.

Par exemple A = [200, [[32, 25], [52]], 42] donne l’arbre suivant:

arbre

Question 1. Vérifier.

Écrire une fonction est_arbre qui prend un argument et qui retourne si c’est bien un arbre.

Question 2. Taille.

Écrire une fonction taille_arbre qui prend en argument un arbre et qui retourne sa taille.

Question 2. Profondeur.

Écrire une fonction profondeur_arbre qui prend en argument un arbre et qui retourne sa profondeur.

Question 3. Cime.

La cime d’un arbre est la liste de ses feuilles en respectant leur ordre d’apparition. Par exemple, pour l’arbre A, c’est [200, 32, 25, 52, 42].

Proposez une fonction cime.

Il est possible de l’écrire en passant par la représentation par chaîne de caractères de l’arbre. On s’attend à un algorithme qui manipule les listes comme des listes ici.

Des arbres binaires de recherche

Un arbre est un arbre binaire s’il est soit:

ou un arbre vérifiant que:

La valeur d’un nœud interne est sa feuille en position 1 dans la liste.

Par exemple [[4, 5, 6], 3, [[1, 20, 30], 2, 44]]

arbre

Par exemple [[[], 3, 22], 4, [5, 220, ,[30, 21, []]]]

arbre

Un arbre binaire est un arbre de recherche si pour chaque nœud les valeurs du sous arbres à droites sont plus petite que la valeur du noeud qui est plus petite que les valeurs du sous-arbre droit.

Par exemple [[4, 5, 6], 10, [[11, 20, 30], 200, 440]]

arbre

Question 1. Vérifier.

Écrire une fonction est_ABR qui prend en argument un arbre et vérifie que c’est un arbre binaire de recherche

Question 2. Contient.

Écrire une fonction contient qui prend en argument un arbre et un élément et qui retourne si l’élément est une des valeurs de l’arbre.

Question 3. Ajout.

Écrire une fonction ajout qui prend en argument un arbre binaire de recherche et un entier et qui ajoute en place l’élément à l’arbre.

Question 4. Complexité

Proposez une analyse de complexité pour contient et ajout en fonction de la profondeur de l’arbre.