1
$\begingroup$

I need a tree structure that works roughly like the following

  • for each new child I need to match it (with some criteria) with a parent from the previous level only

  • when the tree is completely initialized, for each leaf I need to find the first parent ancestor that has siblings, i.e. the node just after the branching point.

While the latter is pretty easy with a tipical tree structure, for the first I'd like to just access all nodes of a layer without traversing the whole tree (even with BFS). Does this have a name?

I'm thinking to just keep track of level number for each node and build a second structure to represent levels.

Improve this question
$\endgroup$
2
  • $\begingroup$ The wording is slightly unusual in my eyes: for a child, there should be exactly one parent, which should be known/well-defined on insertion(new): are you talking about potential parents to select from? First parent might be first ancestor. $\endgroup$
    – greybeard
    Jan 28, 2018 at 9:42
  • $\begingroup$ You're right, I meant ancestor $\endgroup$
    – filippo
    Jan 28, 2018 at 11:20

2 Answers 2

Reset to default
2
$\begingroup$

To support the operations mentioned - especially level-order traversal (or walk) - in time bounded by the depth, you don't need an extra attribute for each node.

For a "semi-static" tree¹, you could use an array of nodes to store it:
For every level, keep the index just beyond.
For every node, keep parent, for non-leaf nodes, children ("first" child), too:
siblings are successive nodes with same parent.

For a "dynamic" tree, modify the [typical] tree structure keeping children, siblings and optionally parent to support level-order traversal:
Change sibling to next in same level - not a sibling iff different parent.
You may need support for first in level, or "the list of nodes in the same level" to be circular to be able to access all of them starting from any-one thereof.

[1]: semi-static tree: only structural change is addition of nodes.
(The task sketched may have another restriction: no node with children will get another child once a different node gets one.)
(or even static: [once] the tree is completely initialized)

Improve this answer
$\endgroup$
0
$\begingroup$

If it’s a complete tree, you could use an array to store it. Accessing parents, siblings, and children would be quite simple and you wouldn’t have to traverse the tree.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ It's not complete, any node could have any number of children. The only thing I know in advance is the number of layers. Another thing I can exploit is that once it's initialized it's fixed, and I only need to climb it backwards from leaves looking for branching points. $\endgroup$
    – filippo
    Nov 29, 2017 at 6:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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