Fractional Cascading

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 gleichgroße bzw. größere Schlüsselwerte in den beiden Sohnarrays. Durch Verfolgen dieser Verweise kann in O(1+k) in dem Baum gesucht werden.


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Fractional cascading — In computer science, fractional cascading is a technique to speed up a sequence of binary searches for the same value in a sequence of related data structures. The first binary search in the sequence takes a logarithmic amount of time, as is… …   Wikipedia

  • Fractional reserve banking — Banking A series on Financial services …   Wikipedia

  • List of mathematics articles (F) — NOTOC F F₄ F algebra F coalgebra F distribution F divergence Fσ set F space F test F theory F. and M. Riesz theorem F1 Score Faà di Bruno s formula Face (geometry) Face configuration Face diagonal Facet (mathematics) Facetting… …   Wikipedia

  • Cascade — A cascade is a type of waterfall or a series of waterfalls.Cascade may also refer to: Places North America* Cascade Range, a mountain range on the west coast of North America * Cascade Volcanoes, a grouping of volcanoes on the west coast of North …   Wikipedia

  • Range tree — Ein Bereichsbaum (engl.: range tree) ist eine Datenstruktur für das Speichern einer Menge von Punkten im k dimensionalen reellen Raum . Er wird in der Informatik im Bereich der algorithmischen Geometrie eingesetzt und unterstützt effizient… …   Deutsch Wikipedia

  • Leonidas John Guibas — est professeur d informatique à l université Stanford, où il dirige le groupe de recherche sur la géométrie algorithmique. Il est aussi membre des laboratoires de synthèse d image et d intelligence artificielle. Sommaire …   Wikipédia en Français

  • Algorithmic efficiency — In computer science, efficiency is used to describe properties of an algorithm relating to how much of various types of resources it consumes. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or… …   Wikipedia

  • Point location — The point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems (GIS), motion planning, and computer aided… …   Wikipedia

  • Segment tree — In computer science, a segment tree is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its content cannot be… …   Wikipedia

  • Leonidas J. Guibas — Leonidas John Guibas is a professor of computer science at Stanford University, where he heads the geometric computation group and is a member of the computer graphics and artificial intelligence laboratories. Guibas was a student of Donald Knuth …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”