Arbre binaire de recherche

[pic 1]T NSI        A        2023-2024

[pic 2]

1. Notion  ⊲

D’une manière générale, un arbre binaire de recherche (abrégé en ABR) est un arbre binaire dont les nœuds contiennent des valeurs qui peuvent être comparées entre elles, comme des entiers ou des chaînes de caractères par exemple ou des objets ayant des attributs « comparables » (en poo).

Dans un ABR, pour tout nœud de l’arbre, toutes les valeurs situées dans le sous-arbre gauche (respective-ment droit) sont plus petites (respectivement plus grandes) que la valeur située dans le nœud.

[pic 3]

Remarque : Les mêmes valeurs peuvent être stockées dans plusieurs ABR différents. (cf. exemples pré-cédents

•        •

[pic 4]

2. Représentation en Python  ⊲

Un ABR est un arbre binaire ; on le représente en Python exactement comme dans le document _        ,

avec la classe Nœud. On ne fait qu’ajouter deux contraintes :

• les valeurs contenues dans les nœuds peuvent être comparées avec les opérations <, >, =,etc. de Py-

thon ;

• les arbres verifient la propriété d’ABR.

Ces deux contraintes ne sont pas encodées en Python. Elles sont uniquement supposées ou garanties, selon le cas, par les fonctions que nous allons écrire dans les sections suivantes.

•        •

[pic 5]

1. Opérations  ⊲

Les fonctions (et méthodes en poo) définies dans le cadre d’une implémentation d’arbres binaires, à savoir taille, hauteur et parcours_infixe restent valables pour des ABR.

En particulier le parcours infixe d’un ABR affiche les valeurs contenues dans l’ABR par ordre croissant. En effet, il commence par afficher les valeurs du sous-arbre gauche, puis affiche la racine, et affiche enfin les valeurs du sous-arbre droit.

•        •

[pic 6]

1. Opérations spécifiques aux ABR  ⊲

Recherche dans un ABR        :

La propriété d’un ABR tire son intérêt de l’efficacité de la recherche qu’elle permet. En effet, pour cher-cher une valeur dans un ABR, il suffit de la comparer à la valeur à la racine puis, si elle est différente, de se diriger vers un seul des deux sous-arbres. On élimine ainsi complètement la recherche dans l’autre sous-arbre. On va écrire :

Lycée Bertran de Born        1 sur 3

[pic 7]RETURN

T NSI        A        2023-2024

[pic 8][pic 9][pic 10][pic 11]

1

2

D E F        a p p a r t i e n t ( x , a ) :

[pic 12]

" " "        d é t e r m i n e        s i        l a        v a l e u r        x        e s t        d a n s        l ’ a r b r e        a        " " "

On commence par le cas d’un arbre vide,

[pic 13][pic 14][pic 15][pic 16]

1

2

I F        a        I S        N O N E :

[pic 17]

RETURN        FALSE

Dans le cas contraire, cela veut dire que l’arbre contient au moins un nœud. On compare donc x avec la valeur située à la racine de l’arbre, c’est à dire a.valeur. Si la valeur x est plus petite, il faut continuer la recherche dans le sous-arbre gauche, ce que l’on fait récursivement,

...