Inhaltsverzeichnis 1  Das Verwalten von Datenmengen 1 1.1   binäre Suchbäume als Datenstruktur . . . . . . . . . . . . . . . .     1 2  Treaps 2 2.1   Random Treaps . . . . . . . . . . . . . . . . . . . . . . . . . . . .     3 2.1.1   Mulmuley Games . . . . . . . . . . . . . . . . . . . . . . .     3 2.1.2   Laufzeitanalyse von FIND . . . . . . . . . . . . . . . . . .     5 2.1.3   Zur Anzahl der erwarteten nötigen Rotationen  . . . . . .     6 3  Skip Lists 8 3.1   Random Skip Lists . . . . . . . . . . . . . . . . . . . . . . . . . .     9 4  Hash Tables 11 4.1   Universale Hash Familien  . . . . . . . . . . . . . . . . . . . . . .   11 4.2   Anwendung auf Dynamic Dictionary . . . . . . . . . . . . . . . .   13 4.3   Konstruktion von Familien universaler Hashfunktionen . . . . . .   14 4.4   Stark universale Hashfamilien . . . . . . . . . . . . . . . . . . . .   16 5  Hashing mit O(1) Suchzeit 17 5.1   Fast perfekte Hashfamilien . . . . . . . . . . . . . . . . . . . . . .   17 5.2    Erreichen der Schranke der Zugriffszeit .  .  .  .  .  .  .  .  .  .  .  .  .  .  .    19 II