Scribd
Upload
134 views10 pages

Range Tree PDF

A 2D range tree is an augmented tree used to solve orthogonal range searching queries on a set of points in the plane. It consists of a main tree storing x-coordinates and associated trees storing y-coordinates. Range trees use O(n log n) space and can be constructed in O(n log n) time. Orthogonal range reporting queries can be answered in O(k + (log n)2) time, where k is the number of reported points. Layered range trees add fractional cascading to speed up queries to O(k + log n) time.

Uploaded by

Armando Padrón
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
134 views10 pages

Range Tree PDF

A 2D range tree is an augmented tree used to solve orthogonal range searching queries on a set of points in the plane. It consists of a main tree storing x-coordinates and associated trees storing y-coordinates. Range trees use O(n log n) space and can be constructed in O(n log n) time. Orthogonal range reporting queries can be answered in O(k + (log n)2) time, where k is the number of reported points. Layered range trees add fractional cascading to speed up queries to O(k + log n) time.

Uploaded by

Armando Padrón
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 10

Range Trees

A 2D range tree for a point set S is an augmented tree. The main tree
is a leaf-oriented balanced binary search tree on the x-coordinates
of the points in S. The data structure associated with a node v is a
leaf-oriented balanced binary search tree on the y-coordinates of the
canonical subset of v.

Range tree applet: http://www.cs.umd.edu/users/brabec/quadtree/RANGEtrees/range.html

1
Lemma: A range tree for a set of n points in the plane uses O(n log n)
space and can be constructed in O(n log n) time.

Two-Dimensional Orthogonal Range Searching

2
2DR ANGE Q UERY(T, [x, x0 ] × [y, y0 ])
1 vsplit ← F IND S PLIT N ODE(T, x, x0 )
2 if vsplit is a leaf
3 then check if point at vsplit must be reported
4 else v ← lc(vsplit )
5 while v is not a leaf
6 do if x ≤ xv
7 then 1DR ANGE Q UERY(Tassoc (rc(v)), [y, y0 ])
8 v ← lc(v)
9 else v ← rc(v)
10 Check if point stored at v must be reported
11 v ← rc(vsplit )
12 while v is not a leaf
13 do if x ≤ xv
14 then v ← lc(v)
15 else 1DR ANGE Q UERY(Tassoc (lc(v)), [y, y0 ])
16 v ← rc(v)
17 Check if point stored at v must be reported
3
Lemma: An orthogonal range reporting query in a range tree storing
n points in the plane takes O(k + (log n)2 ) time, where k is the num-
ber of reported points.

4
Higher-dimensional Range Trees

Theorem: Let S be a set of n points in d-dimensional space, d ≥ 2.


A range tree for S uses O(n(log n)d−1 ) space and can be constructed
in O(n(log n)d−1 ) time. One can report the points contained in an
axis-parallel box in O(k + (log n)d ) time, where k is the number of
reported points.

5
Fractional Cascading
searching in similar lists, especially sublists

12 14 29 33 35 38 49 51 57 66 68 72 74 81 86 90 99 101 108

14 35 38 51 66 72 74 86 99 101

Add a pointer at each element k in the top list pointing to the smallest element
in the bottom list larger than or equal to k. Once a query element q is located
in the top list, the element (or the next larger element) can be located in the
bottom list in O(1) time.

6
7 22 40 51 55 68 75 90 92 101

14 35 38 51 66 72 74 86 99 101

If the bottom list is not a sublist of the top list, copy every other element
from bottom to top. Once a query element q is located in the extended top
list, the element (or the next larger element) can be located in the bottom list
in O(1) time, inspecting O(1) neighboring elements.

7 14 22 38 40 51 55 66 68 74 75 90 92 99 101

14 35 38 51 66 72 74 86 99 101

7
Layered Range Tree = Range Tree + Fractional Cascading

P(lc(v)) ⊂ P(v) P(rc(v)) ⊂ P(v)


12 14 29 33 35 38 49 51 57 66 68 72 74 81 86 90 99 101 108

14 35 38 51 66 72 74 86 99 101 12 29 33 49 57 68 81 90 108

35 38 72 86 99 14 51 66 74 101 29 33 49 68 108 12 57 81 90

35 86 38 72 99 14 66 74 51 101 29 68 33 49 108 57 81 12 90

35 86 72 38 99 14 66 74 51 101 68 29 33 108 49 57 81 90 12

38 99 14 66 108 33

8
12 14 29 33 35 38 49 51 57 66 68 72 74 81 86 90 99 101 108

14 35 38 51 66 72 74 86 99 101 12 29 33 49 57 68 81 90 108

35 38 72 86 99 14 51 66 74 101 29 33 49 68 108 12 57 81 90

35 86 38 72 99 14 66 74 51 101 29 68 33 49 108 57 81 12 90

35 86 72 38 99 14 66 74 51 101 68 29 33 108 49 57 81 90 12

38 99 14 66 108 33

9
Theorem: Let S be a set of points in 2-dimensional space. A lay-
ered range tree for S uses O(n log n) space and can be constructed in
O(n log n) time. A layered range tree allows one to report the points
contained in an axis-parallel box in O(k + log n) time, where k is the
number of reported points.

10

You might also like