Дерево покрытий

Дерево покрытий (англ. Cover tree) — древовидная структура данных (дерево), специально разработанная для ускорения поиска ближайшего соседа.

Дерево можно рассматривать как иерархию, верхний уровень которой содержит корневую точку, а нижний - все точки в метрическом пространстве. Каждому уровню соответствует целое число , которое уменьшается на единицу в каждом нижнем уровне. Каждый уровень в дереве покрытий имеет три важных свойства:

  • Вложенность:
  • Покрытие: Для каждой точки существует точка такая, что расстояние от до меньше или равно, чем и ровно одна такая точка является предком точки .
  • Разделение: Для всех точек расстояние от до больше или равно, чем .

Вычислительная сложностьПравить

ПоискПравить

ВставкаПравить

ПамятьПравить

См. такжеПравить

СсылкиПравить