覆蓋樹是計算機里的一種數據結構，是專門用於最近鄰搜尋的一種數據結構，可以提高最近鄰搜尋的效率、減少計算量。
基本介紹
- 中文名：覆蓋樹
- 外文名：Cover Tree
覆蓋樹具有顯式的和隱式兩種表示方式，隱式表示的覆蓋樹一個節點可能在樹中出現多次，但它在一層中至多出現一次。顯式表示的覆蓋樹則是將隱式表示的覆蓋樹的孩子節點與自己的節點合併，每一個顯式表示的覆蓋樹都有一個非己的父節點。相對來說顯式表示的覆蓋樹節省了存儲空間。
覆蓋樹中每一層C都遵循如下三個重要的特性（d(q,p)表示p、q之間的距離）：
嵌套（Nesting）：
⊆
覆蓋（Covering）：對於
，
，使得d(p,q)
，且q是p的父節點
分隔（Separation）：
， 有
