 # K-Dimensional Tree in Data Structures

Amit Kumar Ghosh  21 min read
16 Jun 2023
Beginner
332 Views

## Introduction

Have you ever wondered how to easily organize or search through a large set of data? K-dimensional trees (kd-trees) offer an efficient way to quickly store and retrieve information in both two-dimensional and multidimensional spaces. Kd-trees can be used in applications ranging from computer graphics to scientific computing, offering increased speed and accuracy when searching large datasets. In this article, we will explore what kd-trees are, the benefits they offer, and where they can be applied for optimal results. Read on to find out more about this powerful algorithm!

## What is a K-Dimensional tree

A k-dimensional tree, also known as a k-d tree, is a data structure used for organizing points in a k-dimensional space. It is a binary tree in which nodes represent a point in k-dimensional space. Each node has a key that corresponds to one of the k dimensions, and its left and right child nodes represent points that have smaller and higher values in that dimension, respectively. The k-d tree is particularly useful when searching for nearest neighbor points in large data sets. By efficiently partitioning the data and pruning irrelevant branches, the k-dimensional tree can greatly reduce the time required to find nearest neighbors. Whether you're a computer scientist, mathematician, or someone who deals with large data sets, understanding the k-d tree is an important tool in your arsenal.

## Complexity of K-Dimensional tree

The complexity of a k-dimensional tree, also known as a kd-tree, depends on the specific operation being performed. There are several common operations associated with kd-trees, each with its own complexity.

1. Construction: Constructing a kd-tree from a set of k-dimensional points is typically performed using a recursive algorithm. The complexity of constructing a kd-tree with n points is O(n log n) on average. However, in the worst case, it can be O(n^2), for example, when the input points are already sorted or nearly sorted.
2. Searching: Searching for a point in a kd-tree involves traversing the tree in a manner that exploits its hierarchical structure. The complexity of searching in a balanced kd-tree is O(log n), where n is the number of points in the tree. However, in the worst case, when the kd-tree is highly unbalanced, the search complexity can deteriorate to O(n).
3. Nearest neighbor search: Finding the nearest neighbor to a given query point in a kd-tree requires traversing the tree and pruning branches based on distance calculations. The average complexity of nearest neighbor search in a balanced kd-tree is O(log n), but in the worst case, it can be O(n).
4. Range search: Performing a range search in a kd-tree involves finding all points within a specified range or bounding box. The complexity of range search depends on the number of points that fall within the range. In the worst case, where all points are within the range, the complexity is O(n). However, on average, the complexity can be much lower, closer to O(sqrt(n)).

## Implementations of K-Dimensional tree

``````
# A Python program to demonstrate operations of KD tree
import sys

# Number of dimensions
k = 2

# A structure to represent node of kd tree
class Node:
def __init__(self, point):
self.point = point
self.left = None
self.right = None

# A method to create a node of K D tree
def newNode(point):
return Node(point)

# Inserts a new node and returns root of modified tree
# The parameter depth is used to decide axis of comparison
def insertRec(root, point, depth):
# Tree is empty?
if not root:
return newNode(point)

# Calculate current dimension (cd) of comparison
cd = depth % k

# Compare the new point with root on current dimension 'cd'
# and decide the left or right subtree
if point[cd] < root.point[cd]:
root.left = insertRec(root.left, point, depth + 1)
else:
root.right = insertRec(root.right, point, depth + 1)

return root

# Function to insert a new point with given point in
# KD Tree and return new root. It mainly uses above recursive
# function "insertRec()"
def insert(root, point):
return insertRec(root, point, 0)

# A utility method to determine if two Points are same
# in K Dimensional space
def arePointsSame(point1, point2):
# Compare individual coordinate values
for i in range(k):
if point1[i] != point2[i]:
return False

return True

# Searches a Point represented by "point[]" in the K D tree.
# The parameter depth is used to determine current axis.
def searchRec(root, point, depth):
# Base cases
if not root:
return False
if arePointsSame(root.point, point):
return True

# Current dimension is computed using current depth and total
# dimensions (k)
cd = depth % k

# Compare point with root with respect to cd (Current dimension)
if point[cd] < root.point[cd]:
return searchRec(root.left, point, depth + 1)

return searchRec(root.right, point, depth + 1)

# Searches a Point in the K D tree. It mainly uses
# searchRec()
def search(root, point):
# Pass current depth as 0
return searchRec(root, point, 0)

# Driver program to test above functions
if __name__ == '__main__':
root = None
points = [[3, 6], [17, 15], [13, 15], [6, 12], [9, 1], [2, 7], [10, 19]]

