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

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

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

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