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 treestructNode{int point[2];structNode*left,*right;};// Function to create a new nodestructNode*newNode(int arr[]){structNode* temp =(structNode*)malloc(sizeof(structNode));
temp->point[0]= arr[0];
temp->point[1]= arr[1];
temp->left = temp->right =NULL;return temp;}// Function to insert a new nodestructNode*insertNode(structNode* root,int point[],unsigned depth){if(root ==NULL)returnnewNode(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 treestructNode*constructKdTree(int points[][2],int n){structNode* 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)voidprintKdTree(structNode* root){if(root ==NULL)return;printf("(%d, %d)\n", root->point[0], root->point[1]);printKdTree(root->left);printKdTree(root->right);}// Main functionintmain(){int points[][2]={{3,6},{17,15},{13,15},{6,12},{9,1},{2,7},{10,19}};int n =sizeof(points)/sizeof(points[0]);structNode* root =constructKdTree(points, n);printKdTree(root);return0;}
Output
(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 treestructNode{int point[2];structNode*left,*right;};// Function to create a new nodestructNode*newNode(int arr[]){structNode* temp =(structNode*)malloc(sizeof(structNode));
temp->point[0]= arr[0];
temp->point[1]= arr[1];
temp->left = temp->right =NULL;return temp;}// Function to insert a new nodestructNode*insertNode(structNode* root,int point[],unsigned depth){if(root ==NULL)returnnewNode(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 treestructNode*minValueNode(structNode* root,int d,unsigned depth){if(root ==NULL)returnNULL;unsigned cd = depth %2;if(cd == d){if(root->left ==NULL)return root;returnminValueNode(root->left, d, depth +1);}structNode* left =minValueNode(root->left, d, depth +1);structNode* right =minValueNode(root->right, d, depth +1);structNode* 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 treestructNode*deleteNode(structNode* root,int point[],unsigned depth){if(root ==NULL)returnNULL;unsigned cd = depth %2;if(root->point[0]== point[0]&& root->point[1]== point[1]){if(root->right !=NULL){structNode* 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);}elseif(root->left !=NULL){structNode* 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);returnNULL;}}elseif(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 treestructNode*constructKdTree(int points[][2],int n){structNode* 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)voidprintKdTree(structNode* root){if(root ==NULL)return;printf("(%d, %d)\n", root->point[0], root->point[1]);printKdTree(root->left);printKdTree(root->right);}// Main functionintmain(){int points[][2]={{3,6},{17,15},{13,15},{6,12},{9,1},{2,7},{10,19}};int n =sizeof(points)/sizeof(points[0]);structNode* 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);return0;}
Output
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 treestructNode{int point[2];structNode*left,*right;};// Function to create a new nodestructNode*newNode(int arr[]){structNode* temp =(structNode*)malloc(sizeof(structNode));
temp->point[0]= arr[0];
temp->point[1]= arr[1];
temp->left = temp->right =NULL;return temp;}// Function to insert a new nodestructNode*insertNode(structNode* root,int point[],unsigned depth){if(root ==NULL)returnnewNode(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 treestructNode*searchNode(structNode* root,int point[],unsigned depth){if(root ==NULL)returnNULL;if(root->point[0]== point[0]&& root->point[1]== point[1])return root;unsigned cd = depth %2;if(point[cd]< root->point[cd])returnsearchNode(root->left, point, depth +1);returnsearchNode(root->right, point, depth +1);}// Function to construct a k-d treestructNode*constructKdTree(int points[][2],int n){structNode* 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 treevoidfreeKdTree(structNode* root){if(root ==NULL)return;freeKdTree(root->left);freeKdTree(root->right);free(root);}// Main functionintmain(){int points[][2]={{3,6},{17,15},{13,15},{6,12},{9,1},{2,7},{10,19}};int n =sizeof(points)/sizeof(points[0]);structNode* root =constructKdTree(points, n);int searchPoint[]={13,15};// Searching for (13, 15)structNode* node =searchNode(root, searchPoint,0);if(node !=NULL)printf("Node found: (%d, %d)\n", node->point[0], node->point[1]);elseprintf("Node not found\n");// Free allocated memoryfreeKdTree(root);return0;}
Output
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.
Leave a Reply