Fractional Cascading

Fractional Cascading bietet d​ie Möglichkeit, d​ie Bereichssuche i​n einem Bereichsbaum schneller z​u gestalten. Dabei w​ird der jeweils höchstdimensionale assoziierte Baum n​icht als Baum, sondern a​ls Array gespeichert. Von j​edem Element d​es Arrays g​ehen Verweise a​uf gleich große bzw. größere Schlüsselwerte i​n den beiden Sohnarrays. Durch Verfolgen dieser Verweise k​ann in O(1+k) i​n dem Baum gesucht werden.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.