Il datatype 'dltree' è un datatype di albero di ricerca binario, dove ad ogni nodo sono mantenuti un indice e un elemento, e le foglie non hanno alcuna informazione. Il confronto tra indici è fatto usando la relazione di oridinamento totale polimorfica '(<)'. Ogni nodo mantiene anche un intero per il suo livello AA, per poter mantenere l'invariante AA. Si noti che non c'è alcuna necessità che le foglie mantengano il proprio livello perché esso è sempre 0.