Informatik Datenstrukturen – Skip-Listen und Balancierung
Karteikarten zum Thema „Informatik“ · 14 Karten · von atrio. Beispiele: Was ist eine Skip-Liste? · Wie wird die Höhe eines Knotens in einer Skip-Liste bestimmt?
Karten
14 KartenWas ist eine Skip-Liste?
Rückseite
Eine probabilistische Datenstruktur aus mehreren verketteten Listen mit Express-Spuren, die erwartete O(log n)-Suchzeit bei einfacher Implementierung bietet.
Wie wird die Höhe eines Knotens in einer Skip-Liste bestimmt?
Rückseite
Durch wiederholtes Münzwurf (Coin-Flip): Solange Kopf fällt, steigt die Ebene; die erwartete Höhe beträgt 1/(1-p) mit p=0,5.
Welche Ebenen hat eine Skip-Liste mindestens?
Rückseite
Ebene 0 enthält alle Elemente als sortierte Basisliste; höhere Ebenen sind Dünnungen mit Express-Pfeilern für schnelles Überspringen.
Wie funktioniert die Suche in einer Skip-Liste?
Rückseite
Start in der höchsten Ebene, rechts solange nächsten Knoten ≤ Schlüssel, dann eine Ebene tiefer – bis Ebene 0 das Element findet oder nicht.
Was ist die erwartete Zeitkomplexität für Suche, Einfügen und Löschen?
Rückseite
Erwartet O(log n) für alle drei Operationen, da die Höhe logarithmisch verteilt ist und jede Ebene etwa halb so viele Knoten hat.
Was ist die worst-case Zeitkomplexität einer Skip-Liste?
Rückseite
O(n) bei extrem unglücklicher Münzwurf-Sequenz, die alle Knoten in einer einzigen Kette degenerieren lässt – extrem unwahrscheinlich.
Wie läuft das Einfügen eines neuen Schlüssels ab?
Rückseite
Suche Pfad merken, neuen Knoten mit zufälliger Höhe erzeugen, in alle betroffenen Ebenen über Vorwärts- und Rückwärtszeiger einhängen.
Wie wird ein Knoten gelöscht?
Rückseite
Suche Pfad merken, Knoten in allen Ebenen aus den Vorwärtszeigern der Vorgänger entfernen, Speicher freigeben – keine Rebalancierung nötig.
Wie hoch ist der Speicherbedarf einer Skip-Liste im Erwartungswert?
Rückseite
Erwartet O(n) Zeiger, da jeder Knoten im Mittel 1/(1-p)=2 Ebenen hat; Konstantfaktor größer als bei einfach verketteten Listen.
Welchen Vorteil haben Skip-Listen gegenüber AVL- oder Rot-Schwarz-Bäumen?
Rückseite
Einfachere Implementierung, keine komplexen Rotationsfälle, natürliche Parallelisierbarkeit und Cache-freundlichere Speicherzugriffsmuster.
Welchen Nachteil haben Skip-Listen gegenüber balancierten BSTs?
Rückseite
Nicht deterministische Laufzeit (nur erwartet), höherer Speicherverbrauch durch Vorwärtszeiger, schlechtere Cache-Lokalität bei sehr großen Datenmengen.
Wo werden Skip-Listen in der Praxis eingesetzt?
Rückseite
Redis (Sorted Sets), LevelDB/RocksDB (MemTables), Java ConcurrentSkipListMap, Lucene-Indizes – überall wo lock-freie Konkurrenz gefragt ist.
Was ist der Unterschied zwischen deterministischen und probabilistischen Skip-Listen?
Rückseite
Deterministische (z. B. 1-2-3-Skip-Listen) garantieren O(log n) worst-case durch feste Aufbau-Regeln; probabilistische nutzen Zufall für erwartete Laufzeit.
Wie wirkt sich der Parameter p auf Höhe und Performance aus?
Rückseite
Kleineres p (z. B. 0,25) → höhere Türme, weniger Zeiger pro Knoten, schnelleres Suchen, aber mehr Speicher für hohe Knoten; p=0,5 ist Standard.