K-Dimensional (K-D) Trees in Datastructures

The K-D is a multi-dimensional binary search tree. It is defined as a data structure for storing multikey records. This structure has been implemented to solve a number of "geometric" problems in statistics and data analysis.

A k-d tree (short for k-dimensional tree) is defined as a space-partitioning data structure for organizing points in a k-dimensional space. Data structure k-d trees are implemented for several applications, for example, searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches). k-d trees are treated as a special case of binary space partitioning trees.

Properties of K-D Trees

Following are the properties of k-d trees:

• The depth of the k-d tree is O(log n) where n is the number of points.
• Each node in the tree contains a k-dimensional point and pointers to the left and right child nodes.
• The choice of the axis at each level of the tree follows a cycle through the axes.
• And choice of axis at each level will affect's the tree's performance in terms of search speed.

Operations on K-D Trees

Following are the operations that can be performed on k-d trees:

• Insert(x): Insert a point x into the k-d tree.
• Delete(x): Delete a point x from the k-d tree.
• Search(x): Search for a point x in the k-d tree.

Construction of K-D Trees

The construction of k-d trees is done by using recursive partitioning. The steps to construct a k-d tree are as follows:

• Choose the axis of the splitting plane.
• Choose the median as the pivot element.
• Split the points into two sets: one set contains points less than the median and the other set contains points greater than the median.
• Repeat the above steps for the left and right subtrees.

Now, let's code the construction of k-d trees:

Code to Construct K-D Trees and Insert Operation

We performed insert operation in order to construct a k-d tree.

Following is the example code to construct a k-d tree in C, C++, Java, and Python:

 #include <stdio.h> #include <stdlib.h> // Structure to represent a node of the k-d tree struct Node { int point[2]; struct Node *left, *right; }; // Function to create a new node struct Node* newNode(int arr[]) { struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->point[0] = arr[0]; temp->point[1] = arr[1]; temp->left = temp->right = NULL; return temp; } // Function to insert a new node struct Node* insertNode(struct Node* root, int point[], unsigned depth) { if (root == NULL) return newNode(point); unsigned cd = depth % 2; if (point[cd] < (root->point[cd])) root->left = insertNode(root->left, point, depth + 1); else root->right = insertNode(root->right, point, depth + 1); return root; } // Function to construct a k-d tree struct Node* constructKdTree(int points[][2], int n) { struct Node* root = NULL; for (int i = 0; i < n; i++) root = insertNode(root, points[i], 0); return root; } // Function to print the k-d tree (Preorder Traversal) void printKdTree(struct Node* root) { if (root == NULL) return; printf("(%d, %d)\n", root->point[0], root->point[1]); printKdTree(root->left); printKdTree(root->right); } // Main function int main() { int points[][2] = {{3, 6}, {17, 15}, {13, 15}, {6, 12}, {9, 1}, {2, 7}, {10, 19}}; int n = sizeof(points) / sizeof(points[0]); struct Node* root = constructKdTree(points, n); printKdTree(root); return 0; } 

 (3, 6) (2, 7) (17, 15) (13, 15) (6, 12) (9, 1) (10, 19) 

 // C++ program to construct a k-d tree #include <iostream> using namespace std; // Structure to represent a node of the k-d tree struct Node { int point[2]; Node *left, *right; }; // Function to create a new node Node* newNode(int arr[]) { Node* temp = new Node; temp->point[0] = arr[0]; temp->point[1] = arr[1]; temp->left = temp->right = NULL; return temp; } // Function to insert a new node Node* insertNode(Node* root, int point[], unsigned depth) { if (root == NULL) return newNode(point); unsigned cd = depth % 2; if (point[cd] < (root->point[cd])) root->left = insertNode(root->left, point, depth + 1); else root->right = insertNode(root->right, point, depth + 1); return root; } // Function to construct a k-d tree Node* constructKdTree(int points[][2], int n) { Node* root = NULL; for (int i = 0; i < n; i++) root = insertNode(root, points[i], 0); return root; } // Function to print the k-d tree void printKdTree(Node* root) { if (root == NULL) return; cout << "(" << root->point[0] << ", " << root->point[1] << ")" << endl; printKdTree(root->left); printKdTree(root->right); } // Main function int main() { int points[][2] = {{3, 6}, {17, 15}, {13, 15}, {6, 12}, {9, 1}, {2, 7}, {10, 19}}; int n = sizeof(points) / sizeof(points[0]); Node* root = constructKdTree(points, n); printKdTree(root); return 0; } 

 (3, 6) (2, 7) (17, 15) (13, 15) (6, 12) (9, 1) (10, 19) 

 // Java program to construct a k-d tree class Node { int[] point; Node left, right; Node(int[] point) { this.point = point; this.left = this.right = null; } } public class KdTree { Node root; Node insertNode(Node root, int[] point, int depth) { if (root == null) return new Node(point); int cd = depth % 2; if (point[cd] < root.point[cd]) root.left = insertNode(root.left, point, depth + 1); else root.right = insertNode(root.right, point, depth + 1); return root; } Node constructKdTree(int[][] points) { for (int i = 0; i < points.length; i++) root = insertNode(root, points[i], 0); return root; } void printKdTree(Node root) { if (root == null) return; System.out.println("(" + root.point[0] + ", " + root.point[1] + ")"); printKdTree(root.left); printKdTree(root.right); } public static void main(String[] args) { int[][] points = {{3, 6}, {17, 15}, {13, 15}, {6, 12}, {9, 1}, {2, 7}, {10, 19}}; KdTree tree = new KdTree(); tree.constructKdTree(points); tree.printKdTree(tree.root); } } 

 (3, 6) (2, 7) (17, 15) (13, 15) (6, 12) (9, 1) (10, 19) 

 # Python program to construct a k-d tree class Node: def __init__(self, point): self.point = point self.left = None self.right = None def insertNode(root, point, depth): if root is None: return Node(point) cd = depth % 2 if point[cd] < root.point[cd]: root.left = insertNode(root.left, point, depth + 1) else: root.right = insertNode(root.right, point, depth + 1) return root def constructKdTree(points): root = None for point in points: root = insertNode(root, point, 0) return root def printKdTree(root): if root is None: return print("(", root.point[0], ", ", root.point[1], ")") printKdTree(root.left) printKdTree(root.right) points = [[3, 6], [17, 15], [13, 15], [6, 12], [9, 1], [2, 7], [10, 19]] root = constructKdTree(points) printKdTree(root) 

 (3, 6) (2, 7) (17, 15) (13, 15) (6, 12) (9, 1) (10, 19) 

