Skip List

Einfügen und Suchen in einer sortierten Skip List erkunden. Bis zu 31 ganze Zahlen von −99999999 bis 99999999 eingeben, mit Kommas oder Leerraum getrennt. Leere Kommaeinträge und ungültige Schlüssel werden abgelehnt, Duplikate übersprungen.

Start fügt alle 0,6 Sekunden einen Schlüssel ein. Pause und Schritt erlauben die Einzelprüfung. Leeren entfernt die aufgebaute Liste; geänderte Schlüssel oder ein anderer Startwert ebenfalls. Enter im Suchfeld sucht nach dem Aufbau. Der Schlüsseleditor erlaubt Zeilenumbrüche; Strg/Meta+Enter startet das Einfügen.

Auf L0 stehen alle Schlüssel sortiert. Knoten steigen mit Wahrscheinlichkeit 1/2 auf, begrenzt auf vier Ebenen L0–L3. Derselbe Startwert (0–4294967295) reproduziert die Höhen bei gleicher Eingabereihenfolge. −∞ ist der Startknoten, kein gespeicherter Schlüssel.

Die Suche geht nach rechts, solange der nächste Schlüssel kleiner als das Ziel ist, und anschließend eine Ebene tiefer. Orange markiert besuchte Vorgänger und den Weg; der blaue Rahmen kennzeichnet einen Treffer auf L0. Die optionale Tabelle zeigt aktuelle und nächste Zeiger einschließlich Stopps vor dem Abstieg. Wiederholte Zeilen können einen Stopp nach einer Bewegung darstellen.

Beispiel: 3,7,2,9,5,1,8 mit Startwert 42; danach 5 und 6 suchen. 5 existiert, 6 endet vor seiner möglichen Einfügeposition. Große Diagramme scrollen lokal mit lesbarer Schrift.

Eingaben, Fortschritt, letzter Pfad und geöffnete Details werden lokal gespeichert. Nach dem Neuladen bleibt die Animation pausiert. Ein geänderter Suchentwurf entfernt den alten Pfad. Übergroße Entwürfe bleiben in der laufenden Sitzung; Schlüssel vor dem Neuladen herunterladen.

Lehrmodell einer Menge ohne Löschung oder Nutzdaten. Vier feste Ebenen belegen keine asymptotische Leistung für beliebig große Datenmengen. Grundlage: William Pughs Skip-List-Algorithmus.