KD Trees in Java

Yasin Cakal

K-D Trees (also known as K-dimensional Trees) are a data structure used for efficient storage and retrieval of data in a multidimensional space. They are used for solving problems such as nearest neighbor search, as well as range search and nearest neighbor search in higher dimensions. K-D Trees are a type of binary tree that is used to store data points in a multi-dimensional space. The data points are stored in a tree such that each node of the tree represents a single data point. The data points are sorted in a way that the left subtree contains points that are less than the node’s data, and the right subtree contains points that are greater than the node’s data.

In this article, we will be discussing the basic concepts of K-D Trees and how to implement them in Java. We will also discuss the time and space complexities of the operations associated with K-D Trees.

What is a KD Tree?

How Does a KD Tree Work?

K-D Trees are constructed using two simple steps. First, the data points are sorted along one of the dimensions (i.e., the x-axis, y-axis, etc.). This sorting process is repeated until the data points are sorted in all dimensions.

Once the data points are sorted, the tree is constructed by creating a node for each data point. The nodes are connected to form a tree structure, with each node having two children (left and right). The left child contains the data points that are less than the node’s data, and the right child contains the data points that are greater than the node’s data. This process is repeated until all the data points are added to the tree.

Time and Space Complexity

K-D Trees have an average time complexity of O(log n) for insert, delete, and search operations, where n is the number of data points stored in the tree. The worst case time complexity is O(n), which occurs when the tree is unbalanced.

The space complexity for K-D Trees is O(n), since the entire tree must be stored in memory.

KD Tree Implementation in Java

Now that we have discussed the basic concepts of K-D Trees, let’s look at how to implement them in Java. We will be using the following Java code to demonstrate how to construct a K-D Tree, as well as how to perform the insert, delete, and search operations.

// A simple class to represent a point in the K-D Tree
class Point {
    double x;
    double y;
    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
}

// The K-D Tree class
class KDTree {
    Node root; // The root node of the tree

    // A node of the K-D Tree
    class Node {
        Point point; // The data point stored in this node
        Node left; // The left child node
        Node right; // The right child node

        public Node(Point point) {
            this.point = point;
            this.left = null;
            this.right = null;
        }
    }

    // Constructor
    public KDTree() {
        this.root = null;
    }

    // Method to insert a new data point into the tree
    public void insert(Point point) {
        // Create a new node for the data point
        Node newNode = new Node(point);

        // If the tree is empty, set the new node as the root
        if (root == null) {
            root = newNode;
            return;
        }

        // Start at the root and traverse the tree to find the correct
        // place to insert the new node
        Node current = root;
        Node parent = null;
        int level = 0; // The level of the tree (0 is the root)

        while (true) {
            parent = current;

            // Check if the new node should be inserted in the left subtree
            if (point.x < current.point.x) {
                current = current.left;

                // If the left subtree is empty, insert the new node here
                if (current == null) {
                    parent.left = newNode;
                    return;
                }
            }
            // Otherwise, insert the new node in the right subtree
            else {
                current = current.right;

                // If the right subtree is empty, insert the new node here
                if (current == null) {
                    parent.right = newNode;
                    return;
                }
            }

            level++; // Increase the level of the tree
        }
    }

    // Method to delete a data point from the tree
    public void delete(Point point) {
        // Start at the root and traverse the tree to find the node to be deleted
        Node current = root;
        Node parent = null;
        int level = 0; // The level of the tree (0 is the root)

        while (true) {
            if (point.x == current.point.x && point.y == current.point.y) {
                break; // Found the node to be deleted
            }

            parent = current;

            // Check if the node to be deleted is in the left subtree
            if (point.x < current.point.x) {
                current = current.left;
            }
            // Otherwise, it is in the right subtree
            else {
                current = current.right;
            }

            level++; // Increase the level of the tree
        }

        // If the node to be deleted is a leaf node, simply delete it
        if (current.left == null && current.right == null) {
            // Check if the node to be deleted is a left child or a right child
            if (parent.left == current) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }
        // If the node to be deleted has one child, replace it with its child
        else if (current.left == null || current.right == null) {
            // Check if the node to be deleted is a left child or a right child
            if (parent.left == current) {
                parent.left = (current.left != null) ? current.left : current.right;
            } else {
                parent.right = (current.left != null) ? current.left : current.right;
            }
        }
        // If the node to be deleted has two children, replace it with its in-order successor
        else {
            Node successor = getSuccessor(current);

            // Replace the node to be deleted with its successor
            if (parent.left == current) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }

            successor.left = current.left;
        }
    }

    // Method to search for a data point in the tree
    public boolean search(Point point) {
        // Start at the root and traverse the tree to find the data point
        Node current = root;
        int level = 0; // The level of the tree (0 is the root)

        while (true) {
            // Check if the data point is found
            if (point.x == current.point.x && point.y == current.point.y) {
                return true;
            }

            // Check if the data point is in the left subtree
            if (point.x < current.point.x) {
                current = current.left;
            }
            // Otherwise, check if it is in the right subtree
            else {
                current = current.right;
            }

            // If the node is null, the data point is not in the tree
            if (current == null) {
                return false;
            }

            level++; // Increase the level of the tree
        }
    }

    // Helper method to get the in-order successor of a node
    private Node getSuccessor(Node node) {
        Node parent = node;
        Node current = node.right;

        // Find the in-order successor in the right subtree
        while (current != null) {
            parent = current;
            current = current.left;
        }

        // If the successor has a right child, set its parent to its left child
        if (parent != node.right) {
            parent.left = node.right;
            node.right = null;
        }

        return parent;
    }
}

