# Implementation of k-d-Tree

I am a complete beginner in C and I have started learning it by implementing binary trees. So have implemented a basic k-d-Tree. I provide two structs and two methods for comparing values on different axis.

typedef struct Point2D {
double x;
double y;
} Point2D;

int x_comparator(const void *v1, const void *v2) {
const Point2D *p1 = (Point2D *) v1;
const Point2D *p2 = (Point2D *) v2;
if (p1->x < p2->x)
return -1;
else if (p1->x > p2->x)
return +1;
else
return 0;
}

int y_comparator(const void *v1, const void *v2) {
const Point2D *p1 = (Point2D *) v1;
const Point2D *p2 = (Point2D *) v2;
if (p1->y < p2->y)
return -1;
else if (p1->y > p2->y)
return +1;
else
return 0;
}

#define DIMENSION 2

typedef struct KdNode {
Point2D *p;
struct KdNode *left, *right;
int splittingAxis;
} KdNode;


and my method for building the k-d-Tree :

KdNode* build(Point2D data[], int splittingAxis, int numberElements) {
KdNode *temp = (KdNode*) malloc(sizeof(KdNode));
KdNode *left = (KdNode*) malloc(sizeof(KdNode));
KdNode *right = (KdNode*) malloc(sizeof(KdNode));
if (temp == NULL || left == NULL || right == NULL) {
exit(1);
}
if (numberElements == 0) {
return NULL;
}

int median, numberElementsLeft, numberElementsRight;
median = floor(numberElements / 2);
Point2D leftSide[median], rightSide[numberElements - median - 1];
splittingAxis = splittingAxis % DIMENSION;

if (splittingAxis == 0) {
qsort(data, numberElements, sizeof(Point2D), x_comparator);
} else {
qsort(data, numberElements, sizeof(Point2D), y_comparator);
}

numberElementsLeft = median;
numberElementsRight = numberElements - median - 1;

memcpy(leftSide, data, numberElementsLeft * sizeof(Point2D));
memcpy(rightSide, &data[numberElements - median],
numberElementsRight * sizeof(Point2D));

Point2D *tPoint = (Point2D*) malloc(sizeof(Point2D));

tPoint->x = data[median].x;
tPoint->y = data[median].y;
left = build(leftSide, (splittingAxis + 1) % DIMENSION,numberElementsLeft);
right = build(rightSide, (splittingAxis + 1) % DIMENSION,
numberElementsRight);
temp->p = tPoint;
temp->left = left;
temp->right = right;
temp->splittingAxis = splittingAxis;
return temp;
}


Is this a correct implementation of a k-d-Tree in C? What would you criticize and how could it be improved?

## malloc

You should not cast the return value from malloc() in C. Instead, include its header file, and let the compiler's conversion from void* to specific pointer happen naturally.:

KdNode *temp = malloc(sizeof (KdNode));


It's often better to use the size of the actual object(s) you're allocating, rather than the size of the type. This isn't an issue here, where your declaration is on the same line as the allocation, but consider this:

temp = malloc(sizeof (KdNode));


If you can't see the declaration, then it's harder to be sure that sizeof KdNode is the right size. Instead we can write:

temp = malloc(sizeof *temp);


This also eliminates some irritating parentheses, which is nice!

## error behaviour

What should happen when you misuse the function? Here, you have two different behaviours:

if (temp == NULL || left == NULL || right == NULL) {
exit(1);
}
if (numberElements == 0) {
return NULL;
}


If anything, these are the wrong way around - you abort the whole program for an unpredictable run-time failure from malloc(), but nicely return a null value when you're (avoidably) given nonsense arguments. It's generally best not to invoke exit() from a function you want anybody to be able to use anywhere; I'd make both cases return NULL. And change the test for numberElements to be <= 0, or its type to unsigned.

## comparators

Comparators for qsort can return any positive value or any negative value or zero as results. So they don't need to be coerced to -1/0/+1; however, as you've noticed, the difference may be out of range for an int. However, there's an easier way to obtain a value of correct sign, and the default conversion will work for us:

#include <math.h>
int x_comparator(const void *v1, const void *v2) {
const Point2D *p1 = v1;
const Point2D *p2 = v2;
return copysign(1, p1->x - p2->x);
}


I took out the unnecessary casts from void* here, too.

## avoid floor() with integer division

This has an unnecessary round-trip through floating-point and back:

median = floor(numberElements / 2);


Integer division rounds down, so numberElements / 2 is sufficient.

## possible simplification of if/else

Most of this is invariant between the two branches:

