¿Qué es un Treemap en Java??

El valor de un nodo en un árbol se llama clave. Un árbol binario es un árbol, donde cada nodo no tiene más de dos hijos. Un árbol de búsqueda binario (BST) es un árbol, donde para cada nodo, el niño derecho es mayor o igual al niño izquierdo. Esto lleva a que la mitad derecha del árbol tenga valores generalmente mayores que los de la mitad izquierda en cada nivel. Esto significa que un árbol de búsqueda binario está parcialmente ordenado (un tipo de clasificación incompleta). Se puede mantener un BST en una estructura similar a una matriz, siendo el nodo raíz el primer valor.

Se puede convertir un árbol binario en diferentes árboles de equilibrio a sí mismo con diferentes conjuntos de condiciones adicionales, como el árbol AVL y el árbol rojo-negro.

El Treemap en Java es un árbol rojo-negro. Sin embargo, cada nodo consiste en una clave y un valor correspondiente (par de clave/valor) en lugar de solo una clave. Cada par de clave/valor sería un elemento en una estructura de matriz. Este artículo explica cómo usar un Treemap en Java, comenzando con un árbol de búsqueda binario, seguido por el árbol rojo-negro, y luego el Java Treemap.

Contenido del artículo

• Árbol de búsqueda binario
• Árbol rojo-negro
• Pares de clave/valor para Java Treemap
• Construcción de Java Treemap
• Métodos Java Treemap
• Conclusión

Árbol de búsqueda binario

El siguiente es un ejemplo de un árbol de búsqueda binario:

Cada nodo tiene una clave. La clave (valor) para el nodo raíz es 8. El niño izquierdo tiene 3 años y el niño derecho es 10 (10> = 3). Se puede ver que para cualquier nodo que tenga dos hijos, el niño derecho es mayor o igual al niño izquierdo. Además, la mitad derecha del árbol tiene valores mayores que los de la mitad izquierda del árbol para cada nivel.

Todos los valores del árbol anterior se pueden colocar en una matriz, de la siguiente manera:

8, 3, 10, 1, 6 ,,,, 14, 4, 7 ,,,,,,, 13, ,

Observe que la matriz (árbol) comienza a las 8; desciende a 3, luego se eleva a más de 8 a las 10; desciende a 1, se eleva a 6, luego tiene nils, hasta 14; desciende a 4; sube a 7; Nils de nuevo; luego 13 y el último nulo.

8 es el primer valor en el índice 0. Es el nodo raíz (padre raíz). No es necesariamente el mayor valor entre todos los valores. Su primer hijo (3) está en el índice 1, cuyo índice es igual a 2 (0) + 1, donde 0 es el índice del padre. Su segundo hijo (10) está en el índice 2, que es igual a 2 (0) + 2, donde 0 es el índice del padre.

3 está en el índice 1. Es un padre. Su primer hijo (1) está en el índice 3, que es igual a 2 (1) + 1, donde 1 es el índice del padre. Su segundo hijo (6) está en el índice 4, que es igual a 2 (1) + 2, donde 1 es el índice del padre.

6 está en el índice 4. Es un padre. Su primer hijo (4) está en el índice 9, que es igual a 2 (4) + 1, donde 4 es el índice del padre. Su segundo hijo (7) está en el índice 10, que es igual a 2 (4) + 2, donde 4 es el índice del padre.

10 está en el índice 3. Es un padre. No tiene el primer niño (izquierda), que se suponía que debía estar en el índice 7, que es igual a 2 (3) + 1, donde 3 es el índice de los padres. Su segundo hijo (14) está en el índice 8, que es igual a 2 (3) + 2, donde 3 es el índice del padre.

14 está en el índice 8. Es un padre. Su primer hijo (13) está en el índice 17, que es igual a 2 (8) + 1, donde 8 es el índice del padre. No tiene derecho (segundo) niño, que se suponía que debía estar en el índice 18, que es igual a 2 (8) + 2, donde 8 es el índice de los padres.