Delete Operation on K-D Trees

The delete operation in k-d trees is performed by following the below steps:

• Find the node to be deleted.
• If the node is a leaf node, delete it directly.
• If the node has only one child, replace the node with its child.
• If the node has two children, find the inorder successor of the node, replace the node with the inorder successor, and delete the inorder successor.

Code to Delete a Node from K-D Trees

Following is the example code to delete a node from k-d trees in C, C++, Java, and Python:

 // C program to delete a node from a k-d tree #include <stdio.h> #include <stdlib.h> // Structure to represent a node of the k-d tree struct Node { int point[2]; struct Node *left, *right; }; // Function to create a new node struct Node* newNode(int arr[]) { struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->point[0] = arr[0]; temp->point[1] = arr[1]; temp->left = temp->right = NULL; return temp; } // Function to insert a new node struct Node* insertNode(struct Node* root, int point[], unsigned depth) { if (root == NULL) return newNode(point); unsigned cd = depth % 2; if (point[cd] < root->point[cd]) root->left = insertNode(root->left, point, depth + 1); else root->right = insertNode(root->right, point, depth + 1); return root; } // Function to find the minimum value node in a k-d tree struct Node* minValueNode(struct Node* root, int d, unsigned depth) { if (root == NULL) return NULL; unsigned cd = depth % 2; if (cd == d) { if (root->left == NULL) return root; return minValueNode(root->left, d, depth + 1); } struct Node* left = minValueNode(root->left, d, depth + 1); struct Node* right = minValueNode(root->right, d, depth + 1); struct Node* min = root; if (left != NULL && left->point[d] < min->point[d]) min = left; if (right != NULL && right->point[d] < min->point[d]) min = right; return min; } // Function to delete a node from the k-d tree struct Node* deleteNode(struct Node* root, int point[], unsigned depth) { if (root == NULL) return NULL; unsigned cd = depth % 2; if (root->point[0] == point[0] && root->point[1] == point[1]) { if (root->right != NULL) { struct Node* min = minValueNode(root->right, cd, depth + 1); root->point[0] = min->point[0]; root->point[1] = min->point[1]; root->right = deleteNode(root->right, min->point, depth + 1); } else if (root->left != NULL) { struct Node* min = minValueNode(root->left, cd, depth + 1); root->point[0] = min->point[0]; root->point[1] = min->point[1]; root->right = deleteNode(root->left, min->point, depth + 1); root->left = NULL; } else { free(root); return NULL; } } else if (point[cd] < root->point[cd]) { root->left = deleteNode(root->left, point, depth + 1); } else { root->right = deleteNode(root->right, point, depth + 1); } return root; } // Function to construct a k-d tree struct Node* constructKdTree(int points[][2], int n) { struct Node* root = NULL; for (int i = 0; i < n; i++) root = insertNode(root, points[i], 0); return root; } // Function to print the k-d tree (Preorder Traversal) void printKdTree(struct Node* root) { if (root == NULL) return; printf("(%d, %d)\n", root->point[0], root->point[1]); printKdTree(root->left); printKdTree(root->right); } // Main function int main() { int points[][2] = {{3, 6}, {17, 15}, {13, 15}, {6, 12}, {9, 1}, {2, 7}, {10, 19}}; int n = sizeof(points) / sizeof(points[0]); struct Node* root = constructKdTree(points, n); printf("K-D Tree before deletion:\n"); printKdTree(root); int deletePoint[] = {13, 15}; // Deleting (13, 15) root = deleteNode(root, deletePoint, 0); printf("K-D Tree after deletion:\n"); printKdTree(root); return 0; } 

 K-D Tree before deletion: (3, 6) (2, 7) (17, 15) (13, 15) (6, 12) (9, 1) (10, 19) K-D Tree after deletion: (3, 6) (2, 7) (17, 15) (6, 12) (9, 1) (10, 19) 

 // C++ program to delete a node from a k-d tree #include <iostream> using namespace std; // Structure to represent a node of the k-d tree struct Node { int point[2]; Node *left, *right; }; // Function to create a new node Node* newNode(int arr[]) { Node* temp = new Node; temp->point[0] = arr[0]; temp->point[1] = arr[1]; temp->left = temp->right = NULL; return temp; } // Function to insert a new node Node* insertNode(Node* root, int point[], unsigned depth) { if (root == NULL) return newNode(point); unsigned cd = depth % 2; if (point[cd] < (root->point[cd])) root->left = insertNode(root->left, point, depth + 1); else root->right = insertNode(root->right, point, depth + 1); return root; } // Function to find the minimum value node Node* minValueNode(Node* root, int d, unsigned depth) { if (root == NULL) return NULL; unsigned cd = depth % 2; if (cd == d) { if (root->left == NULL) return root; return minValueNode(root->left, d, depth + 1); } Node* left = minValueNode(root->left, d, depth + 1); Node* right = minValueNode(root->right, d, depth + 1); Node* min = root; if (left != NULL && left->point[d] < min->point[d]) min = left; if (right != NULL && right->point[d] < min->point[d]) min = right; return min; } // Function to delete a node Node* deleteNode(Node* root, int point[], unsigned depth) { if (root == NULL) return NULL; unsigned cd = depth % 2; if (root->point[0] == point[0] && root->point[1] == point[1]) { if (root->right != NULL) { Node* min = minValueNode(root->right, cd, depth + 1); root->point[0] = min->point[0]; root->point[1] = min->point[1]; root->right = deleteNode(root->right, min->point, depth + 1); } else if (root->left != NULL) { Node* min = minValueNode(root->left, cd, depth + 1); root->point[0] = min->point[0]; root->point[1] = min->point[1]; root->right = deleteNode(root->left, min->point, depth + 1); root->left = NULL; } else return NULL; } else if (point[cd] < root->point[cd]) root->left = deleteNode(root->left, point, depth + 1); else root->right = deleteNode(root->right, point, depth + 1); return root; } // Function to construct a k-d tree Node* constructKdTree(int points[][2], int n) { Node* root = NULL; for (int i = 0; i < n; i++) root = insertNode(root, points[i], 0); return root; } // Function to print the k-d tree void printKdTree(Node* root) { if (root == NULL) return; cout << "(" << root->point[0] << ", " << root->point[1] << ")" << endl; printKdTree(root->left); printKdTree(root->right); } // Main function int main() { int points[][2] = {{3, 6}, {17, 15}, {13, 15}, {6, 12}, {9, 1}, {2, 7}, {10, 19}}; int n = sizeof(points) / sizeof(points[0]); Node* root = constructKdTree(points, n); cout << "K-D Tree before deletion:" << endl; printKdTree(root); root = deleteNode(root, points[2], 0); cout << "K-D Tree after deletion:" << endl; printKdTree(root); return 0; } 

 K-D Tree before deletion: (3, 6) (2, 7) (17, 15) (13, 15) (6, 12) (9, 1) (10, 19) K-D Tree after deletion: (3, 6) (2, 7) (17, 15) (6, 12) (9, 1) (10, 19) 

 // Java program to delete a node from a k-d tree class Node { int[] point; Node left, right; Node(int[] point) { this.point = point; this.left = this.right = null; } } public class KdTree { Node root; Node insertNode(Node root, int[] point, int depth) { if (root == null) return new Node(point); int cd = depth % 2; if (point[cd] < root.point[cd]) root.left = insertNode(root.left, point, depth + 1); else root.right = insertNode(root.right, point, depth + 1); return root; } Node minValueNode(Node root, int d, int depth) { if (root == null) return null; int cd = depth % 2; if (cd == d) { if (root.left == null) return root; return minValueNode(root.left, d, depth + 1); } Node left = minValueNode(root.left, d, depth + 1); Node right = minValueNode(root.right, d, depth + 1); Node min = root; if (left != null && left.point[d] < min.point[d]) min = left; if (right != null && right.point[d] < min.point[d]) min = right; return min; } Node deleteNode(Node root, int[] point, int depth) { if (root == null) return null; int cd = depth % 2; if (root.point[0] == point[0] && root.point[1] == point[1]) { if (root.right != null) { Node min = minValueNode(root.right, cd, depth + 1); root.point[0] = min.point[0]; root.point[1] = min.point[1]; root.right = deleteNode(root.right, min.point, depth + 1); } else if (root.left != null) { Node min = minValueNode(root.left, cd, depth + 1); root.point[0] = min.point[0]; root.point[1] = min.point[1]; root.right = deleteNode(root.left, min.point, depth + 1); root.left = null; } else return null; } else if (point[cd] < root.point[cd]) root.left = deleteNode(root.left, point, depth + 1); else root.right = deleteNode(root.right, point, depth + 1); return root; } void printKdTree(Node root) { if (root == null) return; System.out.println("(" + root.point[0] + ", " + root.point[1] + ")"); printKdTree(root.left); printKdTree(root.right); } public static void main(String[] args) { int[][] points = {{3, 6}, {17, 15}, {13, 15}, {6, 12}, {9, 1}, {2, 7}, {10, 19}}; KdTree tree = new KdTree(); for (int[] point : points) tree.root = tree.insertNode(tree.root, point, 0); System.out.println("K-D Tree before deletion:"); tree.printKdTree(tree.root); tree.root = tree.deleteNode(tree.root, points[2], 0); System.out.println("K-D Tree after deletion:"); tree.printKdTree(tree.root); } } 

 K-D Tree before deletion: (3, 6) (2, 7) (17, 15) (13, 15) (6, 12) (9, 1) (10, 19) K-D Tree after deletion: (3, 6) (2, 7) (17, 15) (6, 12) (9, 1) (10, 19) 

 # Python program to delete a node from a k-d tree class Node: def __init__(self, point): self.point = point self.left = None self.right = None def insertNode(root, point, depth): if root is None: return Node(point) cd = depth % 2 if point[cd] < root.point[cd]: root.left = insertNode(root.left, point, depth + 1) else: root.right = insertNode(root.right, point, depth + 1) return root def minValueNode(root, d, depth): if root is None: return None cd = depth % 2 if cd == d: if root.left is None: return root return minValueNode(root.left, d, depth + 1) left = minValueNode(root.left, d, depth + 1) right = minValueNode(root.right, d, depth + 1) min = root if left is not None and left.point[d] < min.point[d]: min = left if right is not None and right.point[d] < min.point[d]: min = right return min def deleteNode(root, point, depth): if root is None: return None cd = depth % 2 if root.point[0] == point[0] and root.point[1] == point[1]: if root.right is not None: min = minValueNode(root.right, cd, depth + 1) root.point[0] = min.point[0] root.point[1] = min.point[1] root.right = deleteNode(root.right, min.point, depth + 1) elif root.left is not None: min = minValueNode(root.left, cd, depth + 1) root.point[0] = min.point[0] root.point[1] = min.point[1] root.right = deleteNode(root.left, min.point, depth + 1) root.left = None else: return None elif point[cd] < root.point[cd]: root.left = deleteNode(root.left, point, depth + 1) else: root.right = deleteNode(root.right, point, depth + 1) return root def printKdTree(root): if root is None: return print("(", root.point[0], ", ", root.point[1], ")") printKdTree(root.left) printKdTree(root.right) points = [[3, 6], [17, 15], [13, 15], [6, 12], [9, 1], [2, 7], [10, 19]] root = None for point in points: root = insertNode(root, point, 0) print("K-D Tree before deletion:") printKdTree(root) root = deleteNode(root, points[2], 0) print("K-D Tree after deletion:") printKdTree(root) 

 K-D Tree before deletion: (3, 6) (2, 7) (17, 15) (13, 15) (6, 12) (9, 1) (10, 19) K-D Tree after deletion: (3, 6) (2, 7) (17, 15) (6, 12) (9, 1) (10, 19) 

