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).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.