AVL дерево управления

Question

У меня есть вопрос по AVL, предположим, что я создал некоторое avl-дерево целых чисел, как мне нужно управлять вставкой в ​​мое дерево, чтобы можно было извлечь самую длинную последовательность чисел (вставка должна быть сложнойO (logn)), например:

          _   10   _
   _  7 _                _  12  _
6          8

в этом случае самая длинная последовательность будет 6,7,8, поэтому в моей функции void sequence(int* low, int* high) я сделаю *low = 6, *high = 8 ...

сложность функции (последовательности) должна быть O (1)

заранее спасибо за любую идею

Answer 1

На самом деле, если вы создаете интервальный список или что-то очень похожее на него, а затем сохраняете его компоненты в дереве AVL, вы, вероятно, могли бы сделать это хорошо.Дело в том, что вы не просто хотите заданную последовательность, вы хотите самую длинную последовательность.Дольше всего лексически смежных клавиш *, если быть точным.Что, как ни странно, довольно сложно, я думаю, не прибегая к пользовательской метрике для построения вашего дерева AVL.Я предполагаю, что если ваш компаратор для дерева AVL, построенного на списке интервалов, был f (длина интервала), вы могли бы получить его в o (logn) или, возможно, быстрее, если ваша реализация AVL имеет быстрый максимум \ мин.

Мне очень жаль, я надеялся получить дополнительную помощь, но тот факт, что мы должны использовать дерево AVL, немного беспокоит.Мне интересно, есть ли уловка, которую можно использовать с поддеревьями, но я просто не вижу хорошего способа сделать такой подход o (1) без такой предварительной обработки, чтобы это было шуткой.Что-то с фильтрами Блума может работать?

* Некоторые общие порядки могут создавать похожие прогоны, но не у всех есть значимая концепция непосредственной смежности в их ... ну ... фазовом пространстве, я полагаю? **

** Мое слабое формальное образование действительно сейчас меня кусает.

Answer 2

Базовая вставка и поворот в деревьях AVL гарантирует производительность, близкую к O (logn).

Возвращаясь ко 2-й части вашего вопроса, чтобы найти «сложность» вашей последовательности, вам сначала нужно найти (или перейти к) «низкий» элемент в вашем дереве AVL, который сам доставит вас НА БОЛЬШЕ O (LOGN).

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