Speichern separater Werte für doppelte Schlüssel in einem Suchbaum

Question

Ich versuche einen Suchbaum zu erstellen, der doppelte Schlüssel speichern kann und unterschiedliche Werte für diese Schlüssel hat.

Grundsätzlich habe ich Hashcode in Form einer Bitfolge. Der Wert ist diese Bitzeichenfolge und der Schlüssel ist die Anzahl der 1, die in der Bitzeichenfolge angezeigt werden.

Zum Beispiel konnte ich zwei Bitfolgen haben:

bitstring1 = "00001111"; 
bitstring2 = "11110000"; 

So haben sie identische Schlüssel:

key1 = 4; 
key2 = 4; 

Ist es möglich, diese in einen Suchbaum zu implementieren?

Answer 1

Ich kann noch keinen direkten Kommentar posten, aber können Sie nicht nur einen Baum, sondern auch eine statische Karte oder so etwas haben? Wenn das der Fall ist, dann würden die folgenden Links hilfreich sein.

Die Art, wie ich es sehe, haben Sie einen Fall, wo der Schlüssel 4 zu möglichen Werten haben kann, so wie eine Karte wie map <Integer, List<String>> deklarieren gibt es andere Methoden im folgenden Link beschrieben. Es tut mir leid, dass ich dies als Antwort gepostet habe, aber ich kann nichts dazu sagen.

Wenn Sie sie wirklich als separate Schlüssel speichern möchten, dann denke ich, dass der zweite Link nützlicher sein könnte.

HashMap with multiple values under the same key

How to create a HashMap with two keys (Key-Pair, Value)?

Answer 2

Eine Möglichkeit ist ein binärer Suchbaum, in dem der Knoten eine Liste von Werten enthält, die den Schlüssel entsprechen. Dies ist eine sehr einfache Ergänzung zu einem standardmäßigen binären Suchbaum, könnte aber ineffizient werden, wenn viele Werte für einen Schlüssel vorhanden sind, da jeder Zugriff eine sequenzielle Suche nach O (n) erfordert (wobei n die Anzahl der Werte für diesen Schlüssel ist) der Werte dieses Schlüssels.

Wenn Suchvorgänge sehr viel häufiger sind als das Hinzufügen oder Löschen, können Sie die Werteliste sortieren. Einfügungen und Löschungen würden immer noch diesen sequenziellen Scan erfordern, aber Suchvorgänge könnten eine binäre Suche durchführen. Je nach Anwendung ist dies ein guter Kompromiss.

Eine andere Möglichkeit besteht darin, diese Werteliste zu einem anderen binären Suchbaum zu machen. Ihre Knoten würden also einen binären Wertebaum enthalten. Das wäre effizienter als eine sortierte Liste, würde aber mehr Speicher kosten.