n = len(points)

for i in range(n):
root = insert(root, points[i])

point1 = [10, 19]
if search(root, point1):
print("Found")
else:

point2 = [12, 19]
if search(root, point2):
print("Found")
else:

# This code is contributed by Prajwal Kandekar``````
``````
import java.util.*;

class Node {
int[] point;
Node left, right;

public Node(int[] arr)
{
this.point = arr;
this.left = this.right = null;
}
}

class KDtree {
int k = 2;

public Node newNode(int[] arr) { return new Node(arr); }

public Node insertRec(Node root, int[] point, int depth)
{
if (root == null) {
return newNode(point);
}

int cd = depth % k;
if (point[cd] < root.point[cd]) {
root.left
= insertRec(root.left, point, depth + 1);
}
else {
root.right
= insertRec(root.right, point, depth + 1);
}

return root;
}

public Node insert(Node root, int[] point)
{
return insertRec(root, point, 0);
}

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

public boolean searchRec(Node root, int[] point,
int depth)
{
if (root == null) {
return false;
}
if (arePointsSame(root.point, point)) {
return true;
}

int cd = depth % k;
if (point[cd] < root.point[cd]) {
return searchRec(root.left, point, depth + 1);
}
return searchRec(root.right, point, depth + 1);
}

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

public static void main(String[] args)
{
KDtree kdTree = new KDtree();

Node root = null;
int[][] points
= { { 3, 6 }, { 17, 15 }, { 13, 15 }, { 6, 12 },
{ 9, 1 }, { 2, 7 }, { 10, 19 } };

int n = points.length;

for (int i = 0; i < n; i++) {
root = kdTree.insert(root, points[i]);
}

int[] point1 = { 10, 19 };
System.out.println(kdTree.search(root, point1)
? "Found"

int[] point2 = { 12, 19 };
System.out.println(kdTree.search(root, point2)
? "Found"
}
}``````
``````
// A C++ program to demonstrate operations of KD tree
#include<bits/stdc++.h>
using namespace std;

const int k = 2;

// A structure to represent node of kd tree
struct Node
{
int point[k]; // To store k dimensional point
Node *left, *right;
};

// A method to create a node of K D tree
struct Node* newNode(int arr[])
{
struct Node* temp = new Node;

for (int i=0; i<k; i++)
temp->point[i] = arr[i];

temp->left = temp->right = NULL;
return temp;
}

// Inserts a new node and returns root of modified tree
// The parameter depth is used to decide axis of comparison
Node *insertRec(Node *root, int point[], unsigned depth)
{
// Tree is empty?
if (root == NULL)
return newNode(point);

// Calculate current dimension (cd) of comparison
unsigned cd = depth % k;

// Compare the new point with root on current dimension 'cd'
// and decide the left or right subtree
if (point[cd] < (root->point[cd]))
root->left = insertRec(root->left, point, depth + 1);
else
root->right = insertRec(root->right, point, depth + 1);

return root;
}

// Function to insert a new point with given point in
// KD Tree and return new root. It mainly uses above recursive
// function "insertRec()"
Node* insert(Node *root, int point[])
{
return insertRec(root, point, 0);
}

// A utility method to determine if two Points are same
// in K Dimensional space
bool arePointsSame(int point1[], int point2[])
{
// Compare individual pointinate values
for (int i = 0; i < k; ++i)
if (point1[i] != point2[i])
return false;

return true;
}

// Searches a Point represented by "point[]" in the K D tree.
// The parameter depth is used to determine current axis.
bool searchRec(Node* root, int point[], unsigned depth)
{
// Base cases
if (root == NULL)
return false;
if (arePointsSame(root->point, point))
return true;

// Current dimension is computed using current depth and total
// dimensions (k)
unsigned cd = depth % k;

// Compare point with root with respect to cd (Current dimension)
if (point[cd] < root->point[cd])
return searchRec(root->left, point, depth + 1);

return searchRec(root->right, point, depth + 1);
}

// Searches a Point in the K D tree. It mainly uses
// searchRec()
bool search(Node* root, int point[])
{
// Pass current depth as 0
return searchRec(root, point, 0);
}

// Driver program to test above functions
int main()
{
struct Node *root = NULL;
int points[][k] = {{3, 6}, {17, 15}, {13, 15}, {6, 12},
{9, 1}, {2, 7}, {10, 19}};

int n = sizeof(points)/sizeof(points);

for (int i=0; i<n; i++)
root = insert(root, points[i]);

int point1[] = {10, 19};

int point2[] = {12, 19};

return 0;
}``````

#### Output

``````Found 