3.Aufgabe
Skip-Lists
Gegeben sei eine Suchanfrage bestehend aus zwei Wörtern.
Für den einen Term besteht die Posting-Liste aus folgenden 16 Einträgen:
( 4, 6, 10, 12, 14, 16, 18, 20, 22, 32, 47, 81, 120, 122, 157, 180 )
Für den anderen Term besteht die Posting-Liste nur aus einem Eintrag:
( 47 )
Bestimmen Sie die Anzahl notwendiger Vergleichsoperationen für
1. herkömmliche Posting-Listen
2. Posting-Listen mit Skip-Pointers und einer Skip-Länge von √P
Begründen Sie Ihre Antwort!
Kann jemand mir ein paar Tipps geben?
Danke!
MFG