K-dimensional Tree

Intro

We have already seen and hopefully are very familiar with 1-D tree (binary search tree) already. Here we try to generalize the tree structures that organize data points in 2, 3, ..., k dimensions.

Definition

The k-d tree is a binary tree in which every node is k-dimensional data point. Every (non-leaf) node can be thought of as an implicit line/plane that divides the region into two parts. Nodes at level $L$ in a k-d tree discriminate on the $L\mod{k}$’th dimension.

class TreeNode {
    TreeNode leftChild;
    TreeNode rightChild;
    Data point;
    TreeNode (Data point) { this.point = point; }
}

Operations

• Insert

• Delete

• Range (rectangle/circle) Query

• Nearest/Farthest Neighbors

2D Tree

Insert - Adding a new point to a k-d tree is the same as inserting in any other search tree. First, traverse the tree, starting from the root and going either left or right depending on the branching rules. Once you get to the node under which the child should be located, add the new point as either the left or right child of the leaf node, again depending on the branching rules.

Level - The root discriminates on x-axis. The root's children discriminate on the y-axis. The root's grandchildren discriminate on the x-axis so on and so forth.

Insert (x', y'), at node(x, y)
if (level % 2 == 0) // level is even
    if (x' < x)
        go left
    else // (x' >= x)
        go right
else // level is odd
    if (y' < y)
        go left
    else // (y' >= y)
        go right

Range Query - if region(node) intersects with the query region

3D Tree

Insert - The root discriminates on x-axis. The root's children discriminate on the y-axis. The root's grandchildren discriminate on the z-axis.

Insert newNode(x', y', z'), at node(x, y, z)
// base case
    return newNode
if (level % 3 == 0) // discriminate on x-axis
    if (x' < x)
        root.left = insert(root.left, newNode)
    else // (x' >= x)
        root.right = insert(root.right, newNode)
else if (level % 3 == 1) // discriminate on y-axis
    if (y' < y)
        root.left = insert(root.left, newNode)
    else // (y' >= y)
        root.right = insert(root.right, newNode)
else // discriminate on z-axis
    if (z' < z)
        root.left = insert(root.left, newNode)
    else // (z' >= z)
        root.right = insert(root.right, newNode)

Range Query - if region(node) intersects with the query region

Time Complexity

Depending on if the kd tree is balanced

Operation	Average	Worst
Space	O(n)	O(n)
Search	O(logn)	O(n)
Insert	O(logn)	O(n)
Delete	O(logn)	O(n)
Range	O(?)	O(n)
Nearest	O(?)	O(n)