目錄

• 1.數(shù)據(jù)結構定義
  1.1 定義
  1.2 一維k-d樹（1-d樹——二叉搜索樹）
  1.3 二維k-d樹（2-d樹）
  1.4 k-d樹的結構性質
• 2.應用
• 3.數(shù)據(jù)結構以及操作
  3.1 Weiss《數(shù)據(jù)結構與算法分析》中簡單的定義
  3.2 UFL（佛羅里達大學）課程給出的定義
  3.3 一個經(jīng)典的定義

1.數(shù)據(jù)結構定義

1.1 定義

k-d樹（k-dimensional tree），是一棵二叉樹，樹中存儲的是一些k維數(shù)據(jù)。在一個k維數(shù)據(jù)集合上構建一棵k-d樹代表了對k維數(shù)據(jù)集合構成的k維空間的一個劃分，即樹中的每個結點就對應了一個k維的超矩形區(qū)域。

1.2 一維k-d樹（1-d樹——二叉搜索樹）

對于一維的情況，所有的點都在數(shù)軸上面，此時 k-d樹 其實就是二叉搜索樹。
二叉搜索樹（Binary Search Tree，BST），是具有如下性質的二叉樹：

• 若它的左子樹不為空，則左子樹上所有結點的值均小于它的根結點的值；
• 若它的右子樹不為空，則右子樹上所有結點的值均大于它的根結點的值；
• 它的左、右子樹也分別為二叉搜索樹；

例如，下圖是一棵二叉搜索樹，其滿足 BST 的性質。

1.3 二維k-d樹（2-d樹）

對于每一層，可以指定一個劃分維度（軸垂直分區(qū)面axis-aligned splitting planes），最簡單的就是按照關鍵字輪流劃分（例如：奇數(shù)層按照x軸劃分，也即第一個關鍵字；偶數(shù)層按照y軸劃分，也即第二個關鍵字）。

1.4 k-d樹的結構性質

一棵隨機構造的2-d樹與一棵隨機二叉搜索樹具有相同的結構性質：高度平均為O(lgN)，但最壞情形則是O(N)。
不像二叉搜索樹有精巧的O(lgN)最壞情況的變種在，沒有已知的方案能夠保證一棵平衡的2-d樹。問題在于，這樣一種方案很可能基于樹的旋轉，而樹旋轉在2-d樹中是行不通的。
最好的辦法是通過重新構造子樹來定期對樹進行平衡。

2.應用

多維鍵值搜索（例：范圍搜尋及最鄰近搜索）。
例如：一廣告公司擁有一個數(shù)據(jù)庫并需要為某些客戶生成郵寄標簽。典型的要求可能是需要散發(fā)郵件給那些年齡在34-49之間且年收入在100000美元到150000美元之間的人們。這個個問題叫做二維范圍查詢。

3.數(shù)據(jù)結構以及操作

3.1 Weiss《數(shù)據(jù)結構與算法分析》中簡單的定義

1）性質
在奇數(shù)層上的分支按照第一個關鍵字進行，而在偶數(shù)層上的分支按照第二個關鍵字進行。

2）插入

3）查詢

• 要求精確匹配
• 部分匹配查詢——基于兩個關鍵字中一個關鍵的匹配

上面兩種都是（正交）范圍查詢的特例。
正交范圍查詢給出其第一個關鍵字在一個特殊的值集合之間且第二關鍵字在另一個特殊的的值集合之間的所有項。

3.2 UFL（佛羅里達大學）課程給出的定義

COMPUTATIONAL GEOMETRY
1）性質
分割跟Weiss的定義類似，偶數(shù)層深度用垂直的線進行分割，奇數(shù)層用水平線進行分割。

2）建k-d樹
不斷使用中位數(shù)進行分割，達到平衡。

3）查詢

4）查詢時間分析

• 針對區(qū)域v的查詢，分為三類點

  
  

• 灰結點分析

  
  
  
  
  
  
  
  
  
  
  
  

  這個可以得到G(n) = √n

  
  
  
  

如下是定理：

高維情況：

3.3 一個經(jīng)典的定義

k-d tree算法
1）應用背景

