Дерево покрытий () — древовидная структура данных (дерево), специально разработанная для ускорения поиска ближайшего соседа.
Дерево можно рассматривать как иерархию, верхний уровень которой содержит корневую точку, а нижний - все точки в метрическом пространстве. Каждому уровню соответствует целое число , которое уменьшается на единицу в каждом нижнем уровне. Каждый уровень в дереве покрытий имеет три важных свойства:
Вложенность: Покрытие: Для каждой точки существует точка такая, что расстояние от до меньше или равно, чем и ровно одна такая точка является предком точки . Разделение: Для всех точек расстояние от до больше или равно, чем .
Вычислительная сложность
Поиск
Вставка
Память
См. также Задача поиска ближайшего соседа K-мерное дерево
Ссылки
Alina Beygelzimer, Sham Kakade, and John Langford. Cover Trees for Nearest Neighbor. In Proc. International Conference on Machine Learning (ICML), 2006. John Langford's Cover Tree page. Реализация Cover tree на C++.
Категория:Деревья (структуры данных)