C Programming Data Structures K D Tree And Quad Trees Intro Complete Guide

KD-Tree Implementation

A KD-Tree (K-dimensional Tree) is a binary tree used for organizing points in a k-dimensional space. Here, we will implement a 2-dimensional KD-Tree.

Step 1: Define the Structure

First, we need to define the structure for a point and a node in the KD-Tree.

#include <stdio.h>
#include <stdlib.h>

#define DIM 2  // Dimension (2D)

typedef struct {
    double coord[DIM];  // Coordinates
} Point;

typedef struct Node {
    Point p;            // Point stored at this node
    struct Node *left;  // Left child
    struct Node *right; // Right child
} Node;

Step 2: Create a New Node

Implement a function to create a new node given a point.

Node* createNode(Point p) {
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->p = p;
    temp->left = temp->right = NULL;
    return temp;
}

Step 3: Insert Points into KD-Tree

To insert points into the KD-Tree, you'll want to keep track of which dimension to compare against at each level of the tree.

Node* insertRec(Node* root, Point p, unsigned depth) {
    if (root == NULL)
        return createNode(p);  // Create new node

    unsigned cd = depth % DIM;  // Determine axis

    if (cd == 0) {
        if (p.coord[cd] < (root->p).coord[cd])
            root->left  = insertRec(root->left, p, depth + 1);
        else
            root->right = insertRec(root->right, p, depth + 1);
    } else {
        if (p.coord[cd] < (root->p).coord[cd])
            root->left  = insertRec(root->left, p, depth + 1);
        else
            root->right = insertRec(root->right, p, depth + 1);
    }

    return root;
}

Node* insert(Node* root, Point p) {
    return insertRec(root, p, 0);
}

Step 4: Print the KD-Tree

Now, let's implement a simple depth-first traversal to print the tree.

void inorderRec(Node* root, unsigned depth) {
    if (root != NULL) {
        inorderRec(root->left, depth);
        
        printf("Depth: %u, Point: ", depth); 
        for (int i = 0; i < DIM; i++) 
            printf("%.2lf ", root->p.coord[i]);
        printf("\n");

        inorderRec(root->right, depth);
    }
}

void inorder(Node* root) {
    inorderRec(root, 0);
}

Step 5: Test the KD-Tree Implementation

Finally, let's write a main function to test our KD-Tree implementation.

int main() {
    struct Node* root = NULL; 

    Point points[] = {{30, 40}, {5, 25}, {7, 40}, {50, 30}, {35, 45}};
    int n = sizeof(points)/sizeof(points[0]);

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

    printf("Inorder:\n");
    inorder(root);

    return 0;
}

Quad Tree Implementation

A Quad Tree is a tree data structure in which each internal node has exactly four children: north-west, north-east, south-west, south-east. Quad Trees are used for spatial indexing of two-dimensional points and regions.

Step 1: Define Structures

Define the structures for boundaries, points, and nodes.

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    double x, y, width, height;
} Boundary;

typedef struct {
    double x, y;
} Point;

typedef struct {
    Boundary boundary;
    struct QuadTreeNode* NE;
    struct QuadTreeNode* NW;
    struct QuadTreeNode* SE;
    struct QuadTreeNode* SW;
    Point* point;
    unsigned capacity;
    unsigned count;
} QuadTreeNode;

QuadTreeNode* createQuadTree(Boundary boundary, unsigned capacity) {
    QuadTreeNode* qtree = (QuadTreeNode*)malloc(sizeof(QuadTreeNode));
    qtree->boundary = boundary;
    qtree->capacity = capacity;
    qtree->NE = NULL;
    qtree->NW = NULL;
    qtree->SE = NULL;
    qtree->SW = NULL;
    qtree->point = (Point*)malloc(capacity * sizeof(Point));
    qtree->count = 0;
    return qtree;
}

Step 2: Divide Regions & Check Boundaries

Create functions to check whether a point or region lies within a Quad TreeNode's boundary.

