¿Qué estructura de datos utiliza Map?

¿Qué es un mapa?

Antes de aprender la estructura de datos utilizada por un mapa, echemos un vistazo al mapa.

El mapa es la parte de la biblioteca STL que almacena pares de valores clave y no hay dos valores que tengan las mismas claves, pero las diferentes claves pueden almacenar valores similares. El mapa almacena claves ordenadas.

Estas son algunas funciones que usa el mapa con sus Complejidades de Tiempo:

• insert() – Complejidad de tiempo O (Log N)
• delete() – Complejidad de tiempo O (Registro N)
• erase() – Complejidad de tiempo O (Registro N)
• find() – Complejidad de tiempo O (Log N)

¿Qué estructura de datos utiliza Map?

Ahora, llegando al punto de qué estructura de datos utiliza el mapa. La implementación interna del mapa es un árbol binario autoequilibrado. En general, existen dos métodos para implementar un árbol binario autoequilibrado:

• Árbol rojo-negro y 
• Arboles AVL . 

Estos son los dos métodos pero 

Para la implementación interna del mapa utiliza Red-Black Tree. 

Para equilibrar el árbol después de una inserción/eliminación, ambos algoritmos utilizan la noción de rotaciones donde los Nodes del árbol se giran para realizar el reequilibrio. Mientras que en ambos algoritmos las operaciones de inserción/eliminación son O(log N) , en el caso de la rotación de reequilibrio del árbol rojo-negro es una operación O(1) , mientras que con AVL es una operación O(log N ), lo que hace que Red-Black Tree es más eficiente en este aspecto de la etapa de reequilibrio y una de las posibles razones por las que se usa más comúnmente.

¿Qué es el árbol rojo-negro?

Un árbol rojo-negro es una especie de á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) que se utiliza para garantizar que el árbol permanezca equilibrado durante las inserciones y eliminaciones

Para obtener más información sobre el árbol rojo-negro, consulte el artículo sobre » Árbol rojo-negro «.