KD-Tree

A kd-tree is a space partitioning data structure for organizing points in k-dimensional space. It partitions data along different axes at each level for quick searching.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Node {
  int[] point; 
  Node left, right;

  public Node(int[] point) {
    this.point = point;
  }
}

public Node construct(int[][] points, int depth) {
  if (points.length == 0) {
    return null;
  }

  int axis = depth % k; // k is dimension
  int median = findMedian(points, axis);

  Node node = new Node(points[median]);

  node.left = construct(pointsLeft(points, axis, median), depth+1);
  node.right = construct(pointsRight(points, axis, median), depth+1);

  return node;
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Node {
  vector<double> point;
  Node* left;
  Node* right;
};

Node* construct(vector<vector<double>>& points, int depth) {

  if (points.empty()) {
    return nullptr;
  }

  int axis = depth % k;

  int median = findMedian(points, axis);

  Node* node = new Node{points[median]}; 
  node->left = construct(pointsLeft(points, axis, median), depth+1);
  node->right = construct(pointsRight(points, axis, median), depth+1);

  return node;
}

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Node:
  def __init__(self, point):
    self.point = point
    self.left = None
    self.right = None
    
def construct(points, depth):

  if not points:
    return None

  axis = depth % k
  
  median = find_median(points, axis)  

  node = Node(points[median])
  node.left = construct(points_left(points, axis, median), depth+1)
  node.right = construct(points_right(points, axis, median), depth+1)

  return node

Kd-trees partition space for fast searching, nearest neighbors, and related geomtry problems.

A k-d tree, short for k-dimensional tree, is a space-partitioning data structure used for organizing points in a k-dimensional space. It is useful in various applications, like searches involving multi-dimensional keys, nearest neighbor queries, and range searches. The tree is built by selecting one dimension at each level of the tree and splitting the data at the median value along that dimension.

The main advantage of a k-d tree is that it enables efficient search operations, generally improving performance over linear search.

Example Code

Below are basic examples for constructing a k-d tree with points in 2D space.

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Node {
    int[] point;
    Node left, right;
    int axis;

    public Node(int[] point, int axis) {
        this.point = point;
        this.axis = axis;
    }
}

public class KDTree {
    Node root;

    // Insert point
    public Node insert(int[] point, Node node, int axis) {
        // Implementation here
        return node;
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
using namespace std;

struct Node {
    vector<int> point;
    Node* left;
    Node* right;
    int axis;

    Node(vector<int> point, int axis) : point(point), axis(axis), left(nullptr), right(nullptr) {}
};

class KDTree {
public:
    Node* root;

    // Insert point
    Node* insert(vector<int> point, Node* node, int axis) {
        // Implementation here
        return node;
    }
};

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Node:
    def __init__(self, point, axis):
        self.point = point
        self.axis = axis
        self.left = None
        self.right = None

class KDTree:
    def __init__(self):
        self.root = None

    # Insert point
    def insert(self, point, node=None, axis=0):
        # Implementation here
        return node

These code snippets offer the basic structure for a k-d tree, specifying the properties and parameters that each node should have. However, they don’t include the complete logic for inserting or searching for points.