WikiSort.ru - Программирование

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

Память

Этот раздел статьи ещё не написан. Согласно замыслу одного или нескольких участников Википедии, на этом месте должен располагаться специальный раздел. Вы можете помочь проекту, написав этот раздел. Эта отметка установлена 30 июня 2016 года.

См. также

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

Ссылки

• Alina Beygelzimer, Sham Kakade, and John Langford. Cover Trees for Nearest Neighbor. In Proc. International Conference on Machine Learning (ICML), 2006.
• John Langford's Cover Tree page.
• Реализация Cover tree на C++.

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