Blog

Priority search tree is a hybrid data structures, means it is a combination of binary search tree and priority queue. It is used for storing a set of points in a two-dimensional space, which are ordered by their priority and also key value.

It is a data structure that stores the points in sorted order based on their x-coordinate. Each node in the tree contains a priority queue that stores the points in sorted order based on their y-coordinate.

This data structure mainly used for solving the 2-D range query problem in computational geometry.

Structure of Priority Search Tree

Priority search tree has two main components:

• Binary Search Tree: The binary search tree stores the points in sorted order based on their x-coordinate.The left subtree of a node contains points with x-coordinates less than the x-coordinate of the node, and the right subtree contains points with x-coordinates greater than the x-coordinate of the node.
• Priority Queue: The priority queue stores the points in sorted order based on their y-coordinate.Each node in the tree contains a priority queue that stores the points in sorted order based on their y-coordinate.

Operations on Priority Search Tree

Priority search tree supports the following operations −

• Insert: Insert a point into the priority search tree.
• Search: Search for a point in the priority search tree based on its x-coordinate.
• Range Query: Find all the points that lie within a given range in the two-dimensional space.

Implementing Priority Search Tree

Priority search tree can be implemented using a binary search tree and a priority queue.

Here is an example of a priority search tree implemented using a binary search tree and a priority queue:

CC++JavaPython

#include <stdio.h>#include <stdlib.h>// Structure to represent a point in 2D spacestructPoint{int x, y;};// Structure to represent a node in the priority search treestructNode{structPoint point;structNode* left;structNode* right;};// Function to create a new nodestructNode*createNode(structPoint point){structNode* newNode =(structNode*)malloc(sizeof(structNode));
   newNode->point = point;
   newNode->left =NULL;
   newNode->right =NULL;return newNode;}// Function to insert a point into the priority search treestructNode*insert(structNode* root,structPoint point){if(root ==NULL){returncreateNode(point);}if(point.x < root->point.x){
       root->left =insert(root->left, point);}else{
       root->right =insert(root->right, point);}return root;}// Function to print the points in the priority search treevoidprintPoints(structNode* root){if(root !=NULL){printPoints(root->left);printf("(%d, %d) ", root->point.x, root->point.y);printPoints(root->right);}}intmain(){structNode* root =NULL;structPoint points[]={{5,3},{2,8},{9,1},{7,4},{3,6}};int n =sizeof(points)/sizeof(points[0]);for(int i =0; i < n; i++){
       root =insert(root, points[i]);}printf("Points in the priority search tree: ");printPoints(root);printf("\n");return0;}

Output

Output of the above code will be:

Points in the priority search tree: (2, 8) (3, 6) (5, 3) (7, 4) (9, 1)

Search in Priority Search Tree

Searching for a point in a priority search tree is similar to searching for a key in a binary search tree. We start at the root of the tree and recursively search the tree based on the x-coordinate of the point.

Let us understand how the search operation works in a priority search tree:

Algorithm

Following is the algorithm, follow the steps:

1. Start at the root of the tree.
2. return the root if it is null or the x-coordinate of the root is equal to the search key.
3. if the search key is less than the x-coordinate of the root, recursively search the left subtree.
4. if the search key is greater than the x-coordinate of the root, recursively search the right subtree.
5. return the node if found, otherwise return null.

Example code

Here is an example code that demonstrates the search operation in a priority search tree:

CC++JavaPython

#include <stdio.h>#include <stdlib.h>// Structure to represent a point in 2D spacestructPoint{int x, y;};// Structure to represent a node in the priority search treestructNode{structPoint point;structNode* left;structNode* right;};// Function to create a new nodestructNode*createNode(structPoint point){structNode* newNode =(structNode*)malloc(sizeof(structNode));
   newNode->point = point;
   newNode->left =NULL;
   newNode->right =NULL;return newNode;}// Function to insert a point into the priority search treestructNode*insert(structNode* root,structPoint point){if(root ==NULL){returncreateNode(point);}if(point.x < root->point.x){
       root->left =insert(root->left, point);}else{
       root->right =insert(root->right, point);}return root;}// Function to search for a point in the priority search treestructNode*search(structNode* root,int x){if(root ==NULL|| root->point.x == x){return root;}if(x < root->point.x){returnsearch(root->left, x);}else{returnsearch(root->right, x);}}intmain(){structNode* root =NULL;structPoint points[]={{5,3},{2,8},{9,1},{7,4},{3,6}};int n =sizeof(points)/sizeof(points[0]);for(int i =0; i < n; i++){
       root =insert(root, points[i]);}int x =7;structNode* result =search(root, x);if(result !=NULL){printf("Point with x-coordinate %d found: (%d, %d)\n", x, result->point.x, result->point.y);}else{printf("Point with x-coordinate %d not found\n", x);}return0;}

