1、首先從根節(jié)點(diǎn)開始遞歸往下找到包含x的葉子節(jié)點(diǎn)，每一層都是找對(duì)應(yīng)的xi

2、將這個(gè)葉子節(jié)點(diǎn)認(rèn)為是當(dāng)前的“近似最近點(diǎn)”

3、遞歸向上回退，如果以x圓心，以“近似最近點(diǎn)”為半徑的球與根節(jié)點(diǎn)的另一半子區(qū)域邊界相交，則說(shuō)明另一半子區(qū)域中存在與x更近的點(diǎn)，則進(jìn)入另一個(gè)子區(qū)域中查找該點(diǎn)并且更新”近似最近點(diǎn)“

4、重復(fù)3的步驟，直到另一子區(qū)域與球體不相交或者退回根節(jié)點(diǎn)

5、最后更新的”近似最近點(diǎn)“與x真正的最近點(diǎn)

KD樹進(jìn)行KNN查找：

通過(guò)KD樹的搜索找到與搜索目標(biāo)最近的點(diǎn)，這樣KNN的搜索就可以被限制在空間的局部區(qū)域上了，可以大大增加效率

KD樹搜索的復(fù)雜度：

當(dāng)實(shí)例隨機(jī)分布的時(shí)候，搜索的復(fù)雜度為log(N)，N為實(shí)例的個(gè)數(shù)，KD樹更加適用于實(shí)例數(shù)量遠(yuǎn)大于空間維度的KNN搜索，如果實(shí)例的空間維度與實(shí)例個(gè)數(shù)差不多時(shí)，它的效率基于等于線性掃描。