Отменить вставку в дерево AVL: максимально возможная временная сложность?

Действие отмены можно выполнить за время O(1), но на самом деле вам придется изменить способ вставки узла.

Мы знаем кое-что о последнем вставленном узле в стандартном дереве AVL:

• Это лист. Даже если вставка привела к одному или нескольким поворотам, эти повороты никогда не добавит дочерний элемент к вновь вставленному узлу.

• Его можно удалить без вращений (даже если в момент установки были применены вращения).

• Но может случиться так, что вставка повлечет за собой изменение коэффициента балансировки вдоль всех узлов на пути от корня к вставленному узлу (в худшем случае), поэтому нам все равно придется вернуть эти коэффициенты балансировки, если мы выполним операцию отмены.

Хотя первые два пункта намекают на операцию отмены O(1), последний пункт означает, что у нас все еще есть худший случай O(log𝑛).

Из-за этого последнего «препятствия» я бы предложил следующий подход:

• При вставке не выполняйте для него никаких вращений и не адаптируйте для него какие-либо коэффициенты баланса. Отложите эти действия по балансировке до тех пор, пока вы не выполните еще одну вставку или удаление, а затем сначала выполните отложенную ребалансировку (если таковая имеется), и только затем выполните следующее действие (таким же образом, когда это вставка). Это означает, что вы добавляете временную сложность O(log𝑛) для наихудшего случая к действию, которое само по себе также равно O(log𝑛) в худшем случае, но O(log𝑛 + log𝑛) по-прежнему равно O(log𝑛), поэтому мы можем выполнить это отложенное действие. ребалансировка без влияния на временную сложность самого действия (следующая вставка/удаление).

• При вставке помните, куда вы его вставили (т. е. помните ссылку на родительский узел, если таковая имеется). Если вы уже запомнили точку вставки (для возможной предыдущей вставки), перезапишите эту информацию.

• При удалении удалите информацию, упомянутую в пункте выше, чтобы она не использовалась для последующей операции отмены, что недопустимо).

• Теперь отменить операцию очень просто: подтвердите, что последним действием была вставка, а затем просто удалите вставленный узел. Поскольку мы отложили любые ротации и расчет коэффициентов баланса, делать больше нечего. Теперь это операция O(1).

• Когда вы ищете узел, и это узел, который был вставлен с помощью самого последнего действия, вам потенциально придется пройти еще один узел, чем вам пришлось бы сделать, если бы дерево было правильно перебалансировано. Но это не влияет на временную сложность операции поиска, поскольку O(log𝑛 + 1) = O(log𝑛).

Вывод: с помощью этого типа «отложенной перебалансировки» вы можете реализовать отмену со временной сложностью O (1).