Optimierungsproblem (Tabellen mit Baumstruktur)

[Zacherl]

Dein zweiter Baum ist nicht ganz korrekt, da OBJ1 ja einen anderen Wert für A hat, als OBJ2 und OBJ3. OBJ1 kannst du in der Betrachtung aber auch vorerst mal ausblenden, da das Problem in meinem Beispiel vorerst nur den Ast A = 54 betrifft.

Der dritte Baum ist prinzipiell korrekt (da ist nur die 004 etwas verrutscht ). Tatsächlich hat jeder Filter in meiner Implementation ein 0-Element, worin ich dann die Objekte einordne, für die der Filter nicht zutrifft. Das Problem ist allerdings nicht, die "unnötigen" Filter loszuwerden (das macht mein Algorithmus schon beim Einfügen neuer Objekte), sondern es geht konkret um die Reihenfolge der notwendigen Filter pro Ast.

Ziel soll sein, die Gesamtkapazität des Baumes zu minimieren.

Hierbei ist zu beachten, dass z.b. ein Filter C, bei dem nur ein Element gesetzt ist, trotzdem die volle Kapazität von 5 besitzt. In meinem Beispiel sieht man im 054er Ast ja ganz schön, dass beim naiven Einfügen (erst FilterA, dann FilterB wenn vorhanden, dann FilterC wenn vorhanden, ..) 1x FilterB und 2x FilterC benötigt werden. Man könnte die Objekte aber genauso gut einordnen, indem man erst 1x FilterC und danach 2x FilterB verwendet. Dadurch, dass FilterB aber eine kleinere Kapazität hat, als FilterC, spart man sich am Ende 2 unnötige leere Plätze.