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

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

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

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

  • Вложенность: C_{i} \subseteq C_{i-1}
  • Покрытие: Для каждой точки p \in C_{i-1} существует точка q \in C_{i} такая, что расстояние от p до q меньше или равно, чем 2^{i} и ровно одна такая точка q является предком точки p.
  • Разделение: Для всех точек p,q \in C_i расстояние от p до q больше или равно, чем 2^{i}.

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

Поиск[править | править исходный текст]

Вставка[править | править исходный текст]

Память[править | править исходный текст]

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]