Heuristiken, die Datenstrukturen dynamisch organisieren

Zunächst betrachten wir Heuristiken, die verkettete Listen dynamisch ändern, wodurch häufiger aufgerufene Schlüssel näher an die „Spitze“ der Liste rücken. Wir zeigen, dass die Regel „Move to Front“ die Zugriffszeit viel schneller reduziert als die Transpositionsregel, und geben dann eine „hybride“ Version dieser beiden Regeln an, die die Zugriffszeit schnell verringert und geringe asymptotische Kosten hat. Außerdem diskutieren wir Regeln, die davon ausgehen, dass ein Zähler mit jedem Schlüssel verbunden ist. Zweitens betrachten wir Regeln für binäre Suchbäume. Die monotone Baumregel funktioniert nur gut, wenn die Entropie der Wahrscheinlichkeitsverteilung für Schlüsselanfragen gering ist; andernfalls reduziert sie die Zugriffszeit nicht. Eine letzte Regelklasse, die Rotation verwendet, bietet nahezu optimale Leistung.