Дерево диапазонов
-
Описание дерева диапазонов
- Упорядоченная древовидная структура данных для отображения точек в пределах заданного диапазона.
- Используется в двух или более измерениях.
- Альтернатива дереву k-d.
-
История и усовершенствования
- Представлено Джоном Луисом Бентли в 1979 году.
- Усовершенствовано Бернардом Шазеллом в 1990 году.
-
Структура данных
- Одномерное дерево диапазонов: сбалансированное бинарное дерево поиска.
- Многомерное дерево диапазонов: рекурсивно определенное многоуровневое двоичное дерево поиска.
-
Операции
- Построение: O(n log n) для одномерного дерева, O(n log^d n) для многомерного дерева.
- Запросы по диапазону: O(log n + k) для одномерного дерева, O(log^d n + k) для многомерного дерева.
-
Рекомендации и внешние ссылки
- Ссылки на библиотеки и ресурсы для работы с деревьями диапазонов.