Output

Output of the above code will be:

Point with x-coordinate 7 found: (7, 4)

Range Query in Priority Search Tree

This operation is the main application of the priority search tree. It is used to find all the points that lie within a given range in the two-dimensional space.

Algorithm

Following is the algorithm, follow the steps:

1. Start at the root of the tree.
2. If the range intersects the x-coordinate of the node, search the priority queue at the node based on the y-coordinate of the range.
3. Retrieve the points that lie within the range.
4. Recursively search the left and right subtrees based on the x-coordinate of the range.
5. Return the points that lie within the range.

Example code

Here is an example code that demonstrates the range query operation in a priority search tree:

CC++JavaPython

#include <stdio.h>#include <stdlib.h>// Structure to represent a point in 2D spacestructPoint{int x, y;};// Structure to represent a node in the priority search treestructNode{structPoint point;structNode* left;structNode* right;};// Function to create a new nodestructNode*createNode(structPoint point){structNode* newNode =(structNode*)malloc(sizeof(structNode));
   newNode->point = point;
   newNode->left =NULL;
   newNode->right =NULL;return newNode;}// Function to insert a point into the priority search treestructNode*insert(structNode* root,structPoint point){if(root ==NULL){returncreateNode(point);}if(point.x < root->point.x){
       root->left =insert(root->left, point);}else{
       root->right =insert(root->right, point);}return root;}// Function to print the points in the priority search treevoidprintPoints(structNode* root){if(root !=NULL){printPoints(root->left);printf("(%d, %d) ", root->point.x, root->point.y);printPoints(root->right);}}// Function to find all the points that lie within a given rangevoidrangeQuery(structNode* root,int x1,int x2,int y1,int y2){if(root ==NULL){return;}if(root->point.x >= x1 && root->point.x <= x2 && root->point.y >= y1 && root->point.y <= y2){printf("(%d, %d) ", root->point.x, root->point.y);}if(root->point.x >= x1){rangeQuery(root->left, x1, x2, y1, y2);}if(root->point.x <= x2){rangeQuery(root->right, x1, x2, y1, y2);}}intmain(){structNode* root =NULL;structPoint points[]={{5,3},{2,8},{9,1},{7,4},{3,6}};int n =sizeof(points)/sizeof(points[0]);for(int i =0; i < n; i++){
       root =insert(root, points[i]);}printf("Points in the priority search tree: ");printPoints(root);printf("\n");int x1 =3, x2 =7, y1 =2, y2 =5;printf("Points within the range (%d, %d) - (%d, %d): ", x1, y1, x2, y2);rangeQuery(root, x1, x2, y1, y2);printf("\n");return0;}

Output

Output of the above code will be:

Points in the priority search tree: (2, 8) (3, 6) (5, 3) (7, 4) (9, 1)
Points within the range (3, 2) - (7, 5): (5, 3) (3, 6) (7, 4)

Applications of Priority Search Tree

Following are the applications of a Priority Search Tree −

• Computational Geometry : Priority search tree is mostly used in computational geometry to solve two-dimensional range query problems.
• Database Systems : Used for search records in a database based on their x and y coordinates.
• Scheduling Algorithms : It can be used for scheduling tasks based on their priority and key value.

Conclusion

In this chapter, we have learned about the priority search tree data structure and its applications. We have also seen how to implement a priority search tree using a binary search tree and a priority queue. We have discussed the operations supported by the priority search tree, such as insert, search, and range query.

We have also seen how to search for a point in a priority search tree and find all the points that lie within a given range in a two-dimensional space.

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:

CC++JavaPython

#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:

CC++JavaPython

// 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:

CC++JavaPython

#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.