Structures de données

1 ) 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 ou un tableau associatif dont les clés appartiennent à un ensemble totalement ordonné. Un arbre binaire de recherche permet des opérations rapides pour rechercher une clé, insérer ou supprimer une clé.


2 ) vocabulaire

Voici ce que dit wikipedia au sujet des arbres binaires de recherche :
Un arbre binaire de recherche 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é inférieure ou égale à 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. Les nœuds que l'on ajoute deviennent des feuilles de l'arbre.
Un arbre binaire de recherche est dit complet si tous les niveaux de l'arbre sont remplis, sauf éventuellement le dernier, sur lequel les nœuds sont à gauche.
Un arbre binaire parfait est un arbre complet dont toutes les feuilles sont à la même hauteur (le dernier niveau est complètement occupé).
Un arbre binaire est dit dégénéré si chacun de ses nœuds a au plus un fils.
Un arbre binaire est équilibré si tous les chemins de la racine aux feuilles ont la même longueur.


Pour bien comprendre , voici des vidéos permettant de vous familiariser avec le vocabulaire et quelques types d'arbres.

* Voici une présentation vidéo des ABR


Pour bien comprendre , voici un pdf permettant de vous familiariser avec les arbres binaires de recherche.