Data Structures Algorithm and Design

DSECFZG519 Akshaya Ganesan

BITS Pilani Asst. Prof [OFF-CAMPUS]
Pilani|Dubai|Goa|Hyderabad

1
 BITS Pilani
Pilani|Dubai|Goa|Hyderabad

CS10: k-d Trees

2
Query Types
Exact match query: Asks for the object(s) whose key
matches query key exactly.

Range query: Asks for the objects whose key lies in a

specified query range (interval).

Nearest-neighbor query: Asks for the objects whose key

is “close” to query key.

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

K-d Trees

• Invented in 1970s by Jon Bentley

• Name originally meant “3d-trees, 4d-trees, etc”
• where k was the # of dimensions
• Now, people say “kd-tree of dimension d”
• Idea: Each level of the tree compares against 1 dimension.
• The kd tree is a modification to the BST that allows for efficient
processing of multi-dimensional search keys.
• The kd tree differs from the BST in that each level of the kd tree
makes branching decisions based on a particular search key
associated with that level, called the discriminator.
• Each level has a “cutting dimension” or discriminator
• Cycle through the dimensions as you walk down the tree.
4

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Eg: 2-d Tree
• We define the discriminator at level i to be i mod k for k dimensions.
• For example, assume that we store data organized by xy-coordinates.
• In this case, k is 2 with the x-coordinate field arbitrarily designated key 0,
and the y-coordinate field designated key 1.
• At each level, the discriminator alternates between x and y.
• Thus, a node N at level 0 (the root) would have in its left subtree only nodes
whose x values are less than Nx (because x is search key 0, and
0mod2=0).
• The right subtree would contain nodes whose x values are greater than Nx.
• A node M at level 1 would have in its left subtree only nodes whose y
values are less than My.
• There is no restriction on the relative values of Mx and the x values of M 's
descendants, because branching decisions made at M are based solely on
the y coordinate.

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Example

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

BSP

Binary space partitioning (BSP) is a method for recursively

subdividing a space into two convex sets by using
hyperplanes as partitions.

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

k-d Trees

k-d tree is a space-partitioning data structure for organizing

points in a k-dimensional space.
k-d trees are a useful data structure for searches involving
a multidimensional search key (e.g. range searches and
nearest neighbor searches).
k-d trees are a special case of binary space partitioning
trees.

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Insert into k-d Tree

insert(Point x, KDNode t, int cd) {

if t == null
t = new KDNode(x)
else if (x == t.data)
// error! duplicate
else if (x[cd] < t.data[cd])
t.left = insert(x, t.left, (cd+1) % DIM)
else
t.right = insert(x, t.right, (cd+1) % DIM)
return t
}
9

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

FindMin in kd-trees

• FindMin(d): find the point with the smallest value in

the dth dimension.
• Recursively traverse the tree
• If cutdim(current_node) = d, then the minimum
can’t be in the right subtree, so recurse on just the
left subtree
- if no left subtree, then current node is the min for tree
rooted at this node.
• If cutdim(current_node) ≠ d, then minimum could
be in either subtree, so recurse on both subtrees.
- (unlike in 1-d structures, often have to explore several
paths down the tree)
10

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Finding minimum

11

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Find Minimum
Point findmin(Node T, int dim, int cd):
// empty tree
if T == NULL: return NULL
// T splits on the dimension we’re searching
// => only visit left subtree
if cd == dim:
if t.left == NULL: return t.data
else return findmin(T.left, dim, (cd+1)%DIM)

// T splits on a different dimension

// => have to search both subtrees
else:
return minimum(
findmin(T.left, dim, (cd+1)%DIM),
findmin(T.right, dim, (cd+1)%DIM)
T.data
)

12

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Delete in kd-trees

Want to delete node A.

Assume cutting dimension of
A is cd
In BST, we’d inorder
successor or
findmin(A.right).
Here, we have to
findmin(A.right, cd)
Everything in Q has cd-coord
< B, and
everything in P has cdcoord ≥
B
13

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

KD Tree (cont’d)
Example: data stored at the leaves

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

KD Tree (cont’d)
• Every node (except leaves) represents a hyperplane
that divides the space into two parts.
• Points to the left (right) of this hyperplane represent the
left (right) sub-tree of that node.

Pleft Pright

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

KD Tree (cont’d)
As we move down the tree, we divide the space along
alternating (but not always) axis-aligned hyperplanes:

Split by x-coordinate: split by a vertical line that

has (ideally) half the points left or on, and half right.

Split by y-coordinate: split by a horizontal line

that has (ideally) half the points below or on and
half above.

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

KD Tree - Example
Split by x-coordinate: split by a vertical line that
has approximately half the points left or on, and
half right.

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

KD Tree - Example
Split by y-coordinate: split by a horizontal line that
has half the points below or on and half above.

y y

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

KD Tree - Example
Split by x-coordinate: split by a vertical line that
has half the points left or on, and half right.

y y

x
x x x

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

KD Tree - Example
Split by y-coordinate: split by a horizontal line that
has half the points below or on and half above.

y y

x
x x x

y y

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Splitting Strategies
Divide based on order of point insertion
– Assumes that points are given one at a time.

Divide by finding median

– Assumes all the points are available ahead of time.

Divide perpendicular to the axis with widest

spread
– Split axes might not alternate … and more!

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Example – using order of point insertion
(data stored at nodes

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

 Example – using median
(data stored at the leaves)

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

 Example – using median
(data stored at the leaves)

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

 Example – using median
(data stored at the leaves)

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

 Example – using median
(data stored at the leaves)

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

 Example – using median
(data stored at the leaves)

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

 Example – using median
(data stored at the leaves)

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

 Example – using median
(data stored at the leaves)

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

 Example – using median
(data stored at the leaves)

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

 Example – using median
(data stored at the leaves)

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Another Example - using median

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Another Example - using median

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Another Example - using median

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Another Example - using median

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Another Example - using median

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

 Insert new data
55 > 53, move right

Insert (55, 62) 53, 14 x 62 > 51, move right

27, 28 65, 51 y

70, 3 99, 90 x
30, 11 31, 85
55 < 99, move left

40, 26 7, 39 32, 29 82, 64

29, 16 y

38, 23 55,62 73, 75

15, 61
62 < 64, move left
Null pointer, attach

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Delete data
Suppose we need to remove p = (a, b)
– Find node t which contains p
– If t is a leaf node, replace it by null
– Otherwise, find a replacement node r = (c, d) – see below!
– Replace (a, b) by (c, d)
– Remove r
Finding the replacement r = (c, d)
– If t has a right child, use the successor*
– Otherwise, use node with minimum value* in the left
subtree
*
(depending on what axis the node discriminates)

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Delete data (cont’d)

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Delete data (cont’d)

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

KD Tree – Exact Search

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

KD Tree – Exact Search

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

KD Tree – Exact Search

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

KD Tree – Exact Search

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

KD Tree – Exact Search

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

KD Tree – Exact Search

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

KD Tree – Exact Search

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

KD Tree – Exact Search

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

KD Tree – Exact Search

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

KD Tree – Exact Search

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

KD Tree – Exact Search

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Other Examples

Nearest Neighbour Search

Range Search

52

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

Thank You!!

53

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956