Funcionamiento interno de TreeMap en Java

La clase TreeMap es como HashMap . TreeMap almacena pares clave-valor. La principal diferencia es que TreeMap ordena la clave en orden ascendente. TreeMap se clasifica según el orden de sus claves, o por un comparador proporcionado en el momento de la creación del mapa, según el constructor que se utilice.

Requisito previo:

Repasemos los requisitos previos que incluyen principalmente constructores disponibles en el caso de TreeMap antes de seguir discutiendo 

1. TreeMap() Este constructor predeterminado construye un TreeMap vacío
2. TreeMap(Mapa mapa) Crea un TreeMap con las entradas de un mapa.
3. TreeMap(Comparator compare) Este es un constructor de argumentos y toma el objeto Comparator para construir un mapa vacío basado en un árbol. Se ordenará utilizando Comparator compare.
4. TreeMap(SortedMap sortedMap) Se puede inicializar como TreeMap con las entradas de sortedMap .

Ilustración:

Input  : a = ["Alice", 1], b = ["Bob", 2]
Output : TreeMap = {"Alice" = 1, "Bob" = 2}

Input  : a = [1, "First"], b = [2, "Second"], c = [3, "Third"]
Output : TreeMap = {1 = "First", 2 = "Second", 3 = "Third"}

Concepto: árboles rojos y negros 

Un árbol rojo-negro es un árbol de búsqueda binario autoequilibrado en el que cada Node tiene un bit adicional, y ese bit a menudo se interpreta como el color (rojo o negro). Estos colores se utilizan para garantizar que el árbol permanezca equilibrado durante las inserciones y eliminaciones. Aunque el equilibrio del árbol no es perfecto, es lo suficientemente bueno para reducir el tiempo de búsqueda y mantenerlo alrededor del tiempo O(log n), donde n es el número total de elementos en el árbol. Debe tenerse en cuenta que como cada Node requiere solo 1 bit de espacio para almacenar la información de color, estos tipos de árboles muestran una huella de memoria idéntica al árbol de búsqueda binario clásico (sin color). 

1. Como sugiere el nombre del algoritmo, el color de cada Node en el árbol es negro o rojo.
2. El Node raíz debe ser de color negro.
3. El Node rojo no puede tener un Node vecino de color rojo.
4. Todas las rutas desde el Node raíz hasta el nulo deben constar del mismo número de Nodes negros.

Las características anteriores conducen a que un Node posea ciertas propiedades que resultan de la siguiente manera:

1. Los elementos de la izquierda siempre son menores que el elemento principal.
2. El orden natural se calcula en la comparación lógica de los objetos.
3. Los elementos correctos siempre son mayores o iguales que el elemento principal.

Sintaxis: declarar un objeto de TreeMap o simplemente crear un TreeMap

Map<Key, Integer> treemap = new TreeMap<>();

Acercarse:

1. Crear un mapa de árbol.
2. Cree algunas entradas para entrar en el TreeMap.
3. Calcule el código hash de la clave {“key1”}. Se generará como 118.
4. Imprima el TreeMap usando for loop traversal.

Implementación: implementación de árboles rojo-negro para mostrar el funcionamiento interno de TreeMap

Ejemplo

// Java Program to show Internal Working
// of TreeMap in Java
 
// Importing Map and TreeMap classes
// from java.util package
import java.util.Map;
import java.util.TreeMap;
 
// Standard Comparable
public class Key implements Comparable<Key> {
 
    // Custom input
    final int data = 118;
    private String key;
 
    // Constructor of this class
    public Key(String key)
    {
        // Super keyword refers immediate parent class
        // object
        super();
 
        // This keyword is a reference variable
        // referring to current object
        this.key = key;
    }
 
    // Print Key method
    public String printKey() { return this.key; }
 
    // Override compareTo method
    @Override public int compareTo(Key obj)
    {
        return key.compareTo(obj.key);
    }
}
 
// Main Class
class GFG {
 
    // Main driver method
    public static void main(String[] args)
    {
        // Initialize TreeMap
        // Declaring object of String type
        Map<Key, String> treemap = new TreeMap<>();
 
        // Adding the elements in object of TreeMap
        // Custom inputs
        treemap.put(new Key("Key1"), "Alice");
        treemap.put(new Key("Key4"), "Zeya");
        treemap.put(new Key("Key3"), "Geek");
        treemap.put(new Key("Key2"), "Bob");
 
        // Iterate over object elements using for-each loop
        for (Map.Entry<Key, String> entry :
             treemap.entrySet())
 
            // Print elements in TreeMap object
            System.out.println(
                "[" + entry.getKey().printKey() + " = "
                + entry.getValue() + "]");
    }
}

// Java Program to show Internal Working
// of TreeMap in Java
 
// Importing Map and TreeMap classes
// from java.util package
import java.util.Map;
import java.util.TreeMap;
 
// Standard Comparable
public class Key implements Comparable<Key> {
 
    // Custom input
    final int data = 118;
    private String key;
 
    // Constructor of this class
    public Key(String key)
    {
        // Super keyword refers immediate parent class
        // object
        super();
 
        // This keyword is a reference variable
        // referring to current object
        this.key = key;
    }
 
    // Print Key method
    public String printKey() { return this.key; }
 
    // Override compareTo method
    @Override public int compareTo(Key obj)
    {
        return key.compareTo(obj.key);
    }
}
 
// Main Class
class GFG {
 
    // Main driver method
    public static void main(String[] args)
    {
        // Initialize TreeMap
        // Declaring object of String type
        Map<Key, String> treemap = new TreeMap<>();
 
        // Adding the elements in object of TreeMap
        // Custom inputs
        treemap.put(new Key("Key1"), "Alice");
        treemap.put(new Key("Key4"), "Zeya");
        treemap.put(new Key("Key3"), "Geek");
        treemap.put(new Key("Key2"), "Bob");
 
        // Iterate over object elements using for-each loop
        for (Map.Entry<Key, String> entry :
             treemap.entrySet())
 
            // Print elements in TreeMap object
            System.out.println(
                "[" + entry.getKey().printKey() + " = "
                + entry.getValue() + "]");
    }
}

La explicación de salida se representa pictóricamente para obtener el funcionamiento interno de los Nodes de TreeMap, cómo se genera la salida anterior para una mejor comprensión.

Nota: 

• El rendimiento de TreeMap es lento en comparación con HashMap y LinkedHashMap.
• La implementación del árbol proporciona un costo de tiempo de registro (n) garantizado para las operaciones containsKey() , get(), put() y remove().