Algorithmen und Datenstrukturen · Senior · Frage 13 von 75
Was ist eine Skip List?
- 1Eine sortierte Liste mit zufälligen Expressspuren für schnelle Suche
- 2Eine Liste, die beim Einfügen doppelte Werte überspringt
- 3Ein Array, aus dem jedes zweite Element entfernt wird
Antwort zeigen
Richtige Antwort: Eine sortierte Liste mit zufälligen Expressspuren für schnelle Suche
Erklärung
Jeder Knoten bekommt eine zufällige Höhe; höhere Ebenen überspringen mehr Knoten. Suchen, Einfügen und Löschen sind im Schnitt O(log n), und die Struktur lässt sich leichter nebenläufig machen als ein balancierter Baum. Sorted Sets in Redis nutzen Skip Lists.