Diszkrét intervallum kódoló fa

A diszkrét intervallumkódoló fa egy olyan struktúra, amely teljes sorrendű, előd és utódfunkciójú típusú részhalmazokat tárol. Az egyszerűség kedvéért csak az egész számkészletek esetét vesszük figyelembe; az általánosítás nem nehéz. A diszkrét intervallumkódoló fa azon a megfigyelésen alapul, hogy az egész számok halmaza < i | a >tökéletesen ábrázolható a zárt intervallummal [a, b]. Az általános elképzelés az, hogy egy halmazt ábrázolunk egy egész számokat tartalmazó bináris keresőfával, amelyben a maximális szomszédos részhalmazokat egy-egy intervallum képviseli. Például a [6, 9, 2, 13, 8, 14, 10, 7, 5] számsorozat bináris keresési fába illesztése egy diszkrét intervallumot kódoló fába az alább látható fa struktúrákat eredményezi:

zsírkészletekhez

Letöltheti a megvalósítást az ML-ből vagy a Haskellből:

  • diet.sml
  • diéta.hs
A struktúrát részletesebben a Diets for Fat Sets című cikkben fejtik ki

A beszúrási funkció hatékony verziójának lépésenkénti levezetését itt foglaljuk össze.