Как исключать элементы из сбалансированных деревьев?

vodnik2

Имеется упорядоченное бинарное почти сбалансированное (= глубины левого и правого поддеревьев любой вершины отличаются не более чем на 1) дерево.
Как исключить оттуда элемент, чтобы оно осталось почти сбалансированным, используя операции типа "вращение вокруг вершины"?
Разумеется, хочется, чтобы это было сделано за O(глубина дереева)=O(логарифм числа эелементов) операций.
Например, для вставки нового элемента в почти сбалансированное дерево на каждом уровне одним или двумя поворотами можно восстановить почти сбалансированность. К сожалению, удаление элемента задача не совсем обратная вставке, так как новый элемент всегда вставляется в лист дерева, а вот удалять можно и узлы.

electricbird

мб глянуть надо глянуть в Кнута? тем более, что он есть в сети

Ktitiss

Да, тут тебе одним-двумя поворотами не обойтись. Если ты удалил вершину X у которой были дети Y и Z, на место X поставил Z, а Y приткнул где-нибудь в поддереве Z, то тебе придется идти вверх по дереву от Z до папы Y и в каждой вершине если нарушена почти-сбалансированность – поворачивать.

vodnik2

Вот-вот, в этом-то и проблема.
На самом деле, я лопухнулся и вопрос снят, ибо правильно для почти сбалансированных деревьев сортируемые элементы (то есть те, которые вставляются или удаляются) иметь в только листьях. Тогда и проблем с удалением не будет.
Блин, целый день ушел, чтобы это понять
Пришлось сильно прогу переписывать
Зато с таким подходом все заработало
Оставить комментарий
Имя или ник:
Комментарий: