Descripción de TreeMaps

Question

esta es una pregunta clave acerca de los mapas de árbol. He leído la API de Java y otra documentación, pero todavía no tengo claro cómo funciona esto.

Según tengo entendido, un árbol en Java (o cualquier idioma) es una especie de árbol genealógico; donde ha decir:

Layer 1        OldestGuy  
Layer 2  OldGuy1  Oldguy2   OldGuy3  OldGuy4   OldGuy5 
Layer 3 Guy1 Guy2 Guy3 Guy4 Guy5 Guy6........ etc 

Cuando la capa 1 tiene 1 valor (es decir, un nodo central) y desde allí no puede haber cantidades arbitrarias de valores (o hombres) en cada capa posterior, y algunas de las "ramas" puede ser más largo que otros (por ejemplo podría ir OldestGuy -> OldGuy1 -> Guy1 & Guy2 ... Guyn mientras que al mismo tiempo otra rama es simplemente OldestGuy -> OldGuy4)

Con esta idea estoy tratando de agrego valores a un TreeMap en ubicaciones específicas de ramas específicas mientras hago conexiones específicas, pero todo lo que parece obtener es el mismo resultado que un HashMap.

(Parece que lo que quiero hacer requiere algo más que la TreeMap .... como la clave (o Capa (?) Sería la misma para varios valores diferentes)

Cualquier sugerencia/explicaciones serían fantástico porque me siento como si estuviese realmente ladrando el árbol equivocado con este.

He visto ejemplos de esto haciendo uso de Google .jar, (como un árbol genealógico), pero estoy tratando de entender esto ya que parece haber muchos conflictos entre TreeMap y Trees y cómo puede almacenar datos en ellos.

Answer 1

TreeMap es solo una implementación de Map que usa un árbol rojo-negro detrás de escena. Los detalles del árbol no están expuestos a usted, por lo que no puede almacenar elementos en ubicaciones arbitrarias.

En otras palabras, TreeMap no es una estructura de datos de árbol de propósito general. Si eso es lo que realmente quiere, tal vez eche un vistazo a esta pregunta sobre el desbordamiento de la pila: Java tree data-structure?.

Answer 2

Un Java TreeMap usa un árbol como una estructura de datos interna para obtener búsquedas e inserciones O (log n), pero no expone la estructura de árbol en su interfaz. Así que no hay forma de, por ejemplo, obtener un nodo de árbol y todos sus descendientes, o representar un árbol genealógico que lo use.

Answer 3

TreeMap es un Map (implementado a través de un árbol), no es un árbol (implementado a través de Map o de otro modo).

Answer 4

Creo que estás confundiendo dos cosas diferentes. Se ha implementado TreeMap como Árbol Rojo-Negro.
Según el documento Java:

Implementación de NavigableMap en árbol rojo-negro. El mapa está ordenado de acuerdo con el orden natural de sus claves, o por un Comparador proporcionado en el tiempo de creación del mapa, dependiendo de qué constructor se utiliza.

Esta implementación proporciona un costo de tiempo de registro (n) garantizado para las operaciones de containsKey, get, put y remove. Los algoritmos son adaptaciones de aquellos en Cormen, Leiserson, y la Introducción de Rivest a Algoritmos.

Así que, en esencia, si usted quiere tener un orden predecible de sus teclas que debe o bien dejar el TreeMap de pedir sus claves mediante el uso de ordenamiento natural o implementar la interfaz de Comparator mismo. Una vez más, desde el Javadoc:

Tenga en cuenta que el orden mantenido por un mapa de árbol, como cualquier mapa Ordenado, y si es o no se proporciona un elemento de comparación explícita, debe ser consistente con los iguales si este mapa ordenada es para implementar correctamente la interfaz de Mapa. (Consulte Comparable o Comparador para una definición precisa de consistente con iguales.) Esto es así porque la interfaz Mapa se define en términos de la operación igual, pero un mapa ordenado realiza todas las comparaciones de claves usando su compareTo (o compare) método, por lo que dos claves que se consideran iguales por este método son, desde el punto de vista del mapa ordenado, iguales. El comportamiento de un mapa ordenado es bien definido, incluso si su orden es inconsistente con los iguales; simplemente no cumple con el contrato general de la interfaz del Mapa.

Ahora, no está claro si desea colocar sus claves de la manera que mencioné (es decir, ordenamiento natural) o de otra manera (es decir, orden de inserción u otra cosa?).
Por ejemplo, si prefiere la orden de inserción, el LinkedHashMap podría ser mejor para su caso.
Si algo más es el caso, por favor especifíquelo:].

Answer 5

public class TreeMap<K,V> 
extends AbstractMap<K,V> 
implements NavigableMap<K,V>, Cloneable, Serializable 

• Mapa del árbol no utiliza hash para almacenar claves. Es uso Rojo-Negro árbol (árbol de búsqueda binaria de autoequilibrado).
• El TreeMap se ordena de acuerdo con el orden natural de sus claves. Tree Map siempre tendrá todos los elementos ordenados.
• El trabajo del mapa de árbol se basa en estructura de datos de árbol.
• Tree Map es no sincronizado y por lo tanto no es seguro.
• Tree Map en java no permiten la clave nula, pero permiten múltiples valores nulos.

Working of Tree Map se basa en la estructura de datos de árbol.

• Cada nodo tiene 3 referencias: PARENT, IZQUIERDA y DERECHA.
• elementos IZQUIERDOS siempre menos que el elemento principal.
• Los elementos DERECHOS siempre son más o menos iguales al elemento principal.