Arbres binaires et arbres binaires de recherche

Un arbre binaire est une structure hiérarchique où chaque nœud possède au plus deux fils (gauche et droit). La racine est le nœud sans parent, les feuilles sont les nœuds sans fils. La taille est le nombre de nœuds, la hauteur est la longueur du plus long chemin racine-feuille. Un arbre binaire de recherche (ABR) respecte la propriété : pour chaque nœud, toutes les valeurs du sous-arbre gauche sont inférieures, et toutes celles du sous-arbre droit sont supérieures. Par exemple, dans un ABR contenant 5 à la racine, 3 à gauche et 7 à droite, la recherche de 7 ne visite que 2 nœuds. La recherche, l'insertion et la suppression dans un ABR équilibré sont en O(log n), mais un ABR dégénéré (tous les nœuds d'un seul côté) donne O(n).