Дерево можно рассматривать как иерархию, верхний уровень которой содержит корневую точку, а нижний - все точки в
метрическом пространстве
. Каждому уровню
соответствует целое число
, которое уменьшается на единицу в каждом нижнем уровне. Каждый уровень
в дереве покрытий имеет три важных свойства:
Вложенность:
Покрытие:
Для каждой точки
существует точка
такая, что расстояние от
до
меньше или равно, чем
и ровно одна такая точка
является предком точки
.
Разделение:
Для всех точек
расстояние от
до
больше или равно, чем
.
Alina Beygelzimer, Sham Kakade, and John Langford. Cover Trees for Nearest Neighbor. In Proc. International Conference on Machine Learning (ICML), 2006.