En general, a medida que el recuento de índice comienza a partir de 0. Deje que represente el índice de un padre de la matriz; Y así, la izquierda (primero) hijo de un padre en el índice I está en el índice 2i + 1; y su niño (segundo) niño, está en el índice 2i + 2. Algunas celdas en la matriz pueden estar vacías; No deben tener valores.

Árbol rojo-negro

Un árbol rojo-negro es un árbol de búsqueda binario, que está equilibrado. El siguiente es un árbol rojo-negro ya equilibrado:

Un árbol equilibrado es un árbol con una altura corta. Las posiciones del nodo se cambian y marcan con colores rojos y azules para tener la altura del árbol más corta posible en su desarrollo.

Usando las fórmulas, 2i + 1 y 2i + 2, los valores se pueden colocar en una estructura similar a una matriz de la siguiente manera:

13, 8, 17, 1, 11, 15, 25, 6 ,,,,,,22, 27

Observe que la matriz comienza en 13, desciende a 8 y luego se eleva a 17. Luego desciende más allá de 8 a 1 y luego se eleva a 11, luego 15, luego 25; de la cual hay un nulo, y luego desciende a 6. Nils siguen antes del 22 y 27.

La matriz de un árbol equilibrado, como el árbol rojo-negro de arriba, tiene menos nulos que su árbol de búsqueda binario correspondiente que no está equilibrado. La longitud de la matriz de un árbol equilibrado es más corta que el árbol correspondiente que no está equilibrado.

Un árbol rojo-negro es un árbol parcialmente ordenado.

Pares de clave/valor para Java Treemap

El árbol rojo-negro anterior solo tiene claves como valores de nodo. Cada clave entera se puede dar un valor de cadena correspondiente. La siguiente lista tiene las mismas claves con los valores correspondientes:

13/trece, 8/ocho, 17/diecisiete, 1/uno, 11/once, 15/quince, 25/veinticinco, 6/seis, 22/veintidós, 27/veintisiete

Estos son pares de clave/valor adecuados para un Java Treemap. Cada clave se asignará a su valor correspondiente. Un par de clave/valor se llama entrada de mapa en Java. Para el Java Treemap, la disposición de los nodos se realiza mediante claves (no valores de los pares de clave/valor). Cada clave se asigna a su valor.

Construcción de Java Treemap

En Java, Treemap es una clase en Java.utilizar.* Paquete, que debe importarse. Esta clase tiene cuatro constructores, y dos constructores se ilustran en este artículo.

Treemap público ()

Esto construye un treemap vacío. El siguiente segmento de código ilustra esto:

Treemap tm = nuevo treemap();
TM.poner (13, "trece"); TM.poner (8, "ocho"); TM.poner (17, "diecisiete"); TM.poner (1, "uno");
TM.poner (11, "once"); TM.poner (15, "quince"); TM.poner (25, "Veinticinco"); TM.poner (6, "seis");
TM.poner (22, "Veintidós"); TM.poner (27, "Veintisiete");

El método PUT () incluye pares de clave/valor para el Treemap. Después de todo esto, el Treemap se equilibra internamente.

Treemap público (mapa m)

Este método de constructor crea un mapa de otro mapa ya creado, como en el siguiente segmento de código:

Treemap tm = nuevo treemap();
TM.poner (13, "trece"); TM.poner (8, "ocho"); TM.poner (17, "diecisiete"); TM.poner (1, "uno");
TM.poner (11, "once"); TM.poner (15, "quince"); TM.poner (25, "Veinticinco"); TM.poner (6, "seis");
TM.poner (22, "Veintidós"); TM.poner (27, "Veintisiete");
Treemap tm1 = nuevo treemap(tm);

