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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Вычислительная сложность[править | править вики-текст]

Поиск[править | править вики-текст]

Вставка[править | править вики-текст]

Память[править | править вики-текст]

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]