Fractional Cascading
Zur Navigation springen
Zur Suche springen
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.