Меню Главная Случайная статья Настройки Дерево покрытий Материал из https://ru.wikipedia.org Дерево покрытий (англ. 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}}$. Содержание 1 Вычислительная сложность 1.1 Поиск 1.2 Вставка 1.3 Память 2 См. также 3 Ссылки Вычислительная сложность Поиск Вставка