Получить медиану из дерева AVL?

Если у вас есть дерево AVL, как лучше всего получить из него медиану? Медиана будет определена как элемент с индексом ceil(n/2) (индекс начинается с 1) в отсортированном списке.

Итак, если список был

1 3 5 7 8

медиана равна 5. Если бы список был

1 3 5 7 8 10

медиана 5.

Если вы можете увеличить дерево, я думаю, лучше всего сообщить каждому узлу размер (количество узлов) поддерева (т.е. 1 + левый.размер + правый.размер). Используя это, лучший способ, который я могу придумать, - это медианный поиск O (lg n) времени, потому что вы можете проходить, сравнивая индексы.

Есть ли способ лучше?


performance median algorithm data-structures avl-tree
person omega    schedule 11.02.2013    source источник
comment
FWIW, метод размещения счетчиков в узлах превращает ваши деревья AVL также в деревья статистики заказов: en.wikipedia. org/wiki/Order_statistic_tree . Конечно, вы также должны изменить вращения в алгоритме балансировки, чтобы настроить количество узлов. Идея @templatetypedef о многопоточности дерева и использовании одного медианного указателя оптимальна. Он не требует подсчета узлов и имеет постоянное время на операцию. Он не упомянул, что вам также необходимо знать общее количество узлов в дереве, чтобы вы могли определить, является ли медиана одним элементом (нечетное количество узлов) или средним значением двух (четное количество узлов).   -  person Gene    schedule 22.05.2014
comment
@Gene Спасибо за заполнение этих деталей!   -  person templatetypedef    schedule 22.05.2014

Ответы (1)


arrow_upward
6
arrow_downward

Увеличение дерева AVL для хранения размеров поддеревьев, как правило, является лучшим подходом, если вам нужно оптимизировать медианные запросы. Это занимает время O(log n), что довольно быстро.

Если вы будете вычислять медиану огромное количество раз, вы потенциально можете использовать расширенное дерево, а также кэшировать медианное значение, чтобы вы могли прочитать его за время O (1). Каждый раз, когда вы выполняете вставку или удаление, вам может потребоваться повторно вычислить медиану за время O(log n), что немного замедлит работу, но не повлияет на асимптотические затраты.

Другим вариантом может быть прохождение двусвязного списка через узлы в дереве, чтобы вы могли перемещаться от узла к его преемнику или предшественнику за постоянное время. Если вы это сделаете, вы можете сохранить указатель на срединный элемент, а затем при вставке или удалении переместить указатель влево или вправо в зависимости от ситуации. Если вы удалите саму медиану, вы можете просто переместить указатель влево или вправо по своему усмотрению. Это не требует каких-либо дополнений и может быть немного быстрее, но добавляет два дополнительных указателя в каждый узел.

Надеюсь это поможет!

person templatetypedef    schedule 22.05.2014
comment
Я хотел бы увидеть код для использования указателей в Javascript. - person JSkyS; 03.08.2020