Efektywne pamięciowo trwałe struktury danych

Trwałe struktury danych mają zastosowanie w wielu dziedzinach, m.in. implementacji kompilatorów i algorytmów geometrycznych. Driscoll et al. pokazali jak wydajnie uczynić dowolną wskaźnikową strukturę danych strukturą trwałą. Wzbogacamy ich metody o możliwość efektywnego pamięciowo usuwania wersji. Pogarszamy przy tym złożoności czasowe jedynie o czynnik logarytmiczny.Persistent data structures are useful in many ares, e.g. compiler implementation and geometric algorithms. Driscoll et al. have shown how to make arbitrary linked data structures persistent efficiently. We augment their methods to allow memory efficient deletion of versions. The obtained time complexities are worse by only a logarithmic factor