Дерево покрытий ( англ. 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}}$ .

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

Поиск

Вставка

Этот раздел статьи ещё не написан . Здесь может располагаться отдельный раздел. Помогите Википедии, написав его. ( 30 июня 2016 )

Память

Этот раздел статьи ещё не написан . Здесь может располагаться отдельный раздел. Помогите Википедии, написав его. ( 30 июня 2016 )

См. также

• Задача поиска ближайшего соседа
• K-мерное дерево

Ссылки

• Alina Beygelzimer, Sham Kakade, and John Langford. Cover Trees for Nearest Neighbor. In Proc. International Conference on Machine Learning (ICML), 2006.
• .
• .

Это заготовка статьи по информатике . Помогите Википедии, дополнив её.