Есть ли в STD :: map автоматический баланс

Я знаю, что основные реализации STL map / set используют черно-красные деревья.
Мой вопрос: эти реализации также автоматически сбалансировать дерево при вставке / удалении элементов?

Если нет, то когда элементы отсортированы и вставлены, он всегда будет добавлен в крайнее правое место. Наихудшая стоимость поиска — O (n).

Итак, автоматически ли самобалансируется черно-красное дерево?

3

Решение

Посмотрите на вставить а также стирать станд :: Карта операции.

Гарантируется, что наихудшая сложность для этих операций — логарифмическая.

На самом деле не важно, какой тип дерева используется для реализации станд :: Карта. Но это дерево должно обеспечить необходимую сложность для вставить, стирать и некоторые другие операции. По сути, это означает, что дерево должно быть сбалансировано (и, конечно, само балансировать, когда элементы вставляются или удаляются из).

То же самое верно для станд :: набор.

2

Другие решения

Да. Красно-черные деревья выполняют ротацию узлов, чтобы дерево оставалось сбалансированным

3

Да. в красно-черных деревьях после каждой вставки некоторые элементы в дереве будут перемещаться на новое место, если дерево не сбалансировано.

1