Insérer dans un arbre binaire de recherche

Les nœuds d'un arbre peuvent être munis d'étiquettes. Considérons des étiquettes qui peuvent être classées dans un certain ordre, comme les chaînes de caractères (par ordre alphabétique) ou les nombres.

Un arbre binaire de recherche est un arbre dont les étiquettes peuvent être classées. De plus, dans un arbre binaire de recherche :

• tous les nœuds du sous-arbre gauche ont une étiquette inférieure à celle de la racine ;
• tous les nœuds du sous-arbre droit ont une étiquette supérieure à celle de la racine ;
• les sous-arbres gauche et droit sont eux-mêmes des arbres binaires de recherche.