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