L’arbre binaire de recherche (BST) est une structure de données à base de nœuds ordonnés et d’arborescence binaire. Les nœuds ont une valeur et deux nœuds enfants (un arbre binaire a un maximum de deux nœuds enfants) qui lui sont attachés à gauche et à droite. À l’exception du nœud racine, tous les nœuds ne peuvent être référencés que par leur parent. Une BST a les propriétés suivantes : Tous les nœuds du sous-arbre de gauche sont plus petits que le nœud racine.