BInärbaum in Java

[javatar]

Hallo zusammen,

ich brauche (glaube ich) für ein Projekt eine dynamische Datenstruktur, in der man gut Elemente suchen kann. Aus meiner Algorithmen und Datenstrukturen Vorlesung meine ich mich erinnern zu können, dass Bäume dafür mit Aufwand O(log n) gut geeigneten wären und auf jeden Fall besser als Liste und ähnliches mot O(n). In der java reference habe ich für Bäume aber nur das package javax.swing.tree gefunden und es würde mich doch sehr wundern, wenn man die Datenstruktur tree unter swing finden würde und google liefert mir nur tausend Beispielhafte Implementierungen eines Binärbaums.

Gibt es in Java bereits eine Klasse für Bäume oder eine andere Klasse, die man so verwenden kann (Beispiel wie bei PriorityQueue und Heap)?

Vielen Dank und einen schönen zweiten Feiertag

Edit: Richtig suchen ist hilfreich, in java.util findet man natürlich was. ALlerdings bin ich mir jetzt unsicher ob HashSet oder TreeSet besser ist. Eigentlich brauche ich ja keine Sortierung, ich will ja nur Suchen. Aber das Hashen bringt ja nur dann gute Performance, wenn die Hashfkt. die Elemente gut verteilt. Kann man das irgendwie beeinflussen oder kümmert sich java da selbstständig drum?

[javatar]

Ok, mittlerweile bin ich völlig verwirrt, also versuchen wir es mal umgekehrt.

In einer While-Schleife erzeuge ich einige Objekte. Diese haben eine ID, mit der dich sich logischerweise eindeutig identifizieren lassen, und andere Attribute, die dann eventuell geändert werden sollen. Es ist möglich, dass man sich mehrmals das selbe Objekt anguckt und nochmal ändert. Ansonsten passiert damit eignetlich nicht viel.

meine erste grobe Idee war:
1) prüfe, ob sich ein Objekt mit der aktuell betrachteten ID bereits in der Datanstruktur befindet.
1.1) Falls nein erzeugen und reinpacken
1.2) Falls ja das Objekt liefern
2) Attribute neu berechnen
3) Neues Objekt wieder in die Datenstruktur schmeißen

Könnt ihr mich "beraten" wie man das effizient machen kann?

[anda_skoa]

Die Basisdatenstruktur in Java ist Map, bzw Klassen, die das Map Interface implementieren.

Im Wesentlichen gibt es zwei Arten der Implementierung, HashMap und TreeMap. Letztere ist die, nach der du ursprünglich gesucht hast, also eine Abbildung (map), die als balanzierter Baum ausgeführt ist.

Wenn du ein Objekt in einer Map hast, brauchst du es ansich nicht nochmal neu hinzufügen wenn du es änderst, die Map hat nur eine Referenz des Objekts und zeigt daher immer auf den aktuellen Zustand.

Du könntest also in etwa so vorgehen


MyClass obj = map.get(id);

// wenn nicht vorhanden, erzeugen und hinzufügen
if (obj == null) {
obj = new MyClass();
map.put(id, obj);
}

// obj ändern


Ciao,
_

[javatar]

Ok, also eine Map und gar kein Set, das ist ja schonmal ein erster Schritt.
Nach dem Tree hatte ich ja nur gesucht, weil ich das als effizient Erinnerung hatte, da ich die sortierung aber eigentlich gar nicht brauche wäre eine HashMap ja interessanter oder? Vorrausgesetzt die Hash-Funktion verteilt die Objekte ordentlich, damit habe ich keine Erfahrung.

[anda_skoa]

Ein Set ist eine Menge, d.h. wenn du ein Set von deinen IDs hast, kannst du feststellen, ob du eine ID schon benutzt hast.
Aber sie ist keine Abbildung, daher kann man nicht mittels ID auf das eigentlichen Objekt schließen.

Wenn du einen der Standard Datentypen als ID verwendest, kannst du von einer relativ guten Hashfunktion ausgehen. Aber natürlich kommt es trotzdem immer auf die Werteverteilung an, ob der Hash degeneriert.

Ein Tree hast quasi garantierte obere Schranken, ist aber potentiell langsamer.

Nachdem aber hier beide das selbe Interface implementieren, lassen sie sich ja leicht gegeneinander austauschen. Also einfach erstmal mit HashMap versuchen.

Ciao,
_

[javatar]

Vielen Dank für die Aufklärung, ich werde das ganze dann mal mit einer Hashmap versuchen.