Search Operation on K-D Trees

The search operation in k-d trees is performed by following the below steps:

• Start from the root node.
• If the point is equal to the root node, return the root node.
• If the point is less than the root node, search in the left subtree.
• If the point is greater than the root node, search in the right subtree.

Code to Search a Node in K-D Trees

Following is the example code to search a node in k-d trees in C, C++, Java, and Python:

 #include <stdio.h> #include <stdlib.h> // Structure to represent a node of the k-d tree struct Node { int point[2]; struct Node *left, *right; }; // Function to create a new node struct Node* newNode(int arr[]) { struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->point[0] = arr[0]; temp->point[1] = arr[1]; temp->left = temp->right = NULL; return temp; } // Function to insert a new node struct Node* insertNode(struct Node* root, int point[], unsigned depth) { if (root == NULL) return newNode(point); unsigned cd = depth % 2; if (point[cd] < root->point[cd]) root->left = insertNode(root->left, point, depth + 1); else root->right = insertNode(root->right, point, depth + 1); return root; } // Function to search a node in a k-d tree struct Node* searchNode(struct Node* root, int point[], unsigned depth) { if (root == NULL) return NULL; if (root->point[0] == point[0] && root->point[1] == point[1]) return root; unsigned cd = depth % 2; if (point[cd] < root->point[cd]) return searchNode(root->left, point, depth + 1); return searchNode(root->right, point, depth + 1); } // Function to construct a k-d tree struct Node* constructKdTree(int points[][2], int n) { struct Node* root = NULL; for (int i = 0; i < n; i++) root = insertNode(root, points[i], 0); return root; } // Function to free memory allocated for the k-d tree void freeKdTree(struct Node* root) { if (root == NULL) return; freeKdTree(root->left); freeKdTree(root->right); free(root); } // Main function int main() { int points[][2] = {{3, 6}, {17, 15}, {13, 15}, {6, 12}, {9, 1}, {2, 7}, {10, 19}}; int n = sizeof(points) / sizeof(points[0]); struct Node* root = constructKdTree(points, n); int searchPoint[] = {13, 15}; // Searching for (13, 15) struct Node* node = searchNode(root, searchPoint, 0); if (node != NULL) printf("Node found: (%d, %d)\n", node->point[0], node->point[1]); else printf("Node not found\n"); // Free allocated memory freeKdTree(root); return 0; } 

 Node found: (13, 15) 

 // C++ program to search a node in a k-d tree #include <iostream> using namespace std; // Structure to represent a node of the k-d tree struct Node { int point[2]; Node *left, *right; }; // Function to create a new node Node* newNode(int arr[]) { Node* temp = new Node; temp->point[0] = arr[0]; temp->point[1] = arr[1]; temp->left = temp->right = NULL; return temp; } // Function to insert a new node Node* insertNode(Node* root, int point[], unsigned depth) { if (root == NULL) return newNode(point); unsigned cd = depth % 2; if (point[cd] < (root->point[cd])) root->left = insertNode(root->left, point, depth + 1); else root->right = insertNode(root->right, point, depth + 1); return root; } // Function to search a node Node* searchNode(Node* root, int point[], unsigned depth) { if (root == NULL) return NULL; unsigned cd = depth % 2; if (root->point[0] == point[0] && root->point[1] == point[1]) return root; if (point[cd] < root->point[cd]) return searchNode(root->left, point, depth + 1); return searchNode(root->right, point, depth + 1); } // Function to construct a k-d tree Node* constructKdTree(int points[][2], int n) { Node* root = NULL; for (int i = 0; i < n; i++) root = insertNode(root, points[i], 0); return root; } // Function to print the k-d tree void printKdTree(Node* root) { if (root == NULL) return; cout << "(" << root->point[0] << ", " << root->point[1] << ")" << endl; printKdTree(root->left); printKdTree(root->right); } // Main function int main() { int points[][2] = {{3, 6}, {17, 15}, {13, 15}, {6, 12}, {9, 1}, {2, 7}, {10, 19}}; int n = sizeof(points) / sizeof(points[0]); Node* root = constructKdTree(points, n); Node* node = searchNode(root, points[2], 0); if (node != NULL) cout << "Node found: (" << node->point[0] << ", " << node->point[1] << ")" << endl; else cout << "Node not found" << endl; return 0; } 

 Node found: (13, 15) 

 // Java program to search a node in a k-d tree class Node { int[] point; Node left, right; Node(int[] point) { this.point = point; this.left = this.right = null; } } public class KdTree { Node root; Node insertNode(Node root, int[] point, int depth) { if (root == null) return new Node(point); int cd = depth % 2; if (point[cd] < root.point[cd]) root.left = insertNode(root.left, point, depth + 1); else root.right = insertNode(root.right, point, depth + 1); return root; } Node searchNode(Node root, int[] point, int depth) { if (root == null) return null; int cd = depth % 2; if (root.point[0] == point[0] && root.point[1] == point[1]) return root; if (point[cd] < root.point[cd]) return searchNode(root.left, point, depth + 1); return searchNode(root.right, point, depth + 1); } void printKdTree(Node root) { if (root == null) return; System.out.println("(" + root.point[0] + ", " + root.point[1] + ")"); printKdTree(root.left); printKdTree(root.right); } public static void main(String[] args) { int[][] points = {{3, 6}, {17, 15}, {13, 15}, {6, 12}, {9, 1}, {2, 7}, {10, 19}}; KdTree tree = new KdTree(); for (int[] point : points) tree.root = tree.insertNode(tree.root, point, 0); Node node = tree.searchNode(tree.root, points[2], 0); if (node != null) System.out.println("Node found: (" + node.point[0] + ", " + node.point[1] + ")"); else System.out.println("Node not found"); } } 

 Node found: (13, 15) 

 # Python program to search a node in a k-d tree class Node: def __init__(self, point): self.point = point self.left = None self.right = None def insertNode(root, point, depth): if root is None: return Node(point) cd = depth % 2 if point[cd] < root.point[cd]: root.left = insertNode(root.left, point, depth + 1) else: root.right = insertNode(root.right, point, depth + 1) return root def searchNode(root, point, depth): if root is None: return None cd = depth % 2 if root.point[0] == point[0] and root.point[1] == point[1]: return root if point[cd] < root.point[cd]: return searchNode(root.left, point, depth + 1) return searchNode(root.right, point, depth + 1) def printKdTree(root): if root is None: return print("(", root.point[0], ", ", root.point[1], ")") printKdTree(root.left) printKdTree(root.right) points = [[3, 6], [17, 15], [13, 15], [6, 12], [9, 1], [2, 7], [10, 19]] root = None for point in points: root = insertNode(root, point, 0) node = searchNode(root, points[2], 0) if node is not None: print("Node found: (", node.point[0], ", ", node.point[1], ")") else: print("Node not found") 

 Node found: (13, 15) 

Time Complexity of K-D Trees

The time complexity of k-d trees for various operations is as follows:

• Insertion: The time complexity of inserting a node in a k-d tree is O(log n), where n is the number of nodes in the tree.
• Deletion: O(log n).
• Search: O(log n).

Applications of K-D Trees

K-D trees are used in the following applications:

• Nearest Neighbor Search: K-D trees are used for finding the nearest neighbor of a given point in a k-dimensional space.
• Range Search: K-D trees are used to find all points within a given range of a query point.
• Approximate Nearest Neighbor Search: K-D trees are used to find an approximate nearest neighbor of a given point in a k-dimensional space.
• Image Processing: K-D trees are used in image processing to find similar images.

Conclusion

In this chapter, we discussed k-d trees, which are a data structure used for storing k-dimensional points. We discussed the construction of k-d trees, operations on k-d trees, and the time complexity of k-d trees. We also provided example code to construct, insert, delete, and search nodes in k-d trees in C, C++, Java, and Python.