TM1 se crea a partir de TM. Después de todo esto, ambas treemaps se equilibraron internamente; con el primero equilibrado primero. El equilibrio se lleva a cabo ya que las teclas incluyen pares.

Métodos Java Treemap

Public V Put (K Key, V valor)

Estrictamente hablando, el método Put () no agrega un par de clave/valor. Asocia un valor particular a una clave particular. Si la clave ya existía en el Treemap con un valor diferente, el valor se reemplaza con el nuevo. Este método devuelve el valor anterior o nulo si no hubo un valor antiguo. El uso de este método se ha demostrado anteriormente.

Public int size ()

Este método devuelve el número de asignaciones de clave/valor (pares) en el treemap. El siguiente segmento de código muestra cómo usarlo:

int it = tm.tamaño();
Sistema.afuera.println (it);

La salida es 10, lo que indica que hay 10 pares de clave/valor en este objeto Treemap.

Public v Get (clave de objeto)

Este método devuelve el valor correspondiente al argumento, que es la clave. Devuelve nulo si la clave no existe. El siguiente código ilustra esto para el par de clave/valor: 11/"once", y para la clave, 40, que no existe:

Cadena val = tm.obtener (11); Cadena str = tm.obtener (40);
Sistema.afuera.imprimir (val + ","); Sistema.afuera.imprimir (str + "");
Sistema.afuera.println ();

La salida es:

once, nulo

Public Set KeySet ()

Este método devuelve una vista de ajuste de las teclas que están en el Treemap. Para mostrar las teclas, el iterador debe usarse. El siguiente segmento de código para el Treemap anterior ilustra esto:

Colocar ST = TM.juego de llaves();
Iterador iter = st.iterador ();
mientras (iter.HasNext ())
Sistema.afuera.imprimir (iter.next () + ",");

Sistema.afuera.println ();

La salida es:

1, 6, 8, 11, 13, 15, 17, 22, 25, 27,

La lista de devolución está completamente ordenada (ascendente), aunque el Treemap tiene una clasificación interna parcial.

Valores de colección pública ()

Esto devuelve la vista de colección (lista) de todos los valores en el treemap, sin las claves. Para mostrar los valores, el iterador debe usarse. El siguiente segmento de código para el Treemap anterior ilustra esto:

Recopilación col = tm.valores();
Iterador iter = col.iterador ();
mientras (iter.HasNext ())
Sistema.afuera.imprimir (iter.next () + ",");

Sistema.afuera.println ();

La salida es:

uno, seis, ocho, once, trece, quince, diecisiete, veintidós, veinticinco, veintisiete,

Los valores se han mostrado en función de sus teclas ordenadas completas (ascendentes), aunque el Treemap tiene una clasificación parcial internamente.

Conjunto público EntrySet ()

Esto devuelve un conjunto de pares de clave/valor. Para mostrar las teclas y sus valores correspondientes, el iterador debe usarse. El siguiente segmento de código para el treemap anterior ilustra esto:

Colocar> pares = tm.EntrySet ();
Iterador> iter = pares.iterador ();
mientras (iter.HasNext ())
Mapa.Entrada etry = iter.próximo();
int en = etry.obtener la clave(); Cadena str = etry.getValue ();
Sistema.afuera.println (en + "=>" + str);

La salida es:

1 => uno
6 => seis
8 => ocho
11 => once
13 => Trece
15 => quince
17 => diecisiete
22 => veintidós
25 => Veinticinco
27 => Veintisiete

Los pares se han mostrado en función de sus teclas ordenadas completas (ascendentes), aunque el Treemap tiene una clasificación parcial internamente.

Conclusión

En Java, un Treemap es un árbol rojo-negro, que es un árbol de búsqueda binario de equilibrio. Los métodos comúnmente utilizados y la construcción de Java Treemap se han discutido en este artículo. Esperamos que haya encontrado esta información útil. Echa un vistazo a los otros artículos de Sugerencia de Linux para obtener más consejos y tutoriales.