Здравствуйте, samius, Вы писали:

PD>>Это уже игра в слова. Вставка в моем понимании и есть — взять дерево, добавить элемент и получить новое дерево (пусть мне кто-то скажет, что это прежнее дерево!). Но при этом не меняется истинный root, не меняются никакие ссылки (кроме точенчного изменения в месте вставки) и ничего не копируется — ни данные, ни управляющая информация).
S>Это побочный эффект императивной вставки.

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

PD>>Изменения по памяти — O(1). На то оно и дерево. А иначе я могу и упорядоченный массив взять, и он многое из того, что дерево позволяет (Log N поиск хотя бы), да только вставка в нем O(1) не пройдет ни по памяти, ни по времени. И именно за эти свойтсва я ту или иную структуру применяю или отвергаю в данной ситуации.

S>А я по другим свойствам. Но об алгоритмических оценках помню.

Вот именно. Они, вообще-то, не должны ни от языка, ни от среды ни от императивное vs функциональное зависеть не должны. Они таковы в силу природы вещей. Хотя испоритить их (структуры данных) неудачным алгоритмом или средой исполнения можно .