Каковы различия между деревьями сегментов, деревьями интервалов, деревьями с двоичными индексами и деревьями диапазонов?

200

Каковы различия между деревьями сегментов, деревьями интервалов, деревьями с двоичными индексами и деревьями диапазонов с точки зрения:

  • Ключевая идея / определение
  • Приложения
  • Производительность / порядок в больших размерах / потребление пространства

Пожалуйста, не просто дайте определения.

Адитья
источник
12
Это не дубликат. Вопрос в том, являются ли деревья Фенвика обобщением интервала времени, и мой вопрос более конкретен и отличается.
Адитья
7
На stackoverflow.com/questions/2795989/… он не получил ответа , ответ там просто дает определение.
Адитья
12
Как это слишком широко? "Каковы некоторые различия между х и у?" так же ясно и целенаправленно, как и получается. Это очень хороший вопрос.
IVlad
16
И нет никакого хорошего ответа на это, доступный где-нибудь. Хороший ответ будет отличным для сообщества
Адитья
22
Большинство этих структур данных (кроме деревьев Фенвика) рассматриваются в этом PDF-документе: «Деревья поиска по интервалам, сегментам, диапазонам и приоритетам» (автор DT Lee). Или вы можете прочитать его как главу из этой книги: «Справочник по структурам данных и приложениям» .
Евгений Клюев

Ответы:

319

Все эти структуры данных используются для решения разных задач:

  • Дерево сегментов хранит интервалы и оптимизируется для запросов « какой из этих интервалов содержит заданную точку ».
  • В дереве интервалов также хранятся интервалы, но они оптимизированы для запросов « какие из этих интервалов перекрываются с заданным интервалом ». Его также можно использовать для точечных запросов - аналогично сегментному дереву.
  • Дерево диапазона хранит точки и оптимизировано для запросов « какие точки попадают в заданный интервал ».
  • Двоичное индексированное дерево хранит количество элементов на индекс и оптимизировано для запросов « сколько элементов между индексами m и n ».

Производительность / потребление пространства для одного измерения:

  • Сегментное дерево - O (n logn) время предварительной обработки, O (k + logn) время запроса, O (n logn) пространство
  • Дерево интервалов - O (n logn) время предварительной обработки, O (k + logn) время запроса, O (n) пространство
  • Дерево диапазонов - O (n logn) время предварительной обработки, O (k + logn) время запроса, O (n) пространство
  • Двоичное индексированное дерево - O (n logn) время предварительной обработки, O (logn) время запроса, O (n) пространство

(k - количество зарегистрированных результатов).

Все структуры данных могут быть динамическими в том смысле, что сценарий использования включает как изменения данных, так и запросы:

  • Дерево сегментов - интервал может быть добавлен / удален за время O (logn) (см. Здесь )
  • Дерево интервалов - интервал может быть добавлен / удален за время O (logn)
  • Дерево диапазонов - новые точки могут быть добавлены / удалены за O (logn) время (см. Здесь )
  • Двоичное индексированное дерево - количество элементов на индекс может быть увеличено за время O (logn)

Более высокие размеры (d> 1):

  • Сегментное дерево - O (n (logn) ^ d) время предварительной обработки, O (k + (logn) ^ d) время запроса, O (n (logn) ^ (d-1)) пространство
  • Дерево интервалов - O (n logn) время предварительной обработки, O (k + (logn) ^ d) время запроса, O (n logn) пространство
  • Дерево диапазонов - O (n (logn) ^ d) время предварительной обработки, O (k + (logn) ^ d) время запроса, O (n (logn) ^ (d-1))) пространство
  • Двоичное индексированное дерево - O (n (logn) ^ d) время предварительной обработки, O ((logn) ^ d) время запроса, O (n (logn) ^ d) пространство
Лиор Коган
источник
12
У меня действительно складывается впечатление, что сегментированные деревья <интервальные деревья из этого. Есть ли причина предпочитать дерево сегментов? Например, простота реализации?
j_random_hacker
7
@j_random_hacker: Алгоритмы, основанные на деревьях сегментов, имеют преимущества в некоторых более сложных многомерных вариантах запроса интервалов. Например, определение того, какие неосевые параллельные отрезки пересекаются с 2D-окном.
Лиор Коган
5
Спасибо, я бы заинтересовался любой разработкой, которую вы могли бы дать по этому поводу.
j_random_hacker
3
@j_random_hacker, деревья сегментов имеют еще одно интересное применение: RMQ (минимальный диапазон запросов) за O (log N), где N - общий размер интервала.
ars-longa-vita-brevis
1
Почему деревья сегментов O (n log n) пространства? Они хранят N листьев + N / 2 + N / 4 + ... + N / 2 ^ (log N), и эта сумма равна O (N), если я не ошибаюсь. Также @ icc97 answer также сообщает O (N) пробел.
Муравей
24

Не то чтобы я мог добавить что-нибудь к ответу Лиора , но похоже, что это может быть сделано с хорошим столом.

Одно измерение

k количество сообщенных результатов

|              | Segment       | Interval   | Range          | Indexed   |
|--------------|--------------:|-----------:|---------------:|----------:|
|Preprocessing |        n logn |     n logn |         n logn |    n logn |
|Query         |        k+logn |     k+logn |         k+logn |      logn |
|Space         |        n logn |          n |              n |         n |
|              |               |            |                |           |
|Insert/Delete |          logn |       logn |           logn |      logn |

Более высокие размеры

d > 1

|              | Segment       | Interval   | Range          | Indexed   |
|--------------|--------------:|-----------:|---------------:|----------:|
|Preprocessing |     n(logn)^d |     n logn |      n(logn)^d | n(logn)^d |
|Query         |    k+(logn)^d | k+(logn)^d |     k+(logn)^d |  (logn)^d |
|Space         | n(logn)^(d-1) |     n logn | n(logn)^(d-1)) | n(logn)^d |

Эти таблицы создаются в Github Formatted Markdown - посмотрите этот список, если вы хотите, чтобы таблицы были отформатированы правильно.

icc97
источник
2
Что вы подразумеваете под отчетными результатами?
Пратик Сингхал
@ ps06756 Алгоритмы поиска часто имеют время выполнения log (n), где n - размер входного файла, но может давать линейные по n результаты, которые невозможно сделать в логарифмическом времени (вывод n чисел в лог (n) невозможен) ,
oerpli
1
Разве дерево сегментов не должно быть O(n logn) spaceв первой таблице?
Danny_ds