4
$\begingroup$

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

When you remove the leaves: Range tree with removed 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

$\endgroup$
  • $\begingroup$ Can you give a reference for where you've seen the first representation? $\endgroup$ – Raphael Jan 14 '17 at 22:22
  • $\begingroup$ Please edit these into the question. $\endgroup$ – Raphael Jan 15 '17 at 11:20
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I agree. It's unclear what the leaves contain, so we can't guess at what purpose they serve. $\endgroup$ – Raphael Jan 15 '17 at 11:33
  • $\begingroup$ @Mr.Bombastic ok. So the comments are to clarify something, ask for further details. If you find some answer useful you might upvote it or accept if it suits you. If you find the answer on your own, you may answer yourself and then accept it. But in any case the open-ended discussions are not how this site works. Gathered guessing is not the best way to define the objective. Anyway I am glad that you found what you were looking for. $\endgroup$ – Evil Jan 16 '17 at 1:54
1
$\begingroup$

I can only guess at the intentions of whoever came up with that graphic, but here is an observation.

The leaves always point to the next node you have to visit in an in-order traversal. Therefore, if implemented as pointers (so they don't take up any extra space!), you can traverse the tree in in-order without a stack. You'll have to mark nodes as visited, though, so I'm not too sure where the big advantage is.

Note that, sometimes, textbook authors pick a particular flavor of things so they fit better with something they do later in the book, or for didactic reasons. The choices don't always make sense outside of the context, and neither do they have to.

$\endgroup$
  • $\begingroup$ I think I may have found something in another question: cs.stackexchange.com/questions/37157/…. Helps me a lot, but, again, what is the advantage of storing the points in the leaves? And why do range tree implementations seem to use regular BSTs? $\endgroup$ – Mr. Bombastic Jan 15 '17 at 1:43
  • $\begingroup$ @Mr.Bombastic I gave my best guess at the other question, but I don't think the two issues are necessarily related. They may be, though; it's impossible to tell from just the images. You'll have to read (and quote) some of the accompanying text! $\endgroup$ – Raphael Jan 15 '17 at 11:34
0
$\begingroup$

It's probably just for visual purposes, since actually doing what the first diagram does would effectively double the amount of space needed, really, unnecessarily and there are other deficiencies of such a design compared to regular BSTs with a range query. It is probably just for visualization purposes,(as seen here:http://www.bowdoin.edu/~ltoma/teaching/cs3250-CompGeom/spring16/Lectures/cg-rangetrees.pdf ), and the leaves aren't actually constructed like that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.