Re: Visitor, dynamic_cast or ...

From: H. S. Lahman (h.lahman_at_verizon.net)
Date: 10/27/03 

Date: Mon, 27 Oct 2003 18:09:26 GMT

Responding to Daniel T....

> I've been reading up on OctTrees and I'm a little confused... As far as
> I can tell, all Nodes (both internal and leaf) should have an m_data
> element associated with them, isn't this true?

I haven't used OctTrees with that name, so I may be thinking of
something else. But I did use what appears to be the same idea a couple
of decades ago. I believe the m_data you are referring to is there
purely to support efficient navigation of the tree. That is, it allows
efficient searches by providing information in the parent node about
each of the child nodes.

Liberally translated from the original BLISS, [Node] looked something like:

class Node
{
private:
    Key minimum; // minimum key among all children
    Key maximum; // maximum key among all children
    Key nodeKeys[N]; // maximum key in each child.
    bool isLeaf[N]; // determine mapping of child.
...
}

This allowed very efficient searching at the price of potential
rebalancing overhead when keys were added. If the child was a leaf, it
would be mapped as an entirely different data structure when accessed.

*************
There is nothing wrong with me that could
not be cured by a capful of Drano.

H. S. Lahman
hsl@pathfindermda.com
Pathfinder Solutions -- Put MDA to Work
http://www.pathfindersol.com
(888)-OOA-PATH