• SIFT算法中做特征點匹配的時候就會利用到k-d樹。而特征點匹配實際上就是一個通過距離函數(shù)在高維矢量之間進行相似性檢索的問題。針對如何快速而準確地找到查詢點的近鄰，現(xiàn)在提出了很多高維空間索引結構和近似查詢的算法，k-d樹就是其中一種。
• 索引結構中相似性查詢有兩種基本的方式：一種是范圍查詢（range searches），另一種是K近鄰查詢（K-neighbor searches）。范圍查詢就是給定查詢點和查詢距離的閾值，從數(shù)據(jù)集中找出所有與查詢點距離小于閾值的數(shù)據(jù)；K近鄰查詢是給定查詢點及正整數(shù)K，從數(shù)據(jù)集中找到距離查詢點最近的K個數(shù)據(jù)，當K=1時，就是最近鄰查詢（nearest neighbor searches）。
• 征匹配算子大致可以分為兩類。一類是線性掃描法，即將數(shù)據(jù)集中的點與查詢點逐一進行距離比較，也就是窮舉，缺點很明顯，就是沒有利用數(shù)據(jù)集本身蘊含的任何結構信息，搜索效率較低，第二類是建立數(shù)據(jù)索引，然后再進行快速匹配。因為實際數(shù)據(jù)一般都會呈現(xiàn)出簇狀的聚類形態(tài)，通過設計有效的索引結構可以大大加快檢索的速度。索引樹屬于第二類，其基本思想就是對搜索空間進行層次劃分。根據(jù)劃分的空間是否有混疊可以分為Clipping和Overlapping兩種。前者劃分空間沒有重疊，其代表就是k-d樹；后者劃分空間相互有交疊，其代表為R樹。（這里只介紹k-d樹）

2）數(shù)據(jù)結構

3）k-d樹的構建

• 1.確定split域的首先該取的值。分別計算x，y方向上數(shù)據(jù)的方差得知x方向上的方差最大，所以split域值首先取0，也就是x軸方向；
• 2.確定Node-data的域值。根據(jù)x軸方向的值2,5,9,4,8,7排序選出中值為7，所以Node-data = （7,2）。這樣，該節(jié)點的分割超平面就是通過（7,2）并垂直于split = 0（x軸）的直線x = 7；

• 3.確定左子空間和右子空間。分割超平面x = 7將整個空間分為兩部分，如圖2所示。x < = 7的部分為左子空間，包含3個節(jié)點{（2,3），（5,4），（4,7）}；另一部分為右子空間，包含2個節(jié)點{（9,6），（8,1）}。

  
  
  圖1

k-d樹的構建是一個遞歸的過程。然后對左子空間和右子空間內的數(shù)據(jù)重復根節(jié)點的過程就可以得到下一級子節(jié)點（5,4）和（9,6）（也就是左右子空間的'根'節(jié)點），同時將空間和數(shù)據(jù)集進一步細分。如此反復直到空間中只包含一個數(shù)據(jù)點，如圖2所示。最后生成的k-d樹如圖3所示。

圖2

圖3

4）k-d樹的最鄰近查找算法

4-1）查詢點(2.1, 3.1)
通過二叉搜索，順著搜索路徑很快就能找到最鄰近的近似點，也就是葉子節(jié)點（2,3）。而找到的葉子節(jié)點并不一定就是最鄰近的，最鄰近肯定距離查詢點更近，應該位于以查詢點為圓心且通過葉子節(jié)點的圓域內。為了找到真正的最近鄰，還需要進行'回溯'操作：算法沿搜索路徑反向查找是否有距離查詢點更近的數(shù)據(jù)點。此例中先從（7,2）點開始進行二叉查找，然后到達（5,4），最后到達（2,3），此時搜索路徑中的節(jié)點為<（7,2），（5,4），（2,3）>，首先以（2,3）作為當前最近鄰點，計算其到查詢點（2.1,3.1）的距離為0.1414，然后回溯到其父節(jié)點（5,4），并判斷在該父節(jié)點的其他子節(jié)點空間中是否有距離查詢點更近的數(shù)據(jù)點。以（2.1,3.1）為圓心，以0.1414為半徑畫圓，如圖4所示。發(fā)現(xiàn)該圓并不和超平面y = 4交割，因此不用進入（5,4）節(jié)點右子空間中去搜索。

4-2）查詢點(2, 4.5)
同樣先進行二叉查找，先從（7,2）查找到（5,4）節(jié)點，在進行查找時是由y = 4為分割超平面的，由于查找點為y值為4.5，因此進入右子空間查找到（4,7），形成搜索路徑<（7,2），（5,4），（4,7）>，?。?,7）為當前最近鄰點，計算其與目標查找點的距離為3.202。然后回溯到（5,4），計算其與查找點之間的距離為3.041。以（2，4.5）為圓心，以3.041為半徑作圓，如圖5所示。可見該圓和y = 4超平面交割，所以需要進入（5,4）左子空間進行查找。此時需將（2,3）節(jié)點加入搜索路徑中得<（7,2），（2,3）>?；厮葜粒?,3）葉子節(jié)點，（2,3）距離（2,4.5）比（5,4）要近，所以最近鄰點更新為（2，3），最近距離更新為1.5?；厮葜粒?,2），以（2,4.5）為圓心1.5為半徑作圓，并不和x = 7分割超平面交割，如圖6所示。至此，搜索路徑回溯完。返回最近鄰點（2,3），最近距離1.5。