Welche Java-Datenstruktur/Bibliothek verwenden Sie für einen Baum?

Ich habe eine Regionshierarchie (denke State, District, Taluk, etc), die ich mit einem Baum darstellen muss. Ich sah ein paar Implementationen eines Baumes in der Öffentlichkeit, aber nicht sicher, wie gut sie sind und wie gut sie gepflegt werden. Apache Collections hat keine von denen, die die Google-Sammlungen machen. Ich frage mich, ob einer von euch mich auf eine Implementierung eines Baumes in Java (mit Generika) hinweisen kann.Welche Java-Datenstruktur/Bibliothek verwenden Sie für einen Baum?

Danke,

aktualisieren ich für einen Baum Datenstruktur suchen, vorzugsweise implementiert Generics mit: gut getestet.

Quelle

2010-07-12 anjanb

Ich fühle für Sie, niemand ist tatsächlich Ihre Frage zu beantworten. –

Die Implementierung eines Stammbaums mit Generics ist ziemlich einfach, warum nicht selbst ausprobieren? Wenn Sie mit Generics nicht vertraut sind, können Sie versuchen, einen Baum zu deklarieren, der Elemente enthält, die eine Schnittstelle implementieren, und dann einfach all Ihre verschiedenen Regions-Elemente implementieren lassen.

Quelle

2010-07-12 16:40:02 TMN

Ich habe Bäume schon vor langer Zeit mehrfach in C/C++ implementiert. Wenn es etwas gibt, das ich wiederverwenden könnte, würde ich lieber etwas getestetes und getestetes Gerät verwenden! – anjanb

Ein einfacher Baum ist einfach zu implementieren. Aber ernste Bäume erfordern ein gewisses Gleichgewicht (z. B. rot-schwarze Bäume). Diese brauchen Zeit, um richtig und effizient zu werden. Zum Beispiel, von dem, woran ich mich erinnere, gibt es 7 verschiedene Rotationsfälle für RB-Bäume. –

Wenn Sie einen RB-Baum neu ausbalancieren, sind Sie an der Ordnungseigenschaft des Baums interessiert, nicht an den strukturellen Eigenschaften (Eltern, Kinder). Wenn das der Fall ist, dann hat Java absolut TreeSet, das genau das tut, überprüfen Sie die Bibliotheken. Wenn Sie möchten, dass eine "Baumstruktur" Eltern/Kind-Beziehungen verfolgt, ist die Implementierung trivial und Ihr Einwand macht keinen Sinn. –

Meinst du ein Tree Widget oder eine baumähnliche Datenstruktur? Wenn Sie über ein Tree-Widget sprechen, hat Swing eine Implementierung.

JTree

Quelle

2010-07-12 16:41:11 Roman

danke. Ich meinte eine Baumstruktur. – anjanb

Was Sie beschreiben, ist viel mehr wie ein Document Object Model (DOM). Normalerweise, wenn Leute auf eine "Baum" -Datenstruktur verweisen, sprechen sie von einem ausgeglichenen Binärbaum (wie ein Rot-Schwarz-Baum, der sicherlich in der Java-Sammlungsbibliothek existiert). Aber diese Arten von Bäumen sind nur für schnelle In-Order-Einfügungen und Nachschlagevorgänge.

Jedenfalls, wenn Leute ein DOM benutzen, lesen oder schreiben sie XML, aber es gibt keinen Grund, dass Sie kein DOM für Ihre eigenen willkürlichen hierarchischen Daten verwenden könnten. Selbst wenn Sie es nie in XML beibehalten.

Quelle

2010-07-12 16:46:28 benjismith

DOM. Wie teuer ist DOM, wenn Sie es NICHT für XML verwenden? – anjanb

Ich weiß es nicht wirklich, aber ich kann über ein paar Dinge spekulieren ...Der Grund, warum DOM als teures XML-Parsing-Verfahren betrachtet wird, ist, dass Sie die gesamte XML-Datei analysieren und im Speicher behalten müssen, anstatt das XML zu scannen und SAX-Ereignisse auszulösen. Aber in Ihrem Fall brauchen Sie sowieso das gesamte Dokument im Speicher, also würde ich nicht denken, dass eine DOM-Implementierung viel teurer wäre als jede benutzerdefinierte Datenstruktur, die Sie selbst erstellen könnten. (Und natürlich werden Sie die I/O-Kosten nicht bezahlen.) Sie müssen wiederum mit der spezifischen Semantik von XML in Ihrem eigenen Baummodell leben. – benjismith

Würde so etwas wie http://www.java-tips.org/java-se-tips/java.lang/red-black-tree-implementation-in-java.html funktionieren?

Auch, wie wäre es mit der java.util.TreeMap Quelle aus dem OpenJDK zu starten? http://download.java.net/openjdk/jdk7/

Quelle

2010-07-12 22:20:00

Diese Implementierungen sind für binäre Bäume. Kann jeder Staat nur zwei Bezirke haben, und jeder Bezirk nur zwei Taluks? Wenn ja, dann könnten diese funktionieren. Wenn Sie jedoch mehr als zwei Instanzen jeder Ebene in der Hierarchie unterbringen müssen (und ich vermute, dass Sie das tun), sollten Sie Ihre eigenen Rollen erstellen. Ich habe das vor ein paar Wochen für ein XML-Parsing getan, und ich brauchte nur ein paar Stunden, um es zu entwerfen, zu testen, zu schreiben und zu dokumentieren. Ich kann den Code nicht teilen (es ist sowieso in C#), aber ich könnte das Design teilen, wenn du nicht selbst etwas aufarbeiten willst. – TMN

Dies ist das RB-Tree-Beispiel, das zuerst in Google angezeigt wird, wenn Sie nach einer Java-Implementierung eines RB-Baums suchen. Aber es gibt keine Komponententests usw., und es ist unvollständig: Die Entfernungsoperation ist nicht implementiert, und ich kann sehen, warum (angesichts ihrer Komplexität für RB-Bäume). –

Auschecken DefaultMutableTreeNode. Es ist nicht generisch, aber ansonsten scheint die Rechnung zu passen. Obwohl es im Paket javax.swing enthalten ist, hängt es nicht von AWT- oder Swing-Klassen ab. Tatsächlich hat der Quellcode tatsächlich den Kommentar // ISSUE: this class depends on nothing in AWT -- move to java.util?

Quelle

2010-10-14 12:25:28 Mark

Welche Java-Datenstruktur/Bibliothek verwenden Sie für einen Baum?

Antwort

Verwandte Themen