int contains(Boundary boundary, Point p) {
    return p.x >= boundary.x && p.x <= (boundary.x + boundary.width) &&
           p.y >= boundary.y && p.y <= (boundary.y + boundary.height);
}

Boundary getQuadrant(Boundary boundary, char quadrant) {
    Boundary subregion = boundary;
    if (quadrant == 'E') {  // North-East
        subregion.x += boundary.width/2;
        subregion.y += boundary.height/2;
    } else if (quadrant == 'W') {  // North-West
        subregion.x += boundary.width/2;
    } else if (quadrant == 'S') {  // South West
        subregion.y += boundary.height/2;
    }
    subregion.width /= 2;
    subregion.height /= 2;
    return subregion;
}

Step 3: Split Subregions

Implement functions to split the Quad Tree into four regions.

void subdivide(QuadTreeNode* node) {
    node->NW = createQuadTree(getQuadrant(node->boundary, 'N'), node->capacity);
    node->NE = createQuadTree(getQuadrant(node->boundary, 'E'), node->capacity);
    node->SW = createQuadTree(getQuadrant(node->boundary, 'S'), node->capacity);
    node->SE = createQuadTree(getQuadrant(node->boundary, 'W'), node->capacity);
}

Step 4: Insert Points into the Quad Tree

Create a function to insert points into the Quad Tree.

int insertIntoNode(QuadTreeNode* node, Point p) {
    if (!contains(node->boundary, p)) 
        return 0;  // Don't add point if outside the bounding box

    if (node->count < node->capacity) {  // If it fits into the capacity, insert point
        node->point[node->count++] = p;
        return 1;
    }
    
    if (node->NW == NULL)  // Not subdivided, subdivide now
        subdivide(node);

    if (insertIntoNode(node->NW, p)) return 1;
    if (insertIntoNode(node->NE, p)) return 1;
    if (insertIntoNode(node->SW, p)) return 1;
    if (insertIntoNode(node->SE, p)) return 1;

    return 0;  // Couldn't insert into any quadrants
}

int insert(QuadTreeNode* root, Point p) {
    return insertIntoNode(root, p);
}

Step 5: Print the Quad Tree

Now, let's implement a simple recursive traversal to print the Quad Tree.

void printTree(QuadTreeNode* node, unsigned depth) {
    if (node == NULL)
        return;

    printf("Depth: %u, Boundary: %.2lf,%.2lf - %.2lf,%.2lf\n", depth,
           node->boundary.x, node->boundary.y,
           node->boundary.x + node->boundary.width, node->boundary.y + node->boundary.height);
    
    for(int i=0; i<node->count; i++){
        printf("\tPoint %.2lu: (%.2f,%.2f)\n", i+1, node->point[i].x, node->point[i].y);
    }

    printTree(node->NW, depth + 1);
    printTree(node->NE, depth + 1);
    printTree(node->SW, depth + 1);
    printTree(node->SE, depth + 1);
}

int main() {
    Boundary rootBound = {0, 0, 80, 80};  // Create bounding box from (0,0) to (80,80)
    unsigned capacity = 4;              // Maximum capacity per node
    QuadTreeNode* root = createQuadTree(rootBound, capacity); 

    Point points[] = {{20, 20}, {40, 50}, {60, 10}, {30, 70}, {45, 15}, {55, 55}, {10, 50}};
    int n = sizeof(points)/sizeof(points[0]);

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

    printf("QuadTree:\n");
    printTree(root, 0);

    free(root);  // Clean-up
    return 0;
}

Summary and Notes

• KD-Tree: The example above shows how to build a KD-Tree for points in 2D space. It includes insertion and inorder traversal functionalities for the purposes demonstration.
• Quad Tree: The example focuses on the basics of building a Quad Tree including subdividing and inserting points with limited capacity per leaf node before subdivision.

Both implementations here are simplified for educational purposes and may lack some additional features such as search operations or full memory management considerations (such as deallocation of all nodes in the tree).