Consider a k-d Tree which stores 3-dimensional data (i.e. triples (x,y,z) where

Question

Consider a k-d Tree which stores 3-dimensional data (i.e. triples (x,y,z) where x, y, and z are integers. The levels in the tree alternate splitting on each dimension starting with the first (so the first split is on x, the second on y, the third split is on z, and the next level starts again with x). Values which are less than or equal to the split value should be stored in the left subtree and values which are larger than the split value should be stored in the right subtree.

Draw the tree which results after inserting the following values in the listed order:

(1, 2, 3)

(2, 1, 3)

(1, 3, 2)

(2, 3, 1)

(3, 1, 2)

(3, 2, 1)

(4, 2, 3)

(2, 4, 3)

(4, 3, 2)

(2, 3, 4)

(3, 4, 2)

(3, 2, 4)

Explanation / Answer

Hi,

Here the degree of the tree is not mentioned so i have assumed as 2. So, we will be constructing a binary tree and there is no concept of balance so we are no need to bother about the degree of a node or sub node.

the tree goes like this:

(1,2,3)

(1,3,2)                              (2,1,3)

                                      (2,3,1)             (3,1,2)

                                               (2,4,3)                          (3,2,1)                             (4,2,3)

                          (2,3,4)                             (3,4,2)                            (4,3,2)

(3,2,4)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.