Я знаю, что основные реализации STL map / set используют черно-красные деревья.
Мой вопрос: эти реализации также автоматически сбалансировать дерево при вставке / удалении элементов?
Если нет, то когда элементы отсортированы и вставлены, он всегда будет добавлен в крайнее правое место. Наихудшая стоимость поиска — O (n).
Итак, автоматически ли самобалансируется черно-красное дерево?
Посмотрите на вставить а также стирать станд :: Карта операции.
Гарантируется, что наихудшая сложность для этих операций — логарифмическая.
На самом деле не важно, какой тип дерева используется для реализации станд :: Карта. Но это дерево должно обеспечить необходимую сложность для вставить, стирать и некоторые другие операции. По сути, это означает, что дерево должно быть сбалансировано (и, конечно, само балансировать, когда элементы вставляются или удаляются из).
То же самое верно для станд :: набор.
Да. Красно-черные деревья выполняют ротацию узлов, чтобы дерево оставалось сбалансированным
Да. в красно-черных деревьях после каждой вставки некоторые элементы в дереве будут перемещаться на новое место, если дерево не сбалансировано.