Thread: QuadTree: Should Non-Leaf Nodes Contain Points?

Hi CBoard,

I'm implementing a quad tree for an assignment, and I'm not sure if every node should contain a list of pointers to every Point in its sub tree (implying the root node will contain all Points), or if only leaf nodes should contain the Points.

I have a feeling it won't really matter much, but I'm curious how it is typically done.

Thanks!

Originally Posted by kmdv

What are the main reasons to use a quadtree?
If you answer this question, you should also be able to answer yours.

Well my first thought is no, they shouldn't. Because it adds extra bulk to each node. But wouldn't having them there make range queries much faster because you wouldn't need to traverse down to the leaves to get all the points within a larger range.

So, I guess right now, both ways make sense to me. But I want to know if I'm missing something. Is it acceptable to implement it either way? Are there any major drawbacks?

Thanks

Originally Posted by kmdv

Yes, it misses its primary point - optimisation for amount of memory occupied.

OK, I get it. I guess I just underestimate how much memory a list of pointers could take.

Thanks for the help!