Theory Group

Considering Internal Representations of Heads of Trees

We have come up with three possibilities for representing the heads of trees within our already existing tree data structure.

This is part of the example tree we worked with:

Bitvectors Labeled Nodes:
The first idea was to mark each node with a bitvector. This vector would store d-1 values each representing which dimensions a node is a head in other than the maximal dimension. For the example tree nodes 0, 3 and 12 would have boolean values representing that they are heads in the second dimension. It has been noted that this would require in the worst case to traverse the entire tree and store this bitvector of size d-1 for each node.
Time: O(n)
Space: O(n*d)

Integer Labeled Nodes:
For this representation each node would contain an integer value. This value would represent the path to follow in order to find the head of a node. In the example tree node 1 would have a value 2 associated with it meaning that the first dimensional successor of its first dimensional successor should be followed. The 2 would represent how many times the first dimensional successor would have to be followed. Node 10 would similarly also have a 2 associated with it.
Time: O(n)
Space: O(n*sizeof(int))

Pointer Labeled Nodes:
Pointer labeled nodes would have a vector of pointers which reference the head of the node in each dimension. In the example tree 0 would reference 3 in the second dimension, and 3 would reference 12 in the second dimension. This would allow for constant time access to the heads of nodes. The space could be worse than other possibilities but not significantly. This is the method we have decided to implement.
Time: O(1)
Space: O(n*d*sizeof(pointer))

Posted by lemanal at June 28, 2004 04:13 PM