Un arbre est une structure définie récursivement, dans laquelle chaque élément a zéro, une ou plusieurs sous-structures du même type. L'efficacité de l'arbre (sauf l'arbre union-find) vient du fait que chaque élément contenu est accessible à partir de la racine en O(log n) opérations.
Certains arbres permettent le stockage d'éléments uniquement aux feuilles (comme l'arbre 2-3) alors que d'autres stockent des éléments dans l'ensemble des cellules de l'arbre.