k-d樹

在計算機科學里，k-d樹可以使用在多種應用場合，如多維鍵值搜索。k-d樹是空間二叉樹的一種特殊情況。

k-d樹是每個節點都為k維點的二叉樹。所有非葉子節點可以視作用一個超平面把空間分割成兩部分。在超平面左邊的點代表節點的左子樹，在超平面右邊的點代表節點的右子樹。超平面的方向可以用下述方法來選擇：每個節點都與k維中垂直於超平面的那一維有關。因此，如果選擇按照x軸劃分，所有x值小於指定值的節點都會出現在左子樹，所有x值大於指定值的節點都會出現在右子樹。這樣，超平面可以用該x值來確定，其法矢為x軸的單位向量。