Qué estructura/biblioteca de datos Java utilizas para un árbol

Tengo una Jerarquía de regiones (piense en el estado, el distrito, Taluk, etc.) que necesito representar usando un árbol. Vi algunas implementaciones de un árbol en el dominio público PERO no estoy seguro de qué tan buenas son y qué tan bien se mantienen. Las Colecciones de Apache no tienen una de esas NI tampoco las colecciones de google. Me pregunto si alguno de ustedes puede indicarme una implementación de un Árbol en Java (con genéricos).Qué estructura/biblioteca de datos Java utilizas para un árbol

Gracias,

actualización Busco a una estructura de datos de árbol, preferiblemente implementada utilizando los genéricos: bien probados.

Fuente

2010-07-12 anjanb

Lo siento por usted, en realidad nadie está respondiendo su pregunta. –

Implementar un árbol usando genéricos es bastante simple, ¿por qué no intentarlo usted mismo? Si no te sientes cómodo con los genéricos, puedes intentar declarar un árbol que contenga elementos que implementen una interfaz, luego simplemente haz que todos tus diversos elementos de la región implementen esa interfaz.

Fuente

2010-07-12 16:40:02 TMN

He implementado árboles varias veces en C/C++ hace mucho tiempo. Si hubiera algo que pudiera reutilizar, ¡preferiría usar algo probado y probado a tiempo! – anjanb

Un árbol básico es fácil de implementar. Pero los árboles serios requieren cierto reequilibrio (por ejemplo, árboles Rojo-Negros). Ésos toman tiempo para ser correctos y eficientes. Por ejemplo, por lo que recuerdo, hay 7 casos de rotación diferentes para árboles RB. –

Si vuelve a equilibrar un árbol RB, está interesado en la propiedad de pedido del árbol, no en las cualidades estructurales (padres, hijos). Si ese es el caso, entonces Java tiene absolutamente TreeSet que hace exactamente eso, verifica las bibliotecas. Si desea una "estructura de árbol" para rastrear las relaciones entre padres e hijos, la implementación es trivial y su objeción no tiene sentido. –

¿Te refieres a un widget de árbol o una estructura de datos tipo árbol? Si está hablando de un widget Tree, entonces Swing tiene una implementación.

JTree

Fuente

2010-07-12 16:41:11 Roman

gracias. Quise decir una estructura de árbol. – anjanb

Lo que usted describe es mucho más como un Document Object Model (DOM). Por lo general, cuando las personas se refieren a una estructura de datos "Árbol", están hablando de un árbol binario equilibrado (como un árbol rojo-negro, que ciertamente existe en la biblioteca de colecciones de Java). Pero ese tipo de árboles son solo para inserciones y búsquedas rápidas en orden.

De todos modos, la mayoría de las veces, cuando las personas usan un DOM, están leyendo o escribiendo XML, pero no hay razón por la que no pueda usar un DOM para sus propios datos jerárquicos arbitrarios. Incluso si nunca lo persiste en XML.

Fuente

2010-07-12 16:46:28 benjismith

DOM. ¿Qué tan caro es DOM cuando NO lo está utilizando para XML? – anjanb

Realmente no lo sé, pero puedo especular sobre algunas cosas ...La razón por la que DOM se considera una costosa técnica de análisis XML es que debe analizar todo el archivo XML y mantenerlo en la memoria, en lugar de escanearlo a través del XML y activar eventos SAX. Pero en su caso, necesita todo el documento en la memoria de todos modos, por lo que no creo que una implementación DOM sería mucho más costosa que cualquier estructura de datos personalizada que pueda ejecutar. (Y, por supuesto, no pagará el costo de E/S). De nuevo, tendrá que vivir con la semántica específica de XML en su propio modelo de árbol. – benjismith

¿Algo así como http://www.java-tips.org/java-se-tips/java.lang/red-black-tree-implementation-in-java.html funciona?

Además, ¿qué tal comenzar con la fuente java.util.TreeMap desde OpenJDK? http://download.java.net/openjdk/jdk7/

Fuente

2010-07-12 22:20:00

Esas implementaciones son para árboles binarios. ¿Puede cada estado solo tener dos distritos, y cada distrito solo dos taluks? Si es así, entonces esos podrían funcionar. Sin embargo, si necesita acomodar más de dos instancias de cada nivel en la jerarquía (y supongo que lo hará), querrá implementar la suya propia. Lo hice hace un par de semanas para analizar algunos XML que estaba haciendo, y solo me llevó un par de horas diseñarlo, probarlo, escribirlo y documentarlo. No puedo compartir el código (está en C# de todos modos), pero podría compartir el diseño si no quieres trabajar por tu cuenta. – TMN

Este es el ejemplo del árbol RB que aparece primero en google si busca una implementación Java de un árbol RB. Pero no hay pruebas unitarias, etc., y está incompleto: la operación de eliminación no está implementada, y puedo ver por qué (dada su complejidad para los árboles RB). –

Echa un vistazo DefaultMutableTreeNode. No es genérico, pero de lo contrario parece ajustarse a la factura. Aunque está en el paquete javax.swing, no depende de ninguna clase AWT o Swing. De hecho, el código fuente en realidad tiene el comentario // ISSUE: this class depends on nothing in AWT -- move to java.util?

Fuente

2010-10-14 12:25:28 Mark

Qué estructura/biblioteca de datos Java utilizas para un árbol

Respuesta

Cuestiones relacionadas