Последовательность чисел, над которой выполняются различные операции, представленная в виде дерева AVL. ⇐ JAVA

[Anonymous]

Итак — у меня есть заданная последовательность чисел, над которой мне нужно выполнить определенное количество операций по вставке и удалению некоторых ее элементов. Мне также нужен указатель, указывающий на используемый в данный момент элемент.

Это должно выглядеть так:

Если я предоставлю программе последовательность чисел 6 0 5 2 7 11 - указатель окажется в начале (сейчас на цифре 6). Если это число четное, мне нужно удалить число в следующей позиции - в данном случае - число 0, а затем переместить указатель на (значение удаленного элемента). Таким образом, последовательность будет выглядеть так: 6 5 2 7 11, а указатель по-прежнему будет иметь номер 6. Также важно, чтобы последовательность работала как цикл, поэтому следующий элемент после последнего является первым элементом последовательности. Второй случай — когда число под указателем нечетное. Если это произойдет, мне придется добавить элемент со значением: (значение числа под указателем) - 1 и переместить указатель на значение, которое в данный момент находится под ним (в данном случае 7). Итак, в последовательности 7 2 6 и указатель на элемент 7 - это будет выглядеть так: 7 6 2 6 и указатель будет на последний 6 элемент последовательности.

Итак, используя предыдущий пример: предоставленная последовательность чисел — 6 0 5 2 7 11, а указатель находится на цифре 6.

6 0 5 2 7 11 – указатель на цифру 6.

6 5 2 7 11 – 6 – это даже если я удалю следующий элемент, указатель останется на уровне 6, поскольку значение удаленного числа равно 0. 6 2 7 11 – Та же ситуация, но на этот раз я перемещаю элемент pointer 5 вправо, так что теперь он находится на цифре 2.

6 2 11 — 2 тоже четное, поэтому я удаляю 7 и перемещаю элементы pointer 7 вправо.

6 2 11 10 – 11 нечетно, поэтому я добавляю (11 – 1) в качестве следующего элемента последовательности и перемещаю указатель на 11 элементов. После выполнения 4 операций добавления или удаления элементов последовательность чисел выглядит следующим образом: 6 2 11 10.

Моя проблема заключается в том, как реализовать этот алгоритм с использованием дерева AVL, поскольку я хочу, чтобы его временная сложность была xlogn, где x — количество операций вставки или удаления. это нужно сделать

Моей первой мыслью было просто сохранить индекс каждого узла, что позволило бы мне быстро искать последующие элементы дерева (например, если я знаю, что мне нужно переместить указатель в последовательности на 5 элементов, я мог бы добавьте его текущее значение к 5 и найдите в дереве элемент с индексом x + 5), а затем выполните какое-либо действие, например. добавьте число 10 в качестве следующего элемента. Проблема в том, что если число 10 теперь будет иметь индекс x+5+1, то мне придется менять индексы для всех следующих элементов последовательности, и мне кажется, что это не позволит достичь временной сложности xlogn. .

Итак, мой вопрос: как мне решить эту проблему?

Конечно, если что-то непонятно, я постараюсь объяснить по-другому, проще.