Fractional Cascading

Fractional Cascading bietet die Möglichkeit, die Bereichssuche in einem Bereichsbaum schneller zu gestalten. Dabei wird der jeweils höchstdimensionale assoziierte Baum nicht als Baum, sondern als Array gespeichert. Von jedem Element des Arrays gehen Verweise auf gleich große bzw. größere Schlüsselwerte in den beiden Sohnarrays. Durch Verfolgen dieser Verweise kann in O(1+k) in dem Baum gesucht werden.

Literatur

• R. Tamassia, J. S. Vitter: Optimal cooperative search in fractional cascaded data structures. In: Algorithmica. Band 15, Heft 2, 1996, ISSN 0178-4617, S. 154–171 (englisch).