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

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

S>>Здравствуйте, Pavel Dvorkin, Вы писали:

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

S>>>>Вставка есть как минимум изменяющая исходное дерево и неизменяющая.

PD>>>Вставка куда бы то ни было не может не изменять. Если не согласен — как тогда вообще изменить-то ?
S>>Дык и не надо менять-то. Цель не в том чтобыизменить дерево, а в том, чтобы получить дерево, которое бы содержало все элементы исходного и добавляемый.

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

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

S>>В моем случае перень не заметит разницы даже с секундомером.

PD>Значит, для твоих задач это действительно не важно.
действительно.