Split rules and k-d-tree construction

After this page, you should be able to:

• Trace insertion by the active axis while keeping the strict-left/ties-right rule.

• Describe the inherited region of a descendant rather than extending every cut across the whole plot.

Builds on: Use the shared points and query contracts; depth zero compares x.

Code languages: Python defines the explanations, figures and self-checks. Use the language guide for native conventions and dependencies. Complete runnable topic examples: Python · JavaScript · Julia.

JavaScript points are arrays compared by same_point; Julia points are value tuples. Julia coordinate/child indices are one-based (x=1, y=2; SW/SE/NW/NE=1/2/3/4), while depth still starts at zero. R-tree orientation uses exact big-integer arithmetic for the supplied integer-coordinate geometry; nearest distances remain floating calculations. General R-tree update code is still conceptual in every language.

A coordinate determines the next branch¶

A k-d tree organises points in $k$ dimensions. In the two-dimensional implementation here, nodes at depth 0 compare x, depth 1 compares y, depth 2 compares x again, and so on. The active axis is depth % 2.

Keep one explicit tie policy¶

At a node with active-axis coordinate $s$, every point in the left subtree has that coordinate less than $s$; every point in the right subtree has it greater than or equal to $s$. Both children obey their own next-axis rules too. An exactly identical point is detected before branching and is not inserted twice.

A coordinate tie is not full equality. Distinct points (5, 4) and (5, 7) have equal x values, so the second goes right at an x split, even though y differs. At a y split, compare y instead. Do not replace this rule with ordinary tuple ordering.

Insert the shared points in order¶

class KDNode:
    def __init__(self, point):
        self.point = point
        self.left = None
        self.right = None

def kd_insert(node, point, depth=0):
    if node is None:
        return KDNode(point)
    if point == node.point:
        return node
    axis = depth % 2
    if point[axis] < node.point[axis]:
        node.left = kd_insert(node.left, point, depth + 1)
    else:
        node.right = kd_insert(node.right, point, depth + 1)
    return node

points = [(5, 4), (2, 7), (8, 1), (1, 3), (3, 6), (7, 5), (9, 2)]
root = None
for point in points:
    root = kd_insert(root, point)

class KDNode {
    constructor(point) { this.point=point; this.left=null; this.right=null; }
}
function kd_insert(node,point,depth=0) {
    if (node===null) return new KDNode(point);
    if (same_point(point,node.point)) return node;
    const axis=depth%2;
    if (point[axis]<node.point[axis]) node.left=kd_insert(node.left,point,depth+1);
    else node.right=kd_insert(node.right,point,depth+1);
    return node;
}
var points=[[5,4],[2,7],[8,1],[1,3],[3,6],[7,5],[9,2]], root=null;
for (const point of points) root=kd_insert(root,point);

mutable struct KDNode
    point
    left
    right
end
KDNode(point)=KDNode(point,nothing,nothing)
function kd_insert(node,point,depth=0)
    node===nothing && return KDNode(point)
    point==node.point && return node
    axis=mod(depth,2)+1
    if point[axis]<node.point[axis]; node.left=kd_insert(node.left,point,depth+1)
    else; node.right=kd_insert(node.right,point,depth+1); end
    return node
end
points=[(5,4),(2,7),(8,1),(1,3),(3,6),(7,5),(9,2)]
root=let tree=nothing
    for point in points; tree=kd_insert(tree,point); end
    tree
end

Call with depth 0 for the full tree and reconnect the returned root. Recursion supplies the correct axis for each child. Inserting E follows A left by x, B left by y, then D right by x. The insertion-order tree is not automatically balanced.

Each split is restricted to an inherited region¶

The root divides the plane at x = 5. B splits only the region x < 5 at y = 7; C splits only x ≥ 5 at y = 1. A deeper split does not extend across the entire plane.

For example, the region below D’s right branch satisfies 1 <= x < 5 and y < 7, not merely x >= 1. Ancestor constraints accumulate just as BST key bounds do, but across different coordinates.

Check your understanding¶

Predict the answer before opening the explanation.

1. Starting from the shared tree, predict where a new point H=(5,7) would be inserted.

2. If B=(2,7) were inserted first instead of A, would the root split still be x=5? Would that change which points satisfy the shared range query?

Next: Shape and construction costs, then exact search.