HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What purpose do the leaves in a range trees serve?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thewhatrangeleavestreesservepurpose

Problem

I'm getting into algorithms and I came upon range trees. What confuses me is the leaves in a range tree, since for example:

When you remove the leaves:

It's just a regular BST.
And, every implementation I see of a range tree/range searching, for example, doesn't put the points in the leaves like in the first image.

So, why do depictions of range trees show all the points in the leaves when that would double the amount of space required? Is it just for visualization purposes, or does it represent the output? Is a range tree just a BST with a range query? This may seem nitpicky, but it really confuses me.
Graphic source: graphics.stanford.edu/courses/cs428-03-spring/03Talks/Range.‌​pdf It isn't unique to this specific example. It's seen here: cs.uu.nl/docs/vakken/ga/slides5b.pdf and here:cs.umd.edu/~meesh/cmsc420/ContentBook/FormalNotes/Mount‌​Notes/…, even though they seem to just use regular BSTs and don't seem to put the leaves in the nodes

EDIT: It's probably just for visual purposes: http://www.bowdoin.edu/~ltoma/teaching/cs3250-CompGeom/spring16/Lectures/cg-rangetrees.pdf

Solution

The Range Tree is made from the input array. The array is sorted and then the tree is built. This means that in the standard construction we have started with the array, this may indicate the leaves. And this BST comes from the sorted array, so there is no point in changing it to e.g. self-balancing trees in the standard case and if there are modifications to the points, the self-balanced trees would perform worse (with very complicated implementation for rotations).

But the Range Tree can be more dimensional, them the leaves represent more dimensions, which leads to several decisions: are these actually pointers or integers (as in example)? Do we want to save memory? Are internal nodes used somewhere else to perform destructive operations?

If the footprint really matters, using integers is a good idea, if there are more dimensions or the integers are cheaper than pointers (to me integers are twice cheaper) this design would be better. So if you add pointers instead of the integers it gets heavier, also the ranges might be smaller, so the savings are bigger.

Also like Raphael pointed it looks like in-order traversal, so it may be right thread in the tree as well.

It may also be for illustratory purposes as you indicated.

Please take a look at the Range trees lecture from Marc ban Kreveld.

Context

StackExchange Computer Science Q#68740, answer score: 2

Revisions (0)

No revisions yet.