Die Frage lautet also: Wozu muss die Liste sortiert sein? Der Namenlose hat den B+-Baum im Rahmen einer Lehrveranstaltung Programmiert (klasse)
Naja, nur dafür hätte ich es wohl auch nicht gemacht. Eine sortierte Liste braucht man z.B.
hierfür. Ein Binomialheap ist da auch schon im Einsatz, reicht aber nur für eine der beiden Datenstrukturen.
Ich teste meine Container einmal mit einer sortierten Liste, und einmal mit einer zufällig zusammengewürfelten Liste.
Die sorted Inserts finde ich recht wichtig, da man damit Masseninserts oft wesentlich beschleunigen kann.
Ich hatte erst mal nur Sorted-Inserts getestet, weil es eigentlich spannender ist. Für wirklich zufällige Inserts bräuchte man theoretisch gar keinen
balancierten Baum.
Für einen umfangreichen Test muss natürlich beides getestet werden, das ist klar.