Skip-Listen
Wörterbücher (Dictionaries):
Mengen von Elementen eines Grundtyps mit Operationen Suchen, Einfügen, Entfernen.
Wörterbuchproblem: Finden geeigneter Datenstruktur und effizienter Algorithmen für diese Operationen
(Listen eine von mehreren Realisierungsmöglichkeiten).
Skip-Listen: Effiziente Realisierungsmöglichkeit.
Def.: Eine perfekte Skip-Liste ist eine sortierte, verkettete lineare Liste, mit Kopf und Endelement, wobei gilt:
1) jedes 2i-te Element hat Zeiger auf das 2i Positionen weiter rechts stehendes Element.
2) Endelement hat Wert unendlich.