Aufgaben zu Suchbäumen (und Heaps)

• Gewichtsbalancierte Bäume mit globalem (amortisiertem) Rebalancieren
  • Bestimmen Sie rechnerisch den günstigsten Wert des Balance-Faktors a, in Abhängigkeit von der Anzahl der lookup im Verhältnis zur Anzahl der insert.
  • Implementieren Sie die Datenstruktur und prüfen Sie experimentell Ihren berechneten Wert für a.

• Pairing Heaps
  • Implementieren Sie und stellen Sie Messungen an. Finden Sie eine gute Potentialfunktion!
  • Bauen Sie dazu die Kontoführung ins Programm ein: es gibt ein Konto, auf das zahlen Sie vor jeder Operation etwas ein, und während der Ausführung heben Sie für jeden Speicherzugriff (oder ähnlich) eine Mark ab.

• Treaps
  • Implementieren Sie Einfügen und Löschen sowie Extract.