Я ищу структуру данных, которая хранит в себе диапазоны, задаваемые координатой начала и конца, и поддерживает операции
* добавить диапазон
* удалить диапазон
* Найти все диапазоны, содержащие некоторую точку.
Хотелось бы, чтобы эти операции работали быстрее, чем за линейное время.
Гугл предлагает дерево отрезков, но, если я правильно понимаю, добавление и удаление там в худшем случае будет как раз линейным.
Здравствуйте, LaptevVV, Вы писали:
LVV>Дерево отрезков ?
Процитирую кусок своего же сообщения
> Гугл предлагает дерево отрезков, но, если я правильно понимаю, добавление и удаление там в худшем случае будет как раз линейным.
DTF>Я ищу структуру данных, которая хранит в себе диапазоны, задаваемые координатой начала и конца, и поддерживает операции DTF> * добавить диапазон DTF> * удалить диапазон DTF> * Найти все диапазоны, содержащие некоторую точку.
DTF>Хотелось бы, чтобы эти операции работали быстрее, чем за линейное время.
Здравствуйте, σ, Вы писали:
σ>https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree : >> Both insertion and deletion require O ( log n ) time, with n being the total number of intervals in the tree prior to the insertion or deletion operation
А какая там сложность поиска в случае, когда надо найти все интервалы, в которые входит данная точка?
Если бы был нужен один интервал, то понятно, что логарифм.
Но мне нужны все.
P.S.
Получается, interval tree — это не то же самое, что по-русски дерево отрезков
σ>>https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree : >>> Both insertion and deletion require O ( log n ) time, with n being the total number of intervals in the tree prior to the insertion or deletion operation DTF>А какая там сложность поиска в случае, когда надо найти все интервалы, в которые входит данная точка? DTF>Если бы был нужен один интервал, то понятно, что логарифм. DTF>Но мне нужны все.
Ну, очевидно же: n log n
Но, наверное, еще зависит от того, что ты с ними делать будешь ?
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
σ>>>https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree : >>>> Both insertion and deletion require O ( log n ) time, with n being the total number of intervals in the tree prior to the insertion or deletion operation DTF>>А какая там сложность поиска в случае, когда надо найти все интервалы, в которые входит данная точка? DTF>>Если бы был нужен один интервал, то понятно, что логарифм. DTF>>Но мне нужны все. LVV>Ну, очевидно же: n log n
Откуда очевидно? Даже если всё дерево обходить и проверять каждый интервал, то это O(n)
Здравствуйте, σ, Вы писали:
σ>>>>https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree : >>>>> Both insertion and deletion require O ( log n ) time, with n being the total number of intervals in the tree prior to the insertion or deletion operation DTF>>>А какая там сложность поиска в случае, когда надо найти все интервалы, в которые входит данная точка? DTF>>>Если бы был нужен один интервал, то понятно, что логарифм. DTF>>>Но мне нужны все. LVV>>Ну, очевидно же: n log n
σ>Откуда очевидно? Даже если всё дерево обходить и проверять каждый интервал, то это O(n)
если обходить все дерево
то зачем здесь дерево?
дерево за тем и нужно, что бы обходить его за логарифм
Здравствуйте, DTF, Вы писали:
DTF>Гугл предлагает дерево отрезков, но, если я правильно понимаю, добавление и удаление там в худшем случае будет как раз линейным.
Спрашивай лучше Клода, он намного больше в программировании прошарен
Ваша задача — эффективно хранить диапазоны (отрезки) и быстро выполнять:
добавление диапазона,
удаление диапазона,
поиск всех диапазонов, содержащих точку.
Дерево отрезков (segment tree) действительно не всегда эффективно для динамического добавления/удаления произвольных диапазонов. Для вашей задачи лучше подойдут следующие структуры данных:
1. Interval Tree (интервальное дерево)
Основано на сбалансированном дереве поиска (например, AVL или красно-черное дерево).
Каждый узел хранит диапазон и максимальное значение конца в поддереве.
Операции:
Добавление/удаление диапазона: O(log n)
Поиск всех диапазонов, содержащих точку: O(log n + k), где k — число найденных диапазонов.
2. Segment Tree с динамическими списками
Можно реализовать динамическое дерево отрезков, где в каждом узле хранятся списки диапазонов, полностью покрывающих этот узел.
Добавление/удаление: O(log n + k)
Поиск: O(log n + k)
3. Augmented BST (например, Order Statistic Tree)
Можно хранить интервалы в сбалансированном BST, дополнительно поддерживая максимум конца в поддереве.
Рекомендация
Для вашей задачи классическим и хорошо изученным решением является интервальное дерево (interval tree).
Оно поддерживает все нужные операции быстрее, чем за линейное время.
Здравствуйте, DTF, Вы писали:
DTF>Всем привет. DTF>Нужна помощь коллег.
DTF>Я ищу структуру данных, которая хранит в себе диапазоны, задаваемые координатой начала и конца, и поддерживает операции DTF> * добавить диапазон DTF> * удалить диапазон DTF> * Найти все диапазоны, содержащие некоторую точку.
DTF>Хотелось бы, чтобы эти операции работали быстрее, чем за линейное время. DTF>Гугл предлагает дерево отрезков, но, если я правильно понимаю, добавление и удаление там в худшем случае будет как раз линейным.
DTF>В общем, нужна помощь коллективного разума
Можно посмотреть на R-tree.
Есть реализация в sqlite (1, 2х и тд мерные) так что можно прикинуть скорость работы в конкретном случае.
Есть и специализированные библиотеки.
Здравствуйте, DTF, Вы писали:
bnk>>Поиск всех диапазонов, содержащих точку: O(log n + k), где k — число найденных диапазонов.
DTF>Вот я не понимаю, откуда там O(log n + k) ?
Из Википедии я думаю, но могу спросить, у меня самого моск уже фсе, атрофировался, я теперь стратегией занимаюсь, как тот филин из анекдота
Если всего один интервал, до него надо спуститься, а это в худшем случае h = log n для ±сбалансированных деревьев
А идти по дереву (влево, если ещё внутри левой границы, и вправо, если внутри максимальной правой) и обрабатывать все подходящие k интервалов — это k
Примерно так можно почувствовать
Ну и оценка — верхняя. Если все интервалы подходят, то сложность не C1*n + C2*log n,, а просто C1*n
Здравствуйте, σ, Вы писали:
σ>Если всего один интервал, до него надо спуститься, а это в худшем случае h = log n для ±сбалансированных деревьев σ>А идти по дереву (влево, если ещё внутри левой границы, и вправо, если внутри максимальной правой) и обрабатывать все подходящие k интервалов — это k
σ>Примерно так можно почувствовать
Если все интервалы, то мы спускаемся влево за логарифм, как уже написали, и вправо.
Но вправо — это тоже логарифм, разве нет?
Т.е. чтобы найти каждый интервал, нам надо погулять по дереву.
Это k*log(n) вроде бы
DTF>Т.е. чтобы найти каждый интервал, нам надо погулять по дереву. DTF>Это k*log(n) вроде бы
k*log(n) было бы если бы спускались каждый раз от корня и возвращались назад в корень после нахождения очередного интервала, и потом спускались до следующего
