Answered: Consider the k-d tree shown in Step 3…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

Consider the k-d tree shown in Step 3 of Figure 15.5, constructed out of two
dimensional keys {P: (3, 5), Q: (2, 6), R: (5, 8), S: (1, 7), T: (5, 4), U: (4, 5)}. The
aim is to find the minimum elements MIN1 and MIN2 across dimensions 1 and 2,
respectively. At the end of the FIND MIN operation, MIN1 would be set to 1 and
MIN2 would be set to 4.

Keys: {P: (3,5), Q: (2,6), R: (5,8), S: (1,7), T: (5,4), U: (4,5)}
P
(3,5)
Step 1 (a)
Step 2
(b)
median (6, 7) = 6
Step 3
S(1,7)
Q(2,6)
(2,6)
P
(3,5)
(2,6)
Zas
(1,7)
S
(1,7)
(3,5)
P
(3,5)
DISC=1 median (1, 2, 3 4, 5, 5)=3
DISC = 1
U(4, 5)
R(5,8)
T(5, 4)
URT
T
(5,4)
DISC=1
DISC=2
DISC= 1
U
(4, 5)
R
(5,8)
DISC = 1
DISC = 2 median (4, 5, 8) = 5
DISC = 1
Figure 15.5. Building a k-d tree (method (ii))

Expert Solution

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions