Дървото за кодиране на дискретни интервали е структура за съхраняване на подмножества от типове, имащи общ ред и предшественик и функция наследник. Разглеждаме за простота само случая за цели числа; обобщението не е трудно. Дървото за кодиране на дискретни интервали се основава на наблюдението, че множеството от цели числа < i | a >може да бъде представено перфектно чрез затворения интервал [a, b]. Общата идея е да се представи набор от двоично дърво за търсене на цели числа, в които максималните съседни подмножества са представени от интервал. Например, вмъкването на последователността от числа [6, 9, 2, 13, 8, 14, 10, 7, 5] в бинарно дърво за търсене, съответно, в дискретно дърво за кодиране на интервали води до дървесните структури, показани по-долу:

диети

Можете да изтеглите внедряването в ML или Haskell:

  • diet.sml
  • диета.hs
Структурата е обяснена по-подробно в статията Diets for Fat Sets.

Тук е обобщено поетапното извеждане на ефективна версия за функцията за вмъкване.