Я пытался думать об этой программе последние несколько дней. Был бы признателен за любое мнение.
Гипотетически, скажем, у меня есть стек , в котором есть все последние действия, которые были выполнены с указанным c AVL-деревом. (Включая указатели на все узлы)
Есть 2 вида действий, которые я хочу иметь возможность отменить -
1) insert - вставляет его в дерево и поддерживает баланс (толкает информация о действии в стек)
2) delete - получает узел и удаляет ссылку из дерева (помещает информацию о действии в стек)
После обоих действий произойдет перебалансировка. (Проблема не в этом)
У меня такой вопрос - Насколько эффективно мы можем отследить акт удаления и акт вставки?
Для вставки:
Мне дан указатель на необходимые узлы и номер дела для «типа вставки».
Из моего предполагаемого худшего случая было бы, когда вам нужно удалить узел и сделать «двойное» вращение, чтобы снова сбалансировать дерево. В основном O (1).
Для удаления:
Мне дан указатель на необходимые узлы и номер дела для «типа удаления».
Из моего предполагаемого худшего случая было бы, когда вам нужно повторно сбалансировать дерево h раз после удаления узла. В основном O (log (n))
Я что-то упустил? Еще одна вещь, которая меня смущает, это анализ омеги здесь, как мы можем даже рассмотреть омегу здесь? Разве это не то же самое?
Спасибо, хорошего дня.