Sé que las implementaciones principales de STL map / set usan árboles negro-rojo. Mi pregunta es: ¿estas implementaciones también equilibran automáticamente el árbol al insertar / eliminar elementos?

De lo contrario, cuando los elementos se ordenan e insertan, siempre se agregarán al lugar más a la derecha. El peor costo de búsqueda es O (n).

Entonces, ¿el árbol negro-rojo se equilibra automáticamente?

3
Troskyvs 24 dic. 2016 a las 13:12

3 respuestas

La mejor respuesta

Eche un vistazo a insert y borrar std :: map operaciones.

Se garantiza que la peor complejidad para estas operaciones es logarítmica.

De hecho, no es importante qué tipo de árbol se utiliza para implementar un std :: map . Pero este árbol debe proporcionar la complejidad necesaria para insertar , borrar y algunas otras operaciones. Básicamente significa que el árbol debe estar equilibrado (y, por supuesto, equilibrarse automáticamente cuando se insertan o eliminan elementos).

Lo mismo es cierto para un std :: set .

2
Edgar Rokjān 24 dic. 2016 a las 11:52

Si. En los árboles Rojo-Negros después de cada inserción, algunos elementos del árbol se moverán a un nuevo lugar si el árbol no está equilibrado.

1
saeid zamani 24 dic. 2016 a las 10:49

Si. Los árboles rojo-negros realizan rotaciones de nodos para garantizar que el árbol permanezca equilibrado

3
stefaanv 24 dic. 2016 a las 11:00