Ceci est une ancienne révision du document !
Les arbres sont des types abstraits permettant de structurer les données.
Un arbre binaire un cas particulier d'arbre qui peut se présenter sous la forme :
Vocabulaire :
Dans un arbre binaire, chaque nœud possède au plus 2 fils (souvent appelés fils droit et fils gauche).
Le sous-arbre d'un nœud est le deux sous-arbre ayant pour racine le fils du nœud. Chaque nœud peut avoir jusqu'à deux sous-arbres (un par fils).
Un arbre binaire de recherche est un cas particulier d'arbre binaire. Pour avoir un arbre binaire de recherche :
* il faut avoir un arbre binaire * il faut que les clés de noeuds composant l'arbre soient ordonnables (on doit pouvoir classer les noeuds, par exemple, de la plus petite clé à la plus grande) * soit x un noeud d'un arbre binaire de recherche. Si y est un noeud du sous-arbre gauche de x, alors il faut que y.clé ⩽ x.clé. Si y est un noeud du sous-arbre droit de x, il faut alors que x.clé ⩽ y.clé