#99 一個特別的資料結構 K-D 樹

前陣子和團隊成員討論工作內容時，看到了一位特別的資料結構．老實說，我以前不知道這個結構，因此特別去查了資料，然後將它的內容寫在這裡．

在電腦科學中，組織數據的方式對於快速查找和使用數據至關重要。其中一種特別的數據結構稱為 K-D 樹（K-Dimension tree），主要用於在多維空間中組織點，非常適合應用於機器學習、電腦圖形和資料庫搜索等領域。現在，讓我們來看看 K-D 樹是什麼、為什麼被發明、它可以解決哪些問題，以及如何編寫 K-D 樹的程式碼。

假設你有一組在 2 維空間中的點（例如地圖上的座標），地圖是由 X, Y 軸所組成的．當你希望快速找到某個位置的最近點，K-D 樹就是一個很好的工具．K-D 樹是一種二元搜尋樹，它在具有 k 維空間中將點組織起來的能力。每一層代表一個維度，並且通過交替各個維度的分割，可以使得在空間內找到鄰近點變得更加容易。

所以, K 代表的是維度數，以地圖來說，K=2．

假設你有一組城市地標的座標，並希望快速找到離給定位置最近的地標，假設你有台北 101 的座標，要尋找附近著名的景點座標。在沒有任何其他資料結構的幫助下，每次搜尋都需要比較每一個地點，計算距離，然後依照 "附近" 的定義來決定那些景點的座標符合要求．如果一個地圖裡有成千上萬甚至數百萬個景點座標時，則尋找會非常耗時。K-D 樹就是為了解決這個問題而發明的。它的核心理念是將座標進行合理的排列，以便在搜尋時可以排除大量不相關的點。K-D 樹最早由 Jon Bentley 在 1975 年發明，並在需要快速搜尋和排序空間數據的應用中廣泛使用，例如 最近鄰搜尋（找到最近的點）。

接下來談談 K-D 樹如何建立以及如何利用它來搜尋.

1.建立過程 - 首先選擇一個維度作為 "分割" 維度。為了簡單起見，假設在 2D 空間中，所以我們有兩個維度：X 和 Y。 - 在樹的根節點上，根據 X 座標分割點。 - 找到 X 值的中位數，並將其作為 "支點" (pivot) 來劃分。把其他座標點 X 大於中位數的放在左邊，小於中位數的放在右邊。 - 接下來，在每一層上交替進行維度分割。下一層使用 Y 座標進行分割，然後再回到 x 座標，以此類推。

因此，樹的每一層就是由不同的維度來形成，以地圖為例，就是 X , Y , X , Y 以此類推，一直到把所有的資料都寫入到樹裡.

2. 尋找過程 - 若要找到最近的鄰居，將目標點與樹的每一層進行比較，根據點是更接近左子樹還是右子樹來選擇路徑。 - 當搜尋到 LEAF 節點時，檢查距離以確認它是否為目前發現的最近點。 - 通過使用樹的結構，我們不需要查看每一個點，這使得搜尋比直接比較更快。

我們將上述的想法利用程式碼來呈現時，它看起來如下:

	class Node {
	int[] point; // 儲存 (x, y) 座標
	Node left; // 左子節點
	Node right; // 右子節點
	public Node(int[] point) {
	this.point = point;
	this.left = null;
	this.right = null;
	}
	}
	public class KDTree {
	public Node buildKDTree(int[][] points, int depth) {
	if (points.length == 0) {
	return null;
	}
	int k = points[0].length; // 維度數（在此例中為 2）
	int axis = depth % k; // 在 x 軸 (0) 和 y 軸 (1) 之間交替
	// 根據當前軸排序點並選擇中位數
	Arrays.sort(points, Comparator.comparingInt(a -> a[axis]));
	int medianIndex = points.length / 2;
	// 遞迴建立樹
	Node node = new Node(points[medianIndex]);
	node.left = buildKDTree(Arrays.copyOfRange(points, 0, medianIndex), depth + 1);
	node.right = buildKDTree(Arrays.copyOfRange(points, medianIndex + 1, points.length), depth + 1);
	return node;
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub

以下是使用 KD 權的程式碼範例

	public class KDTreeSearch {
	public static double distanceSquared(int[] point1, int[] point2) {
	int dx = point1[0] - point2[0];
	int dy = point1[1] - point2[1];
	return dx * dx + dy * dy;
	}
	public static Node nearestNeighbor(Node root, int[] target, int depth, Node best, double bestDist) {
	if (root == null) {
	return best;
	}
	int k = target.length;
	int axis = depth % k;
	// 當前點
	double d = distanceSquared(target, root.point);
	if (best == null || d < bestDist) {
	best = root;
	bestDist = d;
	}
	Node closerNode = (target[axis] < root.point[axis]) ? root.left : root.right;
	Node fartherNode = (target[axis] < root.point[axis]) ? root.right : root.left;
	// 搜索更近的一側
	best = nearestNeighbor(closerNode, target, depth + 1, best, bestDist);
	if ((target[axis] - root.point[axis]) * (target[axis] - root.point[axis]) < bestDist) {
	best = nearestNeighbor(fartherNode, target, depth + 1, best, bestDist);
	}
	return best;
	}
	public static void main(String[] args) {
	int[][] points = { {2, 3}, {5, 4}, {9, 6}, {4, 7}, {8, 1}, {7, 2} };
	KDTree kdTree = new KDTree();
	Node root = kdTree.buildKDTree(points, 0);
	int[] target = {9, 2};
	Node nearest = nearestNeighbor(root, target, 0, null, Double.MAX_VALUE);
	System.out.println("最近的點: (" + nearest.point[0] + ", " + nearest.point[1] + ")");
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub

K-D 樹是一種強大的資料結構，可以幫助我們在多維空間中快速找到點。通過有效組織數據，K-D 樹使得進行最近鄰搜尋和範圍搜尋變得更快。當你在地理位置相關的應用中尋找附近的選項時，K-D 樹很可能就在背後默默運作。