Описание тега range-tree
Дерево диапазонов - это структура данных, которая позволяет выполнять быстрые запросы диапазона, такие как [4, 5] x [-2, 0]. Используйте для вопросов, связанных с внедрением / изучением этого дерева.
1
ответ
Реализовать 2D дерево диапазона с ++
Я пытался понять дерево диапазонов в течение некоторого времени, но я все еще не могу понять это. Может кто-нибудь объяснить мне это с помощью реализации, потому что я хочу использовать это для решения 2D RMQ, я знаю дерево сегментов, и мой учитель …
27 мар '13 в 16:20
0
ответов
Range Trees: почему бы не сэкономить место по умолчанию?
Предположим, у вас есть набор S уникальных точек на 2-мерной плоскости. Теперь вы ожидаете кучу вопросов в виде "это точка p присутствует в S"Вы решили построить Range Range для хранения вашего S и ответь на этот вопрос. Основная идея Range Range за…
04 ноя '17 в 18:29
3
ответа
Интервальная структура дерева данных с ++
У меня есть требование, где я должен обновить цвет графического интерфейса на основе некоторого значения атрибута. Значение атрибута имеет разные диапазоны.... скажем, от -30 до -45, от -60 до -80 и так далее.... Итак, мне нужна была структура данны…
20 янв '15 в 19:36
0
ответов
Дерево с большими размерами
Я столкнулся с проблемой, когда может помочь дерево интервалов высокой размерности. Я могу понять, как работает одномерное дерево интервалов. Но я не вижу, как это должно быть реализовано в более высоком измерении. Дерево интервалов и диапазон дерев…
03 апр '17 в 13:23
0
ответов
Какую структуру данных выбрать для поиска по ортогональному диапазону?
Мне нужно решить задачу поиска соседей, то есть для каждого данного элемента найти все соседние элементы на фиксированном расстоянии. Я только что узнал структуру данных range treeПохоже, что она способна решить эту проблему в сложности O(N*(log(N)^…
17 апр '15 в 03:00
1
ответ
Почему число поддеревьев, полученных в результате запроса дерева диапазонов, равно O(log(n))?
Я пытаюсь выяснить эту структуру данных, но я не понимаю, как мы можем сказать, что есть O(log(n)) поддеревьев, которые представляют ответ на запрос? Вот картинка для иллюстрации: Спасибо!
17 ноя '18 в 12:56
1
ответ
Четкая и эффективная реализация 3D Range Tree
Я работаю над этим проектом, где мне нужно искать объекты в трехмерном пространстве, и эффективность - огромная проблема, я думаю, что Range Tree идеально подходит для того, что я пытаюсь сделать, Interval Tree также будет работать, но я не Я собира…
14 дек '12 в 01:31
2
ответа
Диапазон / Сегмент Дерево Рубин
Я ищу реализацию диапазона или дерева сегментов в Ruby. Я не мог найти образец или драгоценный камень в наличии. У кого-нибудь есть пример кода? Спасибо,
08 авг '11 в 18:35
1
ответ
Моделирование узла в RangeTree
В настоящее время я реализую 2D Range Range. У меня возникли проблемы при разработке правдоподобной модели (на Java) для моего класса Node. Узел в дереве может иметь любое из следующих значений: среднее значение, указатель правого и левого дочернего…
12 фев '11 в 19:18
2
ответа
Широко ли используется дерево диапазонов в задачах пространственного поиска?
Я ищу некоторые структуры данных для поиска диапазона. Я думаю, что деревья диапазона предлагают хорошую сложность времени (но с некоторыми требованиями к хранению). Однако мне кажется, что другие структуры данных, такие как KD-деревья, более обсужд…
18 апр '15 в 13:36
1
ответ
Количество элементов в интервале (x,y) за время (logn)(logn)
Домашнее задание Мне нужно использовать структуру данных + алгоритм, который возвращает количество элементов в диапазоне, состоящем из 2 (x,y) значений (т.е. возвращает количество элементов, попадающих в прямоугольный диапазон на плоскости xy) в O(l…
30 июл '14 в 05:17
1
ответ
Как сделать запрос с многомерным диапазоном с фиксированным диапазоном?
У меня есть около 10^4 точек в 7-мерном пространстве. Для определенного приложения мне нужно сделать ~10^6 запросов диапазона на этом входе, чтобы найти все точки, которые лежат в данном диапазоне. В этом приложении все запросы используют одинаковый…
24 апр '14 в 02:49
3
ответа
Самый эффективный способ выбрать точку с наиболее окружающими точками
NB: в нижней части вопроса есть серьезное редактирование - проверьте это Вопрос Скажем, у меня есть набор точек: Я хочу найти точку с наибольшим количеством точек вокруг нее в радиусе (то есть круг) или внутри (т.е. квадрат) точки для 2-х измерений.…
04 июн '17 в 02:12
1
ответ
Как искать в дереве диапазонов?
Я прочитал несколько слайдов, как эта последняя страница, где описывают алгоритм поиска. Однако у меня есть основной вопрос. Данные лежат в двухмерном пространстве. Сначала я строю дерево бинарного поиска на основе значения x точек. Каждый внутренни…
14 май '16 в 00:40
0
ответов
2D RMQ Range Tree
Привет, я пытаюсь реализовать дерево 2D-диапазона для rmq-ing, вот мой код, я думаю, что он недостаточно эффективен, есть ли что-то, что я могу сделать для оптимизации. ls содержит список y, отсортированный на каждом узле рт содержит дерево сегменто…
28 мар '13 в 06:18
0
ответов
Подсчет запросов для деревьев 2D-диапазона с использованием дробного каскадирования
Существуют ли библиотеки, которые предоставили деревья 2d-диапазона с дробным каскадом, которые имеют O(log n) сложность для запросов подсчета диапазона (то есть, O(log^(d-1) n) для d размеров) Один многообещающий кодовый фрагмент, который я нашел, …
07 июн '17 в 23:15
1
ответ
Реализация дерева диапазонов
Я пытаюсь реализовать дерево диапазонов, но я действительно запутался, вот мой текст: Теперь предположим, что у меня есть такое дерево: И я хочу найти точки между 14 и 19. V_Split здесь было бы 17, и, переходя от 17 к 14, согласно алгоритму, я долже…
28 май '15 в 05:14
1
ответ
Путаница в дереве поиска приоритетов
Единственный разумный набор слайдов, который я нашел, это то, что на странице 15 говорит, для построения: Сортируйте все точки по их значениям координаты x и сохраните их в конечных узлах сбалансированного двоичного дерева (т. Е. Дерева диапазонов) …
14 май '16 в 03:33
1
ответ
Алгоритм нахождения ячеек сетки, содержащихся в произвольно повернутом прямоугольнике (растеризация)
Я ищу алгоритм, который может вычислить все ячейки сетки, занятые произвольным прямоугольником в 2-мерном пространстве в определенной области. Прямоугольник определяется его четырьмя угловыми координатами. На рисунке ниже я отметил два из них как кр…
13 авг '19 в 22:19
0
ответов
java.lang.StackOverflowError исключение для примитивных значений вложенных объектов в сериализации объектов Java
У меня есть RangeTreeIndex а также RangeTreeNode класс, который я использую для создания индекса и после вставки 2500 записей, после этого я пытаюсь сохранить RangeTreeIndex объект в файле, из которого я получаю StackruError, ниже мой весь код: publ…
22 ноя '19 в 04:04