Arbres - ABR

I. Objectifs des ABR ou Arbres Binaires de Recherche

ABR

👉 Un arbre binaire de recherche (ABR) est un arbre binaire dans lequel chaque nœud possède une clé, telle que chaque nœud du sous-arbre gauche ait une clé strictement inférieure à celle du nœud considéré, et que chaque nœud du sous-arbre droit possède une clé supérieure ou égale à celle-ci — selon la mise en œuvre de l'ABR, on pourra interdire ou non des clés de valeur égale.

😀 Un arbre binaire de recherche permet des opérations rapides pour rechercher une clé, insérer ou supprimer une clé.

Source : https://fr.wikipedia.org/wiki/Arbre_binaire_de_recherche

Source de l'image : http://ressources.unisciel.fr/algoprog/s46bst/emodules/br00macours1/res/br00cours-texte-xxx.pdf

Définition

En informatique, un arbre binaire de recherche ou ABR (en anglais, binary search tree ou BST) est une structure de données représentant un ensemble dont les clés appartiennent à un ensemble totalement ordonné.

Les opérations caractéristiques sur les arbres binaires de recherche sont l’insertion, la suppression, et la recherche d’une valeur. Ces opérations sont peu couteuses si l’arbre n’est pas trop déséquilibré.

💡 En pratique, les valeurs sont des clés permettant d’accéder à des enregistrements.

Définition d'un ABR

Un arbre binaire de recherche est un arbre binaire dont les valeurs des nœuds (valeurs qu'on appelle étiquettes, ou clés) vérifient la propriété suivante :

• l'étiquette d'un nœud est supérieure ou égale à celle de chaque nœud de son sous-arbre gauche.
• l'étiquette d'un nœud est strictement inférieure à celle du chaque nœud de son sous-arbre droit.

• À noter que l'arbre 3 (qui est bien un ABR) est appelé arbre filiforme.

• L'arbre 5 n'est pas un ABR à cause de la feuille 9, qui fait partie du sous-arbre gauche de 3 sans lui être inférieure.

• Remarque : on pourrait aussi définir un ABR comme un arbre dont le parcours infixe est une suite croissante.

Une définition plus "mathématique"

Soit E un ensemble muni d’une relation d’ordre total, et soit A un arbre binaire portant des valeurs de E. L’arbre A est un arbre binaire de recherche si pour tout nœud p de A, la valeur de p est strictement plus grande que les valeurs figurant dans son sous-arbre gauche et strictement plus petite que les valeurs figurant dans son sous-arbre droit. Cette définition suppose donc qu’une valeur n’apparaît au plus qu’une seule fois dans un arbre de recherche.

⚠️ Attention, nous verrons dans ce cours d'autres définitions possibles des ABR, légèrement différentes (possibilités de clés identiques notamment, que l'on peut appeler des "doublons").

😉 A chaque fois, la définition des ABR sera précisée.

II. Utilisation de binarytree pour créer un ABR et rechercher une clé

😀 Voici une correction ...

Vidéo Lumni

Dans la vidéo qui suit, la définition d'un ABR est légèrement différente de celle que nous venons de voir.

ABR sur Lumni

III. Implémentation itérative et récursive d'un ABR, recherche de clé et insertion

😀 Voici une correction ...

IV. Utilisation d'un ABR

⌛ Avant de commencer

Vous devez travailler sur Basthon

Télécharger dans le même dossier :

• 🌐 Fichier liste_mots.txt : "Clic droit", puis "Enregistrer la cible du lien sous"

• 🌐 TD TP3_ABR_sujet.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"

😀 Voici une correction ...

• 🌐 Fichier liste_mots.txt : "Clic droit", puis "Enregistrer la cible du lien sous"

• 🌐 Correction du TD TP3_ABR_corr.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"

V. Bilan

✍ A noter :

👉 Un arbre binaire de recherche (ABR) est une structure qui permet une recherche de façon très efficace .

😊 La recherche dans un ABR équilibré est de coût logarithmique

Crédits

Jean-Louis Thirot , Mireille Coilhac, Valérie Mousseaux, Gilles Lassus