1. Introduction

A KD-Tree, short for K-dimensional tree, is a space-partitioning data structure useful for organizing points in a K-dimensional space. KD-trees are especially handy for applications involving multidimensional search keys, such as range searches and nearest neighbor searches. Each node in a KD-Tree splits the input point set into two half-spaces.

2. Program Steps

1. Define a Point class to represent K-dimensional points.

2. Define the KDTree class with a Node inner class.

3. Implement the methods insert, and search.

4. Test the KDTree with sample points.

3. Code Program

class KDTree {
    static class Node {
        int[] point;
        Node left, right;
        int splitDimension;

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

    Node root;
    int k;

    public KDTree(int k) {
        this.k = k;
    }

    public void insert(int[] point) {
        root = insert(root, point, 0);
    }

    private Node insert(Node root, int[] point, int depth) {
        if (root == null) {
            return new Node(point, depth % k);
        }

        if (point[root.splitDimension] < root.point[root.splitDimension]) {
            root.left = insert(root.left, point, depth + 1);
        } else {
            root.right = insert(root.right, point, depth + 1);
        }

        return root;
    }

    public boolean search(int[] point) {
        return search(root, point, 0);
    }

    private boolean search(Node root, int[] point, int depth) {
        if (root == null) {
            return false;
        }

        if (isEqual(point, root.point)) {
            return true;
        }

        if (point[depth % k] < root.point[depth % k]) {
            return search(root.left, point, depth + 1);
        } else {
            return search(root.right, point, depth + 1);
        }
    }

    private boolean isEqual(int[] point1, int[] point2) {
        for (int i = 0; i < k; i++) {
            if (point1[i] != point2[i]) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        KDTree tree = new KDTree(2);
        tree.insert(new int[]{3, 6});
        tree.insert(new int[]{17, 15});
        tree.insert(new int[]{13, 15});
        tree.insert(new int[]{6, 12});

        System.out.println(tree.search(new int[]{3, 6})); // true
        System.out.println(tree.search(new int[]{3, 8})); // false
    }
}

Output:

true
false

4. Step By Step Explanation

1. KDTree class has an inner Node class that represents a node in the KD-Tree. Each node contains a point, references to its left and right children, and the dimension on which it splits the space.

2. The Point class has been replaced by an integer array for flexibility. It can store coordinates in multiple dimensions.

3. The insert method recursively inserts a point in the tree, alternating the split dimension as it goes deeper into the tree.

4. The search method recursively searches for a point in the tree, using the split dimension to decide whether to explore the left or right child.

5. The isEqual method compares two points for equality.

6. In the main method, a 2D KD-Tree is created and populated with sample points. Then, two search operations are performed, one of which finds a match, while the other doesn't.

The KD-Tree efficiently manages points in a multidimensional space, enabling faster queries than traditional linear methods for many operations.