if (splittingAxis == 0) {
qsort(data, numberElements, sizeof(Point2D), x_comparator);
} else {
qsort(data, numberElements, sizeof(Point2D), y_comparator);
}


You might choose to make only the comparator argument dependent on the condition:

qsort(data, numberElements, sizeof *data, splittingAxis ? y_comparator : x_comparator);


If that's too opaque, then you could define a variable:

int (*const comparator)(const void*, const void*)
= splittingAxis ? y_comparator : x_comparator;

qsort(data, numberElements, sizeof *data, comparator);


In honesty, the original may well be the best option here (but using sizeof *data rather than sizeof (Point2D) helps ensure a type match).

One approach that works well is to use splittingAxis to index an array. To me, this looks compact and clear :

/* qsort-compatible comparator functions */
typedef int Comparator(const void*, const void*);
Comparator *const comparators[] = {x_comparator, y_comparator };

    qsort(data, numberElements, sizeof *data, comparators[splittingAxis]);


## copy whole struct

Here you copy a Point2D member-by-member:

tPoint->x = data[median].x;
tPoint->y = data[median].y;


We can write that as:

*tPoint = data[median];


## always check allocators' return value before use

You got this right early in the function, but tPoint is accessed immediately after allocation with no check it isn't null.

# Modified version:

I've reordered some code and eliminated some local variables to give something that reads better to me. See whether you agree.

#include <math.h>
#include <stdlib.h>
#include <string.h>

typedef struct Point2D {
double x;
double y;
} Point2D;

static int x_comparator(const void *v1, const void *v2) {
const Point2D *p1 = v1;
const Point2D *p2 = v2;
return copysign(1, p1->x - p2->x);
}

static int y_comparator(const void *v1, const void *v2) {
const Point2D *p1 = v1;
const Point2D *p2 = v2;
return copysign(1, p1->y - p2->y);
}

typedef struct KdNode {
Point2D *p;
struct KdNode *left, *right;
int splittingAxis;
} KdNode;

/* qsort-compatible comparator functions */
typedef int Comparator(const void*, const void*);
Comparator *const comparators[] = {x_comparator, y_comparator };

KdNode* build(Point2D data[],
unsigned int splittingAxis,
unsigned int numberElements)
{
if (numberElements <= 0 || splittingAxis > 1) {
return NULL;
}

KdNode *temp = malloc(sizeof *temp);
KdNode *left = malloc(sizeof *left);
KdNode *right = malloc(sizeof *right);
if (!temp || !left || !right) {
return NULL;
}

temp->p = malloc(sizeof *temp->p);
if (!temp->p) {
return NULL;
}

qsort(data, numberElements, sizeof *data, comparator[splittingAxis]);

const unsigned int median = numberElements / 2;
const unsigned int numberElementsLeft = median;
const unsigned int numberElementsRight = numberElements - median - 1;
Point2D leftSide[numberElementsLeft];
Point2D rightSide[numberElementsRight];

memcpy(leftSide, data, sizeof leftSide);
memcpy(rightSide, &data[numberElements - median], sizeof(rightSide));

const int other_axis = 1 - splittingAxis;

*temp->p = data[median];
temp->left = build(leftSide, other_axis, numberElementsLeft);
temp->right = build(rightSide, other_axis, numberElementsRight);
temp->splittingAxis = splittingAxis;
return temp;
}


# Performance improvement

Given that we're allowed to modify data and that we're not using it after finding the median value, we don't need to copy its elements into new arrays - we can sort its sub-arrays in-place:

KdNode* build(Point2D data[],
unsigned int splittingAxis,
unsigned int numberElements)
{
if (numberElements <= 0 || splittingAxis > 1) {
return NULL;
}

KdNode *temp = malloc(sizeof *temp);
KdNode *left = malloc(sizeof *left);
KdNode *right = malloc(sizeof *right);
if (!temp || !left || !right) {
return NULL;
}

temp->p = malloc(sizeof *temp->p);
if (!temp->p) {
return NULL;
}

qsort(data, numberElements, sizeof *data, comparator[splittingAxis]);

const unsigned int median = numberElements / 2;
const int other_axis = 1 - splittingAxis;

*temp->p = data[median];
temp->left = build(data, other_axis, median);
temp->right = build(data + median + 1, other_axis, numberElements - median - 1);
temp->splittingAxis = splittingAxis;
return temp;
}


Side note: if you ever re-write this in C++, you'll find std::partial_sort() useful for finding the median with less computation than a full qsort().

• Hello @Toby Speight, thank you for your Review. I like the changes you made. I just learned a few things ! Mar 22 '17 at 13:57