AVL-Baum und Duplikate
-
Hallo,
mit AVL-Bäumen kann man ja effizient eindeutige Schlüssel in einer Schlüsselmenge finden.
Ist es auch möglich, einen AVL-Baum (oder eine Modifikation davon) zu nutzen, wenn ich effizient alle Objekte aus einer Liste filtern will, die eine bestimmte Eigenschaft haben? Beispielsweise alle Personen, die 25 Jahre alt sind. Dies würde ja dem Problem entsprechen, in einen AVL-Baum doppelte Schlüssel zu halten (in dem Fall Schlüssel "25").
Danke
-
Was müsste denn die Datenstruktur genau können?
Wenn du Abfragen machen willst wie z.B. "Gebe alle Personen aus, die zwischen 10 und 15 Jahren alt sind", dann wären Range Trees eine Möglichkeit. Die kann man auch balancieren. Ist jedoch kompliziert.
-
Hi, danke für deine Antwort.
Sie sollte genau das können, was ich gesagt habe. Keine Range-Suche oder sowas. Einfach nur ein balancierter Baum, der gleiche Werte enthalten darf, und statt einem Element eine Menge von Elementen (die gleiche Werte halt) zurückliefert und möglichst trotzdem in O(log n) läuft.
-
Solange du auf dem Unterscheidungskriterium (hier: Alter) eine Ordnungsrelation definieren kannst, sollte eigentlich jeder balancierte Suchbaum diese Anforderungen erfüllen.
Problematisch könnte es werden, wenn du Duplikate bezüglich mehrerer Kriterien im selben Datenbestand suchen willst, oder wenn du Kriterien hast, die du nicht vernünftig ordnen kannst (z.B. Haarfarben oder Automarken).PS: Wenn du einen C++ Compiler greifbar hast, schau dir mal den Unterschied zwischen set<>/map<> und multiset<>/multimap<> an.
-
Ist es auch möglich, einen AVL-Baum (oder eine Modifikation davon) zu nutzen, wenn ich effizient alle Objekte aus einer Liste filtern will, die eine bestimmte Eigenschaft haben? Beispielsweise alle Personen, die 25 Jahre alt sind. Dies würde ja dem Problem entsprechen, in einen AVL-Baum doppelte Schlüssel zu halten (in dem Fall Schlüssel "25").
Du könntest doch unter dem Key 25 eine Liste mit allen passenden Values verwalten.
Zb in C++ einen Vector.