Cheap and Secure Web Hosting Provider : See Now

[Solved]: I/O cost to traverse a tree stored in preorder form

, , No Comments
Problem Detail: 

Let T be a binary tree that is stored in the disk following the preorder layout.

For example if this is $T$:

enter image description here

then $T$ will be stored in the disk as follows:

10, 11, 0, 12, 13, 2, 7, 3, 14, 1, 15, 16, 4, 8, 17, 18, 5, 9, 6

Every node of the tree is a struct that stores the offset of the left child, the offset of the right child, the id of the node and a size variable. If a node is a leaf the offsets are set to -1.

Suppose that now in every node $u \in T$ we want to know what is the size of the subtree rooted on $u$. Assume that the elements between the disk and the memory are transferred in blocks of size $B$, the size of the memory is $M$ and it holds that $M \geq B$. Is it possible to do that in $O(\frac{N}{B})$ I/Os?

Asked By : jsguy

Answered By : orlp

It is possible to do it in $O(\frac{N}{B})$ if you have $B + D$ memory available, where $D$ is the maximum depth of the tree. Algorithm:

  1. Read $B$ nodes into a buffer.
  2. For each node in the buffer:
    1. Push $(node.id, num\_children(node), 0)$ to stack $S$ (respectively $(id, num, d)$).
    2. While $S.peek().num = 0$:
      1. $d = S.peek().d$
      2. Output $(S.peek().id, d)$.
      3. $S.pop()$
      4. $S.peek().num = S.peek().num - 1$
      5. $S.peek().d = max(S.peek().d, d + 1)$.
  3. If there are more nodes to process, go to 1.

The idea behind this algorithm is to associate pushing on the stack with going down a child node, and popping coming back up to a parent node.

If we initialize every node with a counter containing the number of child nodes, and we decrement this counter everytime after popping, it means that once the counter hits 0 we have visited every child node as we visit this node: we are in post-order.

We also store a maximum subtree size $d$ with every node. If we pop (go back to visit the parent node) we store the maximum of $node.d$ and $child\_node.d + 1$ into this node. This means that once we are in post-order we have the maximum size of all child subtrees + 1 stored in $d$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63413

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback