implementing an n-ary tree with a single link node

Question

Assume I have a set of nodes of an n-ary tree, packed in a dense array in depth-first order.

This tree (I'm showing links between each parent and its list of children):

  [A]
   |
  [B]--[E]--[F]
   |         |
  [C]--[D]  [G]

would be arranged in an array as [A, B, C, D, E, F, G].

I'm working in a memory-constrained environment, so I want to minimize storage requirements. If I define a node as follows:

typedef struct {
  char name;
  int link;
} node_t;

is there some clever coding of the link field that will allow me to traverse between nodes with these following functions? (Assume that each function has access to the containing depth-first array and the total number of nodes.)

node_t *sibling(int node_index);
node_t *children(int node_index);
node_t *parent(int node_index);

So, using the above example:

parent(A) => NULL
sibling(A) => NULL
children(A) => B
parent(B) => A
sibling(B) => E
children(B) => C
parent(C) => B
sibling(C) = D
children(C) => NULL

etc?

Update / Commentary:

Defining the link field as "the relative index to the next sibling" gets me pretty close to what I want. For example, if a node has zero children but does have a sibling, then its link field would be 1 (since we know that the nodes are arranged in depth-first order). If it has one or more children, the its link field would be greater than one (since those children would come before the node's sibling in the depth-first array).

But I'm not sure if defining the link as the "relative index to the next sibling" would work for finding the parent node, or for various edge cases.

Answer 1

Instead of link you could just store a depth field. depth == 1 signifies the root node, depth == 0 an unallocated slot. At least one unallocated slot is needed at the end of the array as a sentinel.

Note: this code is completely untested...

typedef struct {
  char name;
  unsigned int depth;
} node_t;

node_t parent(node_t *node) {
  unsigned int my_depth = node->depth;
  if (my_depth <= 1)
    return NULL;
  while (node->depth >= my_depth)
    node--;
  return node;
}

node_t children(node_t *node) {
  return node->depth < (node+1)->depth
    ? node+1
    : NULL;
}

node_t sibling(node_t *node) {
  unsigned int my_depth = node->depth;

  node++;
  while (node->depth > my_depth)
    node++; // skip children
  return node->depth == my_depth
    ? node
    : NULL;
}

Answer 2

I can't see any way to implement this efficiently without storing 2 pieces of structural information on each node (link, sizes etc). If you are going to use two links, I would suggest: Parent & First_Sibling

That gives you trivial implementations of:

node_t *sibling(int node_index);
node_t *parent(int node_index);

The function:

node_t *children(int node_index);

Is also pretty simply, because any existing children will be at node_index + 1, i.e.:

if (parent(node_index + 1) == node_index)
    return array[node_index + 1]
else
    return null

Note: You will also need to check you don't run off the end of the array.

---

I'm working in a memory-constrained environment, so I want to minimize storage requirements

Okay, let's tackle the elephant in the room - if you REALLY want to sacrifice runtime performance for memory it can be done. The critical observation is that:

• current index < index of the first sibling.
• current index > index of the parent.

So you can use the same link for both.

You need to add an additional check to the sibling() function to make sure the link is > the current index.

The parent() function is going to get messy - you can implement it by walking down the list of siblings until you find the last one, the last sibling will then point to its parent. You will need a special case for the root node (point to itself or null).

For simplicity you could leave the children() function unchanged.

Another alternative would be to flip the sign of every first child. I think (please check my logic here) that if the node at node_index + 1 is a "first_child" (has a negative link), it is a child of the current node.

Again, if your implementation uses a root node with index 0 you may need to add a special case for links pointing to the root node.

Horrific Performance.

To be clear the parent() function is now tied to list walk implementation, so performance will be really bad if nodes have a large number of direct descendants.

Answer 3

The depth-first order gives us the interesting property that each slice of the array can be interpreted as a sub-tree, and that your "relative index to the next sibling" corresponds to the size of that subtree. If a node has children, the first child will be at the next index.

However, this only lets us work forwards. It does not let us work backwards to the previous sibling, or upwards to the parent. There is also the issue that a node cannot know by itself whether it has a next sibling. Instead, we need to know the parent's size to know when the end of the tree is reached. For example, node D knows that E is the next sub-tree in the array, but cannot know whether this is a sibling of D or some previous node.

Simple solution: track two sizes / relative indexes

You can avoid this by tracking two sizes in each node – one size to work forwards to find the next subtree, and one size to work backwards or upwards. Which choice to make here depends on which operations you expect to be frequent.

• If the second size is the size of the left sibling tree, then you can move back to the left sibling in O(1) time. You can repeat this until the size is zero, in which case you have found the first sibling and know that the previous node is the parent. Thus, you can find the parent in O(siblings) time. Similarly, as you advance forwards, you know that the current subtree is the last sibling if the next tree indicates no left sibling size. Inserting or deleting a node requires you to update the right sibling as well, but that's just an O(1) cost. All in all, you can think of this as a doubly linked list.

• If the second size is the combined size of all left siblings, then you can move back to the parent in O(1) time. You can use this to check the parent's size, which you can use to stop when moving rightwards to the next sibling. However, finding the left sibling would require an O(siblings) search. Inserting or deleting a node requires updates to all rightward siblings, and each ancestor, and each ancestor's rightward siblings. While this approach simplifies queries, it would make updates more expensive.

Example of the second encoding:

We have a struct with fields name, size, and parent. Type offset is an unsigned integral type that is as small as possible, but large enough to hold the size of the largest possible tree.

typedef struct {
  char name;
  offset size;
  offset parent;
} node; 

Your example tree would be encoded as:

{
  { 'A', 7, 0 },
    { 'B', 3, 0 },
      { 'C', 1, 0 },
      { 'D', 1, 1 },
    { 'E', 1, 3 },
    { 'F', 2, 4 },
      { 'G', 1, 0 },
}

Consider how these offsets change when a node X is inserted as a child for E:

{
  { 'A', 8, 0 }, // <- update size
    { 'B', 3, 0 },
      { 'C', 1, 0 },
      { 'D', 1, 1 },
    { 'E', 2, 3 }, // <-- update size
      { 'X', 1, 0 },
    { 'F', 2, 5 },  // <-- update parent link
      { 'G', 1, 0 },
}

That is, all ancestors must be updated, and each involved node's rightward siblings.

Relevant movement operations can be defined as follows:

/// Return index of parent node.
/// For root node, returns zero.
size_t parent(node const* data, size_t self) {
  if (self == 0) return 0;  // root has no parent
  return self - data[self].parent - 1;
}

/// Return index of rightwards sibling.
/// If no rightward sibling exists, returns zero.
size_t right_sibling(node const* data, size_t self) {
  if (self == 0) return 0;  // root has no sibling
  size_t p = parent(data, self);
  size_t end = p + data[p].size;
  size_t next = self + data[self].size;
  // Return next sibling offset if it is within the parent's tree
  return (next < end) ? next : 0;
}

/// Return index of first child.
/// If no child exists, returns zero.
size_t first_child(node const* data, size_t self) {
  return (data[self].size > 1) ? self + 1 : 0;
}

Sacrifice speed for memory compactness by searching for the parent

It is also possible to go ahead with only one size, but that means finding the parent of the node involves a search that starts from the root. This makes all operations more expensive, since even just moving to the next sibling requires knowledge about the parent's subtree-size. All movements would now have a complexity around O(depth × left siblings), which should typically be around O(log size) in total, but could be as bad as O(size) for some trees.

It is convenient here to define a helper function to check whether a node is part of a parent's subtree:

bool is_in_parent(node const* data, size_t self, size_t parent) {
  size_t end = parent + data[parent].size;
  return parent <= self && self < end;
}

This simplifies the right_sibling() API:

size_t right_sibling(node const* data, size_t self) {
  if (self == 0) return 0;  // root has no sibling
  size_t p = parent(data, self);
  size_t next = self + data[self].size;
  return is_in_parent(data, next, p) ? next : 0;
}

However, the parent() function is now much more complex since it must search for the given node from the root:

size_t parent(node const* data, size_t self) {
  if (self == 0) return 0;  // root has no parent

  // loop through all ancestor levels
  size_t parent = 0;
  while (true) {
    assert(is_in_parent(data, self, parent);

    // loop through all siblings in this level
    for (size_t subtree = first_child(data, parent); ; subtree += data[subtree].size) {
      assert(subtree);
      assert(is_in_parent(data, subtree, parent);

      // found the target node
      if (subtree == self) return parent;

      // found a new parent
      if (is_in_parent(data, self, subtree)) {
        parent = subtree;
        break;
      }
    }
  }

  assert(false); // unreachable
}

Answer 4

After a good night's sleep I came up with this. Do you see any issues with it? (Yes, I do -- see update below)

| is_parent  |has_sibling| link |  child_at  | sibling_at | parent_at |
+------------+-----------+------+------------+------------+-----------+
|     no     |    no     |   0  |   -na-     |     -na-   | see below |
|     no     |    yes    |  -1  |   -na-     | [this] + 1 | see below |
|     yes    |    no     |   1  | [this] + 1 |     -na-   | see below |
|     yes    |    yes    |  N>1 | [this] + 1 | [this] + N | see below |
+------------+-----------+------+------------+------------+-----------+

Here are the corresponding tree-walking functions. (Sanity and bounds checking have been omitted for clarity.)

node_t nodes[];   // an array of nodes, ordered depth first.

node_t *sibling(node_t *node) {
  if ((node->link == 0) || (node->link == 1)) {
    return NULL;              // Node has no sibling
  } else if (node->link == -1) {
     return &node[1];         // Node's sibling is in next slot (no children)
  } else {
    return &node[node->link]; // Node's sibling follows N intervening children
  }
}

node_t *children(node_t *node) {
  if (node->link < 1) {
    return NULL;      // Node has no children
  } else {
    return &node[1];  // Node's child is next slot in the array
  }
}

bool is_parent(node_t *node) {
  return node->link >= 1;
}

node_t *parent(node_t *node) {
  // Search backwards in the node array for a parent node.  Since the array
  // is arranged depth-first, the "nearest" parent node must be this node's
  // parent.
  while (&node > &nodes) {
    node_t *yomama= &node[-1];
    if (is_parent(yomama)) {
      return yomama;    // Found the parent node
    }
    node = yomama;      // Continue searching backwards
  }
  return NULL;          // Ran into beginning of array with no parent found
}

update

There's flaw. Specifically, my assertion that

Since the array is arranged depth-first, the 'nearest' parent node must be this node's parent.

is incorrect. Consider this tree:

[A]
 |
[B]--[C]--[F]
      |
     [D]--[E]

Observing the depth-first traversal rule, these will be stored in the array as [A, B, C, D, E, F]. Parent node [A] has [B], [C], and [F] as children and parent node [C] has [D] and [E] as children.

But the buggy implementation of parent([F]) shown above will return [C], since that's the first parent encountered while searching backwards.

So I'm thinking Hans-Martin Mosner's solution saving the depth for each node may be the way to go.