Quale infrastruttura/libreria java si utilizza per un albero

Ho una gerarchia di regioni (think State, District, Taluk, ecc.) Che devo rappresentare utilizzando un albero. Ho visto alcune implementazioni di un albero nel pubblico dominio, ma non sono sicuro di quanto siano brave e quanto bene siano mantenute. Le raccolte Apache non hanno uno di quei NOR che fanno le raccolte di google. Mi chiedo se qualcuno di voi possa indicarmi un'implementazione di un albero in Java (con generici).Quale infrastruttura/libreria java si utilizza per un albero

Grazie,

Aggiornamento Sto cercando un datastructure albero, preferibilmente implementato utilizzando Generics: ben collaudati.

fonte

2010-07-12 anjanb

Mi sento per te, nessuno risponde effettivamente alla tua domanda. –

L'implementazione di un albero utilizzando i generici è piuttosto semplice, perché non provarlo da soli? Se non ti senti a tuo agio con i generici, puoi provare a dichiarare un albero che contiene elementi che implementano un'interfaccia, quindi basta che tutti i vari elementi della tua regione implementino tale interfaccia.

fonte

2010-07-12 16:40:02 TMN

Ho implementato gli alberi più volte in C/C++ molto tempo fa. Se potessi riutilizzare qualcosa, preferirei usare un'unità testata e testata nel tempo! – anjanb

Un albero base è facile da implementare. Ma gli alberi seri richiedono un certo riequilibrio (ad esempio alberi rosso-neri). Coloro hanno bisogno di tempo per essere giusti ed efficienti. Ad esempio, da quello che ricordo, ci sono 7 diversi casi di rotazione per gli alberi RB. –

Se riequilibri un albero RB, sei interessato alla proprietà dell'ordine dell'albero, non alle qualità strutturali (genitore, figli). Se è così, allora Java ha TreeSet che fa esattamente questo, controlla le librerie. Se si desidera una "struttura ad albero" per tenere traccia delle relazioni genitore/figlio rispetto all'implementazione è banale e la tua obiezione non ha senso. –

Intendi un Tree Widget o una struttura dati ad albero? Se stai parlando di un widget Albero, Swing ha un'implementazione.

JTree

fonte

2010-07-12 16:41:11 Roman

grazie. Intendevo un Datastructure Tree. – anjanb

Quello che stai descrivendo è molto più simile a un Document Object Model (DOM). Di solito quando le persone si riferiscono a una struttura dati "Albero", stanno parlando di un albero binario bilanciato (come un albero rosso-nero, che certamente esiste nella libreria delle collezioni Java). Ma questi tipi di alberi sono solo per veloci inserimenti e ricerche in ordine.

Comunque, la maggior parte delle volte, quando le persone usano un DOM, stanno leggendo o scrivendo XML, ma non c'è ragione per cui non si possa usare un DOM per i propri dati gerarchici arbitrari. Anche se non lo si persiste mai in XML.

fonte

2010-07-12 16:46:28 benjismith

DOM. quanto è costoso DOM quando NON lo stai usando per XML? – anjanb

Non lo so, ma posso speculare su alcune cose ...Il motivo per cui DOM è considerato una costosa tecnica di analisi XML è che devi analizzare l'intero file XML e tenerlo in memoria, piuttosto che scansionare l'XML e attivare gli eventi SAX. Ma nel tuo caso, hai comunque bisogno dell'intero documento in memoria, quindi non penserei che un'implementazione DOM sarebbe molto più costosa di qualsiasi altra struttura di dati personalizzata che potresti modificare. (E ovviamente, non pagherete il costo di I/O.) Quindi, di nuovo, dovrete convivere con la semantica specifica di XML nel vostro modello ad albero. – benjismith

Qualcosa come questo http://www.java-tips.org/java-se-tips/java.lang/red-black-tree-implementation-in-java.html funziona?

Inoltre, che ne dici di iniziare con il sorgente java.util.TreeMap da OpenJDK? http://download.java.net/openjdk/jdk7/

fonte

2010-07-12 22:20:00

Queste implementazioni sono per alberi binari. Ogni stato può avere solo due distretti e ogni distretto ha solo due taloghi? Se è così, allora quelli potrebbero funzionare. Se hai bisogno di ospitare più di due istanze di ogni livello nella gerarchia, però (e suppongo che tu lo faccia), allora dovrai eseguire il rollover. L'ho fatto un paio di settimane fa per un parsing XML che stavo facendo, e mi ci sono voluti solo un paio d'ore per farlo progettato, testato, scritto e documentato. Non posso condividere il codice (è comunque in C#), ma potrei condividere il progetto se non vuoi elaborare qualcosa da solo. – TMN

Questo è l'esempio di albero RB che appare per primo in google se si cerca un'implementazione Java di un albero RB. Ma non ci sono test unitari ecc. Ed è incompleto: l'operazione di rimozione non è implementata, e posso capire perché (data la sua complessità per gli alberi RB). –

Check out DefaultMutableTreeNode. Non è generico, ma per il resto sembra adattarsi al conto. Anche se si trova nel pacchetto javax.swing, non dipende da alcuna classe AWT o Swing. In effetti, il codice sorgente ha effettivamente il commento // ISSUE: this class depends on nothing in AWT -- move to java.util?

fonte

2010-10-14 12:25:28 Mark

Quale infrastruttura/libreria java si utilizza per un albero

risposta

Problemi correlati