Дерево с большими размерами
Я столкнулся с проблемой, когда может помочь дерево интервалов высокой размерности. Я могу понять, как работает одномерное дерево интервалов. Но я не вижу, как это должно быть реализовано в более высоком измерении.
Дерево интервалов и диапазон деревьев
Объяснение в Википедии говорит об использовании дерева диапазонов и дерева интервалов для каждого измерения. Но я не вижу, как это работает! Объяснение там для меня непонятно... Пожалуйста, проверьте раздел "Более высокие размеры":
Во-первых, построено дерево диапазонов в N измерениях, которое позволяет эффективно извлекать все интервалы с начальной и конечной точками внутри области запроса R. После того, как найдены соответствующие диапазоны, единственное, что остается, - это те диапазоны, которые охватывают область в некоторых областях. измерение.
Если дерево диапазона более эффективно, зачем нам интервальные деревья?
Переходя к деревьям диапазонов, мы видим, что это было сделано для точек запроса внутри интервала (дерево не хранит интервалы). Поэтому я предполагаю, что Википедия означает:
Сначала строится дерево диапазонов в N измерениях, которое позволяет эффективно извлекать все интервалы с начальной или конечной точкой ИЛИ в области запроса R.
Тогда что? Если я создам дерево интервалов для каждого измерения из этой точки, любой из этих интервалов будет находиться над моим окном поиска, даже если исходные объекты не пересекаются с моим запросом. Пожалуйста, проверьте следующее изображение, чтобы попытаться визуализировать то, что я говорю.
Может быть, что мне не ясно, так это: как я могу пересечь интервальные результаты обоих интервальных деревьев, чтобы убедиться, что они лежат над объектом?
Может ли кто-нибудь дать объяснение, как использовать деревья диапазона в этом случае?
R Tree
Просто чтобы упомянуть, я знаю о существовании R Tree. Но сначала я хочу понять дерево интервалов в высоком измерении. Более того, как примечание, в Википедии говорится:
Интервальное дерево - Вырожденное R-дерево для одного измерения (обычно времени).
С чем я категорически не согласен. В противном случае, почему мы должны говорить о дереве с большими интервалами? Если я хорошо понимаю оба метода:
R Tree использует MBR для группировки объектов, в то время как Interval Tree использует точки.
R Tree может хранить любые пространственные объекты, а Interval Tree - только интервалы.
R Tree нужно время от времени разбивать узлы, что кажется дорогим. Дерево интервалов никогда не разделяет узел.