Что будет, если добавлять элементы в TreeSet по возрастанию

TreeSet будет работать корректно и эффективно, потому что в его основе лежит красно-черное дерево — самобалансирующаяся структура данных. Даже при последовательной вставке отсортированных элементов дерево автоматически выполняет ротации и перекрашивание узлов, чтобы поддерживать баланс.

В отличие от обычного бинарного дерева поиска (которое выродилось бы в список при последовательной вставке), красно-черное дерево гарантирует, что высота не превысит 2 * log2(N + 1). Поэтому все операции (add, remove, contains) остаются O(log N) независимо от порядка вставки.

На собеседовании: ответ — дерево самобалансируется. Покажите, что знаете, зачем нужна самобалансировка и почему обычное BST деградирует при упорядоченной вставке.