Sign in to follow this  
Morpheus011

O(1) searching through an n-ary tree

Recommended Posts

I'm currently working on a rendering system for my new game. The rendering engine relies on my base object which is a node class that only has the members CNode *m_pParent and vector<CNode *> m_pChildren. Because this is going to be used for rendering (as well as various other things) I want to be able to iterate through my tree quickly (which is why I picked vectors) and find a given Node at O(1) speeds. That's the problem though, an N-ary tree I believe only allows me at best (when considering the worst case scenario) O(N) searching. I potentially have to iterate through my entire tree before finding the element I am looking for. I'm about to break out the good ol' Donald Knuth lovin, but if anyone here has any suggestions (some sort of mapping scheme, maybe a better way of tracking the tree, thus allowing me direct indexing...?) it would be appreciated. Thanks

Share this post


Link to post
Share on other sites
Well, what criteria are you going to be using to find things? Are you searching based on name... based on intersection...? Also, realistically, what is your tree's branching going to look like? Scene graphs tend towards a rather pathological structure... one root node, which has one child, which has one child, which has ELEVENTY BAZILLION children, each of which has one child.

If you're just iterating through all the nodes, obviously there's no way to visit N nodes in O(1). That's true regardless of what data structure you're using.

Share this post


Link to post
Share on other sites
I wasn't entirely sure of what I would use this for yet. My reasoning for wanting to have it in there is that in case down the road I do need it, it will be in, and it will be fast.

I'm thinking a potential use for it would be that if I have some object that I need to all of a sudden add an effect to, I wouldn't need to iterate through the entire scene graph, and instead could just directly manipulate that object. But you're absolutely correct in saying that this is data structure independent. My initial method of searching was going to be by memory address comparisons, this is my first shot at a scene graph type structure for a rendering system so I'm still working some of the kinks out.

Perhaps you could make a suggestion as to how you would search through your eleventy bajillion objects. I'm thinking having some sort of unique identifier that allows for direct indexing is probably the best solution, but I'd like to hear some other ideas as well.

Thanks

Share this post


Link to post
Share on other sites
The way you search through eleventy bazillion objects (not eleventy bajillion... you can't do that in real-time yet) to find a particular one, is you don't. If an object cares about that node, it keeps a pointer to the node. The memory address IS the unique identifier, and the accession of the node doesn't involve the data structure at all. Trees only help with searches which are hierarchical; that is, where a parent node is ever able to guarantee that the target node is in its hierarchy, or guarantee that it is not.

Share this post


Link to post
Share on other sites
The only two O(1) containers are either a vector, assuming your key is index-into-vector, or a hash look-up based on unique key.

If your tree is indexed on some known quantity, then finding a node based on that index in a tree is O(log N).

If you care about particular nodes, chances are, you want to hold on to a pointer to that node. If you've found it once, why look it up again? Also, keeping a single tree is so 1980 -- if you want a scene graph that you can query in a bunch of different ways (spatial, by name, by attribute, etc), then you need to keep an appropriate index per queryable parameter.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
A metric bajillion is a heck of a lot. An imperial bajillion is 1.563 hecks of a lot.


1/8.3 bazillion also equals national debt. And it's not usually converted into furlongs per fortnight, since it overflows most real types.

Share this post


Link to post
Share on other sites
Any structure in which you do not know ahead of time which node to visit (e.g. by virtue of an index or a key) requires time proportional to a function of N (but should never be worse than O(N)). Either you use indexing of some kind and get this benefit, or you do not.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this