Conclusion

K-D Trees are a data structure used for efficient storage and retrieval of data in a multidimensional space. They are used for solving problems such as nearest neighbor search, as well as range search and nearest neighbor search in higher dimensions. K-D Trees have an average time complexity of O(log n) for insert, delete, and search operations, where n is the number of data points stored in the tree. The worst case time complexity is O(n), which occurs when the tree is unbalanced. The space complexity for K-D Trees is O(n), since the entire tree must be stored in memory.

In this article, we discussed the basics of K-D Trees, how to implement them in Java, and their associated time and space complexities. We also provided a complete implementation of K-D Trees in Java, as well as a few examples of how to use the data structure.

Exercises

Write a function to find the minimum value in a K-D Tree.

// A function to find the minimum value in a K-D Tree
public static double findMin(Node root) {
    double min = root.point.x; // Initialize the min to the root's x-value
    Node current = root; // Start at the root node

    while (current != null) { // Traverse the tree until we reach a leaf node
        // Check if the current node's x-value is less than the min
        if (current.point.x < min) {
            min = current.point.x; // Update the min
        }

        // Traverse to the left subtree if the current node's x-value is greater than the min
        if (current.point.x > min) {
            current = current.left;
        }
        // Otherwise, traverse to the right subtree
        else {
            current = current.right;
        }
    }

    return min; // Return the min value
}

Write a function to check if a K-D Tree is balanced.

// A function to check if a K-D Tree is balanced
public static boolean isBalanced(Node root) {
    // Check if the tree is empty
    if (root == null) {
        return true;
    }

    // Get the height of the left and right subtrees
    int leftHeight = getHeight(root.left);
    int rightHeight = getHeight(root.right);

    // Check if the absolute difference between the left and right subtree heights is less than or equal to 1
    if (Math.abs(leftHeight - rightHeight) <= 1) {
        // Check if the left subtree is balanced
        if (isBalanced(root.left)) {
            // Check if the right subtree is balanced
            if (isBalanced(root.right)) {
                return true; // The tree is balanced
            }
        }
    }

    return false; // The tree is not balanced
}

// A helper function to get the height of a subtree
private static int getHeight(Node node) {
    if (node == null) { // Base case
        return 0;
    }

    // Get the heights of the left and right subtrees
    int leftHeight = getHeight(node.left);
    int rightHeight = getHeight(node.right);

    // Return the maximum height
    if (leftHeight > rightHeight) {
        return leftHeight + 1;
    } else {
        return rightHeight + 1;
    }
}

Write a function to find the closest data point to a given point in a K-D Tree.

// A function to find the closest data point to a given point in a K-D Tree
public static Point nearestNeighbor(Node root, Point point) {
    // Check if the tree is empty
    if (root == null) {
        return null;
    }

    // Initialize the distance to the maximum value
    double minDistance = Double.MAX_VALUE;
    Point nearest = null; // The nearest data point

    // Start at the root and traverse the tree to find the closest point
    Node current = root;
    int level = 0; // The level of the tree (0 is the root)

    while (true) {
        double distance = getDistance(point, current.point); // Get the distance between the given point and the current node's point

        // Check if the current point is closer than the nearest point
        if (distance < minDistance) {
            minDistance = distance; // Update the minimum distance
            nearest = current.point; // Update the nearest point
        }

        // Check if the given point is in the left subtree
        if (point.x < current.point.x) {
            current = current.left;
        }
        // Otherwise, check if it is in the right subtree
        else {
            current = current.right;
        }

        // If the node is null, we have reached a leaf node
        if (current == null) {
            break;
        }

        level++; // Increase the level of the tree
    }

    return nearest; // Return the nearest data point
}

// A helper function to get the distance between two points
private static double getDistance(Point p1, Point p2) {
    // Use the Euclidean distance formula to calculate the distance
    double xDiff = p1.x - p2.x;
    double yDiff = p1.y - p2.y;
    return Math.sqrt(xDiff * xDiff + yDiff * yDiff);
}

Write a function to find the maximum value in a K-D Tree.

// A function to find the maximum value in a K-D Tree
public static double findMax(Node root) {
    double max = root.point.x; // Initialize the max to the root's x-value
    Node current = root; // Start at the root node

    while (current != null) { // Traverse the tree until we reach a leaf node
        // Check if the current node's x-value is greater than the max
        if (current.point.x > max) {
            max = current.point.x; // Update the max
        }

        // Traverse to the right subtree if the current node's x-value is less than the max
        if (current.point.x < max) {
            current = current.right;
        }
        // Otherwise, traverse to the left subtree
        else {
            current = current.left;
        }
    }

    return max; // Return the max value
}

Write a function to find the sum of all the data points in a K-D Tree.

// A function to find the sum of all the data points in a K-D Tree
public static double sum(Node root) {
    // Check if the tree is empty
    if (root == null) {
        return 0;
    }

    // Recursively calculate the sum of the left and right subtrees
    double leftSum = sum(root.left);
    double rightSum = sum(root.right);

    return root.point.x + leftSum + rightSum; // Return the sum of the root's x-value and the sums of the left and right subtrees
}

Data Structures and Algorithms with Java

Participants 681